Hostname: page-component-cd9895bd7-lnqnp Total loading time: 0 Render date: 2024-12-26T07:40:18.321Z Has data issue: false hasContentIssue false
  • English
  • Français

McCammond’s normal forms for free aperiodic semigroups revisited

Part of: Semigroups Theory of computing

Published online by Cambridge University Press:  01 January 2015

J. Almeida ,
J. C. Costa  and
M. Zeitoun
J. Almeida
Affiliation:
CMUP, Departamento de Matemática, Faculdade de Ciências, Universidade do Porto, Rua do Campo Alegre 687, 4169-007 Porto, Portugal email [email protected]
J. C. Costa
Affiliation:
CMAT, Departamento de Matemática e Aplicações, Universidade do Minho, Campus de Gualtar, 4700-320 Braga, Portugal email [email protected]
M. Zeitoun
Affiliation:
LaBRI, Université Bordeaux & CNRS UMR 5800, 351 cours de la Libération, 33405 Talence Cedex, France email [email protected]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

This paper revisits the solution of the word problem for ${\it\omega}$-terms interpreted over finite aperiodic semigroups, obtained by J. McCammond. The original proof of correctness of McCammond’s algorithm, based on normal forms for such terms, uses McCammond’s solution of the word problem for certain Burnside semigroups. In this paper, we establish a new, simpler, correctness proof of McCammond’s algorithm, based on properties of certain regular languages associated with the normal forms. This method leads to new applications.

MSC classification

Primary: 20M05: Free semigroups, generators and relations, word problems 20M07: Varieties and pseudovarieties of semigroups
Secondary: 20M35: Semigroups in automata theory, linguistics, etc. 68Q70: Algebraic theory of languages and automata
Type
Research Article
Information
LMS Journal of Computation and Mathematics , Volume 18 , Issue 1 , 2015 , pp. 130 - 147
Copyright
© The Author(s) 2015 

References

Almeida, J., ‘Implicit operations on finite J-trivial semigroups and a conjecture of I. Simon’, J. Pure Appl. Algebra 69 (1990) 205–218.CrossRefGoogle Scholar
Almeida, J., Finite semigroups and universal algebra (World Scientific, Singapore, 1995).CrossRefGoogle Scholar
Almeida, J., ‘Hyperdecidable pseudovarieties and the calculation of semidirect products’, Int. J. Algebra Comput. 9 (1999) 241–261.CrossRefGoogle Scholar
Almeida, J., ‘Some algorithmic problems for pseudovarieties’, Publ. Math. Debrecen 54(suppl.) (1999) 531–552; Automata and formal languages, VIII (Salgótarján, 1996).Google Scholar
Almeida, J., ‘Profinite semigroups and applications’, Structural theory of automata, semigroups, and universal algebra: Proceedings of the NATO Advanced Study Institute on Structural Theory of Automata, Semigroups and Universal Algebra, Montréal, Québec, Canada, 7–18 July 2003 , NATO Science Series II: Mathematics, Physics and Chemistry 207 (eds Kudryavtsev, V. B. and Rosenberg, I. G.; Springer, New York, 2005).Google Scholar
Almeida, J., Costa, J. C. and Zeitoun, M., ‘Tameness of pseudovariety joins involving R ’, Monatsh. Math. 146 (2005) no. 2, 89–111.CrossRefGoogle Scholar
Almeida, J., Costa, J. C. and Zeitoun, M., ‘Complete reducibility of systems of equations with respect to R’, Port. Math. 64 (2007) 445–508.Google Scholar
Almeida, J., Costa, J. C. and Zeitoun, M., ‘Closures of regular languages for profinite topologies’, Semigroup Forum 89 (2014) 20–40.CrossRefGoogle Scholar
Almeida, J., Costa, J. C. and Zeitoun, M., ‘Iterated periodicity over finite aperiodic semigroups’, Eur. J. Combin. 37 (2014) 115–149.CrossRefGoogle Scholar
Almeida, J. and Steinberg, B., ‘On the decidability of iterated semidirect products and applications to complexity’, Proc. London Math. Soc. (3) 80 (2000) 50–74.CrossRefGoogle Scholar
Almeida, J. and Steinberg, B., ‘Syntactic and global semigroup theory, a synthesis approach’, Algorithmic problems in groups and semigroups (eds Birget, J. C., Margolis, S. W., Meakin, J. and Sapir, M. V.; Birkhäuser, Boston, 2000) 1–23.Google Scholar
Almeida, J. and Zeitoun, M., ‘An automata-theoretic approach to the word problem for 𝜔-terms over R ’, Theoret. Comput. Sci. 370 (2007) 131–169.CrossRefGoogle Scholar
Costa, J. C., ‘Free profinite locally idempotent and locally commutative semigroups’, J. Pure Appl. Algebra 163 (2001) 19–47.CrossRefGoogle Scholar
Costa, J. C., ‘Canonical forms for free 𝜅-semigroups’, Discrete Math. Theor. Comput. Sci. 16 (2014) no. 1, 159–178.Google Scholar
Costa, J. C. and Nogueira, C., ‘Complete reducibility of the pseudovariety LSl ’, Int. J. Algebra Comput. 19 (2009) 1–36.CrossRefGoogle Scholar
Costa, J. C. and Teixeira, M. L., ‘Tameness of the pseudovariety LSl ’, Int. J. Algebra Comput. 14 (2004) 627–654.CrossRefGoogle Scholar
Henckell, K., ‘Pointlike sets: the finest aperiodic cover of a finite semigroup’, J. Pure Appl. Algebra 55 (1988) no. 1–2, 85–126.CrossRefGoogle Scholar
Huschenbett, M. and Kufleitner, M., ‘Ehrenfeucht-Fraïssé games on omega-terms’, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014) , Leibniz International Proceedings in Informatics (LIPIcs) 25 (eds Mayr, E. W. and Portier, N.; Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, 2014) 374–385.Google Scholar
Lothaire, M., Combinatorics on words (Addison-Wesley, Reading, MA, 1983).Google Scholar
Lothaire, M., Algebraic combinatorics on words (Cambridge University Press, Cambridge, 2002).CrossRefGoogle Scholar
McCammond, J., ‘The solution to the word problem for the relatively free semigroups satisfying t a = t a+b with a⩾6’, Int. J. Algebra Comput. 1 (1991) 1–32.CrossRefGoogle Scholar
McCammond, J., ‘Normal forms for free aperiodic semigroups’, Int. J. Algebra Comput. 11 (2001) 581–625.CrossRefGoogle Scholar
McNaughton, R. and Papert, S., Counter-free automata (MIT Press, Cambridge, MA, 1971).Google Scholar
Moura, A., ‘The word problem for 𝜔-terms over DA ’, Theoret. Comput. Sci. 412 (2011) no. 46, 6556–6569.CrossRefGoogle Scholar
Place, T. and Zeitoun, M., ‘Separating regular languages with first-order logic’, CSL-LICS ’14: Proceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) (ACM Press, New York, 2014).Google Scholar
Rhodes, J. and Steinberg, B., The q-theory of finite semigroups , Monographs in Mathematics (Springer, New York, 2009).CrossRefGoogle Scholar
Schützenberger, M. P., ‘On finite monoids having only trivial subgroups’, Inform. and Control 8 (1965) 190–194.CrossRefGoogle Scholar