The commutation with ternary sets of words (bibtex)
by Karhumaki, Juhani, Latteux, Michel and Petre, Ion
Abstract:
We prove that for any nonperiodic set of words F ⊆ Σ+ with at most three elements, the centralizer of F, i.e., the largest set commuting with F, is F∗. Moreover, any set X commuting with F is of the form X = FI, for some I ⊆ N. A boundary point is thus established, as these results do not hold for all languages with at least four words. This solves a conjecture of Karhum¨aki and Petre, 2000, and provides positive answers to special cases of some intriguing questions on commutation of languages, raised by Ratoandromanana, 1989 and Conway, 1971.
Reference:
The commutation with ternary sets of words (Karhumaki, Juhani, Latteux, Michel and Petre, Ion), In Theory of Computing Systems, Springer, volume 38, 2005.
Bibtex Entry:
@Article{j33,
  author    = {Karhumaki, Juhani AND Latteux, Michel AND Petre, Ion},
  title     = {The commutation with ternary sets of words},
  journal   = {Theory of Computing Systems},
  year      = {2005},
  volume    = {38},
  number    = {2},
  pages     = {161-169},
  abstract  = {We prove that for any nonperiodic set of words F ⊆ Σ+ with at most three elements, the centralizer of F, i.e., the largest set commuting with F, is F∗. Moreover, any set X commuting with F is of the form X = FI, for some I ⊆ N. A boundary point is thus established, as these results do not hold for all languages with at least four words. This solves a conjecture of Karhum¨aki and Petre, 2000, and provides positive answers to special cases of some intriguing questions on commutation of languages, raised by Ratoandromanana, 1989 and Conway, 1971.},
  file      = {KLP2005b.pdf:pdfs/KLP2005b.pdf:PDF},
  keywords  = {Rational languages, combinatorics on words, language equations,},
  publisher = {Springer},
}
Powered by bibtexbrowser