# On the simplest centralizer of a language

RAIRO - Theoretical Informatics and Applications (2006)

- Volume: 40, Issue: 2, page 295-301
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topMassazza, Paolo, and Salmela, Petri. "On the simplest centralizer of a language." RAIRO - Theoretical Informatics and Applications 40.2 (2006): 295-301. <http://eudml.org/doc/249730>.

@article{Massazza2006,

abstract = {
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.
},

author = {Massazza, Paolo, Salmela, Petri},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {Commutation equation; centralizer; lexicographic order.; commutation equation; lexicographic order},

language = {eng},

month = {7},

number = {2},

pages = {295-301},

publisher = {EDP Sciences},

title = {On the simplest centralizer of a language},

url = {http://eudml.org/doc/249730},

volume = {40},

year = {2006},

}

TY - JOUR

AU - Massazza, Paolo

AU - Salmela, Petri

TI - On the simplest centralizer of a language

JO - RAIRO - Theoretical Informatics and Applications

DA - 2006/7//

PB - EDP Sciences

VL - 40

IS - 2

SP - 295

EP - 301

AB -
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.

LA - eng

KW - Commutation equation; centralizer; lexicographic order.; commutation equation; lexicographic order

UR - http://eudml.org/doc/249730

ER -

## References

top- J. Berstel and D. Perrin, Theory of codes. Academic Press, New York (1985). Zbl0587.68066
- J.A. Brzozowski and E. Leiss, On equations for regular languages, finite automata, and sequential networks. Theor. Comp. Sci. 10 (1980) 19–35. Zbl0415.68023
- C. Choffrut, J. Karhumäki and N. Ollinger, The commutation of finite sets: a challenging problem. Theor. Comp. Sci. 273 (2002) 69–79. Zbl1014.68128
- 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. Zbl0148.00804
- J.H. Conway, Regular Algebra and Finite Machines. Chapman & Hall, London (1971). Zbl0231.94041
- 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. Zbl1060.68095
- J. Karhumäki and I. Petre, Conway's problem for three-word sets. Theor. Comp. Sci. 289 (2002) 705–725. Zbl1061.68097
- J. Karhumäki, M. Latteux and I. Petre, Commutation with codes. Theor. Comp. Sci. 340 (2005) 322–333.
- J. Karhumäki, M. Latteux and I. Petre, Commutation with ternary sets of words. Theory Comput. Syst. 38 (2005) 161–169.
- M. Kunc, The power of commuting with finite sets of words, in Proc. of STACS 2005 . Lect. Notes Comput. Sci.3404 (2005) 569–580. Zbl1119.68108
- R.C. Lyndon and M.P. Schützenberger, The equation am = bncp in a free group. Michigan Math. J. 9 (1962) 289–298. Zbl0106.02204
- 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.
- D. Perrin, Codes conjugués. Inform. Control 20 (1972) 222–231. Zbl0254.94015
- B. Ratoandromanana, Codes et motifs. RAIRO-Inf. Theor. Appl. 23 (1989) 425–444. Zbl0689.68102

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.