On the simplest centralizer of a language
Massazza, Paolo ; Salmela, Petri
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006), p. 295-301 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

Given a finite alphabet Σ and a language L⊆Σ + , the centralizer of L is defined as the maximal language commuting with it. We prove that if the primitive root of the smallest word of L (with respect to a lexicographic order) is prefix distinguishable in L then the centralizer of L is as simple as possible, that is, the submonoid L ☆ . This lets us obtain a simple proof of a known result concerning the centralizer of nonperiodic three-word languages.

Publié le : 2006-01-01
DOI : https://doi.org/10.1051/ita:2006014
Classification:  68Q70,  68R15 
@article{ITA_2006__40_2_295_0,
     author = {Massazza, Paolo and Salmela, Petri},
     title = {On the simplest centralizer of a language},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {40},
     year = {2006},
     pages = {295-301},
     doi = {10.1051/ita:2006014},
     mrnumber = {2252640},
     zbl = {1112.68097},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2006__40_2_295_0}
}

Massazza, Paolo; Salmela, Petri. On the simplest centralizer of a language. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006) pp. 295-301. doi : 10.1051/ita:2006014. http://gdmltest.u-ga.fr/item/ITA_2006__40_2_295_0/

[1] J. Berstel and D. Perrin, Theory of codes. Academic Press, New York (1985). | MR 797069 | Zbl 0587.68066

[2] J.A. Brzozowski and E. Leiss, On equations for regular languages, finite automata, and sequential networks. Theor. Comp. Sci. 10 (1980) 19-35. | Zbl 0415.68023

[3] C. Choffrut, J. Karhumäki and N. Ollinger, The commutation of finite sets: a challenging problem. Theor. Comp. Sci. 273 (2002) 69-79. | Zbl 1014.68128

[4] N. Chomsky and M.P. Schützenberger, The algebraic theory of context-free languages. Computer Programming and Formal Systems, edited by P. Braffort and D. Hirschberg. North-Holland, Amsterdam (1963) 118-161. | Zbl 0148.00804

[5] J.H. Conway, Regular Algebra and Finite Machines. Chapman & Hall, London (1971). | Zbl 0231.94041

[6] J. Karhumäki and I. Petre, The branching point approach to Conway's problem, in Formal and Natural Computing, edited by W. Brauer, H. Ehrig, J. Karhumäki, A. Salomaa. Lect. Notes Comput. Sci. 2300 (2002) 69-76. | Zbl 1060.68095

[7] J. Karhumäki and I. Petre, Conway's problem for three-word sets. Theor. Comp. Sci. 289 (2002) 705-725. | Zbl 1061.68097

[8] J. Karhumäki, M. Latteux and I. Petre, Commutation with codes. Theor. Comp. Sci. 340 (2005) 322-333. | Zbl 1079.68051

[9] J. Karhumäki, M. Latteux and I. Petre, Commutation with ternary sets of words. Theory Comput. Syst. 38 (2005) 161-169. | Zbl 1066.68102

[10] M. Kunc, The power of commuting with finite sets of words, in Proc. of STACS 2005. Lect. Notes Comput. Sci. 3404 (2005) 569-580. | Zbl 1119.68108

[11] R.C. Lyndon and M.P. Schützenberger, The equation a m =b n c p in a free group. Michigan Math. J. 9 (1962) 289-298. | Zbl 0106.02204

[12] P. Massazza, On the equation XL=LX, in Proc. of WORDS 2005, Publications du Laboratoire de Combinatoire et d'Informatique Mathématique, Montréal 36 (2005) 315-322.

[13] D. Perrin, Codes conjugués. Inform. Control 20 (1972) 222-231. | Zbl 0254.94015

[14] B. Ratoandromanana, Codes et motifs. RAIRO-Inf. Theor. Appl. 23 (1989) 425-444. | Numdam | Zbl 0689.68102