Playing with Conway's Problem

Emmanuel Jeandel (1, 2) , Nicolas Ollinger (2)

1 LIP - Laboratoire de l'Informatique du Parallélisme
2 LIF - Laboratoire d'informatique Fondamentale de Marseille - UMR 6166

The centralizer of a language is the maximal language commuting with it. The question, raised by Conway in 1971, whether the centralizer of a rational language is always rational, recently received a lot of attention. In Kunc 2005, 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.

Mots clés: Conway's problem; commutation; centralizer; game theory

Domaines: Autre [cs.OH]

Emmanuel Jeandel, Nicolas Ollinger. Playing with Conway's Problem. 2008. ⟨hal-00013788v2⟩