Given a finite alphabet and a language , the centralizer of is defined as the maximal language commuting with it. We prove that if the primitive root of the smallest word of (with respect to a lexicographic order) is prefix distinguishable in then the centralizer of is as simple as possible, that is, the submonoid . This lets us obtain a simple proof of a known result concerning the centralizer of nonperiodic three-word languages.
Keywords: commutation equation, centralizer, lexicographic order
@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}, pages = {295--301}, publisher = {EDP-Sciences}, volume = {40}, number = {2}, year = {2006}, doi = {10.1051/ita:2006014}, mrnumber = {2252640}, zbl = {1112.68097}, language = {en}, url = {http://www.numdam.org/articles/10.1051/ita:2006014/} }
TY - JOUR AU - Massazza, Paolo AU - Salmela, Petri TI - On the simplest centralizer of a language JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2006 SP - 295 EP - 301 VL - 40 IS - 2 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ita:2006014/ DO - 10.1051/ita:2006014 LA - en ID - ITA_2006__40_2_295_0 ER -
%0 Journal Article %A Massazza, Paolo %A Salmela, Petri %T On the simplest centralizer of a language %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2006 %P 295-301 %V 40 %N 2 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ita:2006014/ %R 10.1051/ita:2006014 %G en %F 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, Volume 40 (2006) no. 2, pp. 295-301. doi : 10.1051/ita:2006014. http://www.numdam.org/articles/10.1051/ita:2006014/
[1] Theory of codes. Academic Press, New York (1985). | MR | Zbl
and ,[2] On equations for regular languages, finite automata, and sequential networks. Theor. Comp. Sci. 10 (1980) 19-35. | Zbl
and ,[3] The commutation of finite sets: a challenging problem. Theor. Comp. Sci. 273 (2002) 69-79. | Zbl
, and ,[4] 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
and ,[5] Regular Algebra and Finite Machines. Chapman & Hall, London (1971). | Zbl
,[6] 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
and ,[7] Conway's problem for three-word sets. Theor. Comp. Sci. 289 (2002) 705-725. | Zbl
and ,[8] Commutation with codes. Theor. Comp. Sci. 340 (2005) 322-333. | Zbl
, and ,[9] Commutation with ternary sets of words. Theory Comput. Syst. 38 (2005) 161-169. | Zbl
, and ,[10] The power of commuting with finite sets of words, in Proc. of STACS 2005. Lect. Notes Comput. Sci. 3404 (2005) 569-580. | Zbl
,[11] The equation in a free group. Michigan Math. J. 9 (1962) 289-298. | Zbl
and ,[12] On the equation , in Proc. of WORDS 2005, Publications du Laboratoire de Combinatoire et d'Informatique Mathématique, Montréal 36 (2005) 315-322.
,[13] Codes conjugués. Inform. Control 20 (1972) 222-231. | Zbl
,[14] Codes et motifs. RAIRO-Inf. Theor. Appl. 23 (1989) 425-444. | Numdam | Zbl
,Cited by Sources: