Back to Search
Start Over
Commutation with Ternary Sets of Words
- Source :
- Theory of Computing Systems. 38:161-169
- Publication Year :
- 2005
- Publisher :
- Springer Science and Business Media LLC, 2005.
-
Abstract
- We prove that for any nonperiodic set of words F \subseteq Σ+ 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 \subseteq ℕ. 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.
Details
- ISSN :
- 14330490 and 14324350
- Volume :
- 38
- Database :
- OpenAIRE
- Journal :
- Theory of Computing Systems
- Accession number :
- edsair.doi...........e70344d792389fd55175a64479f991ee