Playing with Conway’s problem

AbstractThe centralizer of a language is the maximal language commuting with it. The question, raised by Conway in [J.H. Conway, Regular Algebra and Finite Machines, Chapman Hall, 1971], whether the centralizer of a rational language is always rational, recently received a lot of attention. In Kunc [M. Kunc, The power of commuting with finite sets of words, in: Proc. of STACS 2005, in: LNCS, vol. 3404, Springer, 2005, pp. 569–580], a strong negative answer to this problem was given by showing that even complete co-recursively enumerable centralizers exist for finite languages. Using a combinatorial game approach, we give here an incremental construction of rational languages embedding any recursive computation in their centralizers