Back to Search Start Over

Commutation with Ternary Sets of Words

Authors :
Ion Petre
Michel Latteux
Juhani Karhumäki
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