On the simplest centralizer of a language

Paolo Massazza; Petri Salmela

RAIRO - Theoretical Informatics and Applications (2006)

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

Abstract

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

How to cite

top

Massazza, 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
  1. J. Berstel and D. Perrin, Theory of codes. Academic Press, New York (1985).  Zbl0587.68066
  2. 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
  3. 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
  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.  Zbl0148.00804
  5. J.H. Conway, Regular Algebra and Finite Machines. Chapman & Hall, London (1971).  Zbl0231.94041
  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.  Zbl1060.68095
  7. J. Karhumäki and I. Petre, Conway's problem for three-word sets. Theor. Comp. Sci. 289 (2002) 705–725.  Zbl1061.68097
  8. J. Karhumäki, M. Latteux and I. Petre, Commutation with codes. Theor. Comp. Sci. 340 (2005) 322–333.  
  9. J. Karhumäki, M. Latteux and I. Petre, Commutation with ternary sets of words. Theory Comput. Syst. 38 (2005) 161–169.  
  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.  Zbl1119.68108
  11. 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
  12. 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.  
  13. D. Perrin, Codes conjugués. Inform. Control 20 (1972) 222–231.  Zbl0254.94015
  14. B. Ratoandromanana, Codes et motifs. RAIRO-Inf. Theor. Appl. 23 (1989) 425–444.  Zbl0689.68102

NotesEmbed ?

top

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.