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
topHow 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).
- J.A. Brzozowski and E. Leiss, On equations for regular languages, finite automata, and sequential networks. Theor. Comp. Sci. 10 (1980) 19–35.
- C. Choffrut, J. Karhumäki and N. Ollinger, The commutation of finite sets: a challenging problem. Theor. Comp. Sci. 273 (2002) 69–79.
- 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.
- J.H. Conway, Regular Algebra and Finite Machines. Chapman & Hall, London (1971).
- 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.
- J. Karhumäki and I. Petre, Conway's problem for three-word sets. Theor. Comp. Sci. 289 (2002) 705–725.
- 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.
- R.C. Lyndon and M.P. Schützenberger, The equation am = bncp in a free group. Michigan Math. J. 9 (1962) 289–298.
- 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.
- B. Ratoandromanana, Codes et motifs. RAIRO-Inf. Theor. Appl. 23 (1989) 425–444.
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.