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},
}