On the simplest centralizer of a language

Massazza, Paolo; Salmela, Petri

doi:10.1051/ita:2006014

Massazza, Paolo ; Salmela, Petri

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006) no. 2, pp. 295-301.

Résumé

Given a finite alphabet $Σ$ and a language $L \subseteq Σ^{+}$ , 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.

MR Zbl

DOI : 10.1051/ita:2006014

Classification : 68Q70, 68R15
Mots clés : 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, Tome 40 (2006) no. 2, pp. 295-301. doi : 10.1051/ita:2006014. http://www.numdam.org/articles/10.1051/ita:2006014/

Bibliographie
Cité par

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

[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

[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

[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

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

[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

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

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

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

[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

[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

[12] P. Massazza, On the equation $X L = L X$ , 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

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

Cité par Sources :