Conway's problem for three-word sets

We prove two results on commutation of languages. First, we show that the maximal language commuting with a three-element language, i. e. its centralizer, is rational, thus giving an affirmative answer to a special case of a problem proposed by Conway in 1971. Second, we characterize all languages commuting with a three-element code. The characterization is similar to the one proved by Bergman for polynomials over noncommuting variables (see Trans. Am. Math. Soc. 137 (1969) 327 and Algebraic Combinatorics on Words, Cambridge University Press, Cambridge, 2000): A language commutes with a three-element code X if and only if it is a union of powers of X.

Authors

• Juhani Karhumäki
• Ion Petre

Keywords

No keywords are indexed for this paper.