Commutation with codes

The centralizer of a set of words X is the largest set of words C ( X ) commuting with X: X C ( X ) = C ( X ) X. It has been a long standing open question due to [J. H. Conway, Regular Algebra and Finite Machines, Chapman & Hall, London (1971). ], whether the centralizer of any rational set is rational. While the answer turned out to be negative in general, see [M. Kunc, Proc. of ICALP 2004, Lecture Notes in Computer Science, Vol. 3142, Springer, Berlin, 2004, pp. 870–881. ], we prove here that the situation is different for codes: the centralizer of any rational code is rational and if the code is finite, then the centralizer is finitely generated. This result has been previously proved only for binary and ternary sets of words in a series of papers by the authors and for prefix codes in an ingenious paper by [B. Ratoandromanana, RAIRO Inform. Theor. 23(4) (1989) 425–444. ]—many of the techniques we use in this paper follow her ideas. We also give in this paper an elementary proof for the prefix case.

Authors

• Juhani Karhumäki
• Michel Latteux
• Ion Petre

Keywords

• Codes
• Commutation
• Centralizer
• Conway's problem
• Prefix codes