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