Centraliseur
En théorie des langages, le centraliseur d'un langage est le plus grand langage solution de l'équation , où désigne l'opération de concaténation.
Ceci signifie que, pour tout mot du centraliseur de , et pour tout mot de , la concaténation admet une décomposition en un mot de suivi d'un mot du centraliseur de - et réciproquement pour .
Problème de Conway
En 1971, Conway conjectura que les centraliseurs de langages réguliers étaient également réguliers. La résolution du problème fut effectuée en 2005 et publiée en 2007 par Michal Kunc dans l'article cité en bibliographie; il montre que contrairement à la conjecture, il existe des langages finis dont le centraliseur n'est même pas récursivement énumérable: il n'y a donc aucun lien de régularité entre un langage et son centraliseur.
Ébauche de la preuve
La preuve de Kunc consiste en un encodage complexe et difficile. L'idée est de considérer une machine de Minsky, et de créer un langage dont le centraliseur ne contienne que les encodages des configurations non accessibles par la machine. Par équivalence des machines de Minsky et des machines de Turing, il existe donc des machines calculant des langages non-décidables. En utilisant une telle machine dans l'encodage, on obtient un centraliseur non récursivement énumérable.
La dynamique des machines de Minsky est restituée à l'aide de successions d'opérations de commutation, qui permettent de modifier de manière bien contrôlée les configurations de la machine, et le centraliseur obtenu est tel que les encodages des configurations correspondant à la même composante connexe du graphe de configurations de la machine sont toutes dans le centraliseur, ou aucune n'y est. On s'arrange alors pour exclure, par une astuce dans la définition du langage, les configurations initiales du centraliseur, tout en permettant à toute autre configuration de s'y trouver. Finalement, ceci exclut toutes les configurations accessibles et inclut toutes les configurations inaccessibles, donc en particulier celles correspondant à l'acceptation des mots du complémentaire du langage de la machine.
Bibliographie
- Michal Kunc : The Power of Commuting with Finite Sets of Words. Theory Comput. Syst. 40(4): 521-551 (2007)