• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

The Commutation with Ternary Sets of Words

Juhani Karhumäki, Michel Latteux, Ion Petre, The Commutation with Ternary Sets of Words. Theory of Computing Systems 38(2), 161–169, 2005.

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 = F^I , 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 Karhumaki and Petre, and provides positive answers to special cases of some intriguing questions on commutation of languages, raised by Ratoandromanana and Conway.

BibTeX entry:

@ARTICLE{jKaLaPe5a,
  title = {The Commutation with Ternary Sets of Words},
  author = {Karhumäki, Juhani and Latteux, Michel and Petre, Ion},
  journal = {Theory of Computing Systems},
  volume = {38},
  number = {2},
  publisher = {Springer-Verlag},
  pages = {161–169},
  year = {2005},
}

Publication Forum rating of this publication: level 2

Edit publication