Hostname: page-component-cd9895bd7-8ctnn Total loading time: 0 Render date: 2024-12-27T09:32:16.307Z Has data issue: false hasContentIssue false
  • English
  • Français

On the simplest centralizer of a language

Published online by Cambridge University Press:  20 July 2006

Paolo Massazza  and
Petri Salmela
Paolo Massazza
Affiliation:
Dipartimento di Informatica e Comunicazione, Università degli Studi dell'Insubria, via Mazzini 5, 21100 Varese, Italy; [email protected]
Petri Salmela
Affiliation:
Department of Mathematics and TUCS, University of Turku, 20014 Turku, Finland; [email protected]
Get access

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.

Keywords

Commutation equationcentralizerlexicographic order.
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 40 , Issue 2: Alberto Bertoni: Climbing summits , April 2006 , pp. 295 - 301
Copyright
© EDP Sciences, 2006

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

J. Berstel and D. Perrin, Theory of codes. Academic Press, New York (1985).
Brzozowski, J.A. and Leiss, E., On equations for regular languages, finite automata, and sequential networks. Theor. Comp. Sci. 10 (1980) 19–35. CrossRef
Choffrut, C., Karhumäki, J. and Ollinger, N., The commutation of finite sets: a challenging problem. Theor. Comp. Sci. 273 (2002) 69–79. CrossRef
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).
Karhumäki, J. and Petre, I., 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. CrossRef
Karhumäki, J. and Petre, I., Conway's problem for three-word sets. Theor. Comp. Sci. 289 (2002) 705–725. CrossRef
Karhumäki, J., Latteux, M. and Petre, I., Commutation with codes. Theor. Comp. Sci. 340 (2005) 322–333. CrossRef
Karhumäki, J., Latteux, M. and Petre, I., Commutation with ternary sets of words. Theory Comput. Syst. 38 (2005) 161–169. CrossRef
Kunc, M., The power of commuting with finite sets of words, in Proc. of STACS 2005 . Lect. Notes Comput. Sci. 3404 (2005) 569–580. CrossRef
Lyndon, R.C. and Schützenberger, M.P., 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.
Perrin, D., Codes conjugués. Inform. Control 20 (1972) 222–231. CrossRef
Ratoandromanana, B., Codes et motifs. RAIRO-Inf. Theor. Appl. 23 (1989) 425–444. CrossRef