Conjecture d'Ehrenfeucht

L'énoncé est le suivant :

Un ensemble T avec la propriété de l’énoncé est appelé un ensemble de test (en anglais test set) pour S. L'énoncé peut donc se formuler en :

La conjecture d'Ehrenfeucht a été formulée par Andrzej Ehrenfeucht dans les années 1970. Elle trouve son origine dans les recherches concernant le problème de décidabilité de l'équivalence des D0L-systèmes, un cas particulier des L-systèmes introduits par le biologiste Aristid Lindenmayer en vue de formaliser des phénomènes de croissance (ici D0L est une abréviation pour « deterministe zéro-interaction Lindenmayer »). Le problème est de décider, pour deux morphismes h et g sur un monoïde finiment engendré et un mot w, s'il y a égalité ${\displaystyle h^{i}(w)=g^{i}(w)}$ pour tout ${\displaystyle i>0}$. De nombreux travaux ont précédé la preuve de la conjecture, sans aboutir à la démonstration. Un historique a été donné par Karhumäki en 1984[3].

La conjecture d'Ehrenfeucht ci-dessus peut être vue comme une propriété de compacité de monoïdes libres[4]. On peut aussi formuler la conjecture pour des systèmes d'équations. Pour cela, on considère un alphabet ${\displaystyle A}$. Un couple ${\displaystyle (u,v)}$ de mots sur ${\displaystyle A}$ est appelé une équation sur ${\displaystyle A}$. Un système d'équations est simplement un ensemble ${\displaystyle S}$ d'équations sur ${\displaystyle A}$. Une solution du système sur un alphabet ${\displaystyle \Sigma }$ est un morphisme ${\displaystyle h}$ de ${\displaystyle A^{*}}$ dans ${\displaystyle \Sigma ^{*}}$ tel que ${\displaystyle h(u)=h(v)}$ pour tout ${\displaystyle (u,v)}$ de ${\displaystyle S}$. Deux systèmes ${\displaystyle S_{1}}$ et ${\displaystyle S_{2}}$ sont équivalents s'ils ont même ensemble de solutions. La généralisation de la conjecture est :

Les deux énoncés de la conjecture d'Ehrenfeucht sont en fait équivalents[5]. La propriété de compacité s'étend à d'autres monoïdes que les monoïdes libres[6] - [7].

La forme en équations de la conjecture a été utilisée de manière indépendante par Michael H. Albert et John Lawrence[1] et par Victor S. Guba[2] pour démontrer la conjecture. Les deux démonstrations de la conjecture d'Ehrenfeucht en font une conséquence presque directe du théorème de la base de Hilbert. Les deux preuves utilisent le fait qu'un monoïde finiment engendré peut être plongé dans une autre structure algébrique, à savoir un groupe métabélien (en) pour Albert et Lawrence, et dans l'anneau de matrices d'ordre 2 à coefficients entiers pour Guba.

Les démonstrations originales ont été commentées et développées, notamment par Dominique Perrin et Arto Salomaa[8] - [9]. John R. Stallings[10] décrit également la preuve comme point de départ de développement plus généraux. Un autre preuve est donnée par Poulsen[11].

Le plongement d'un monoïde libre finiment engendré ${\displaystyle A^{*}}$ sur un alphabet ${\displaystyle A=\{a_{1},\ldots ,a_{k}\}}$ dans le monoïde des matrices carrées d'ordre 2 se fait en deux étapes[12] : d'abord, on injecte le monoïde dans le monoïde libre engendré par deux lettres ${\displaystyle \{a,b\}^{*}}$, en associant à chaque lettre ${\displaystyle a_{i}}$le mot ${\displaystyle ab^{i}}$, puis on représente les lettres ${\displaystyle a}$ et ${\displaystyle b}$ par les matrices

${\displaystyle a\to {\begin{bmatrix}1&1\\0&1\end{bmatrix}}}$ et ${\displaystyle b\to {\begin{bmatrix}1&0\\1&1\end{bmatrix}}}$

L'injectivité vient du fait qu'une matrice

${\displaystyle m={\begin{bmatrix}u&v\\w&t\end{bmatrix}}}$

à coefficients non négatifs représente un mot si et seulement si ${\displaystyle ut-vw=1}$. Si ${\displaystyle m\neq 1}$, le mot représenté se termine par la lettre ${\displaystyle a}$ si ${\displaystyle u\leq v}$ et par la lettre ${\displaystyle b}$ si ${\displaystyle u>v}$.

Un système d'équations ${\displaystyle S=\{(u_{i},v_{i})\mid i\in I\}}$ de mots est transformé en un système d'équations ${\displaystyle \phi (S)}$ algébriques en remplaçant chaque lettre ${\displaystyle a}$ par la matrice

${\displaystyle \phi (a)={\begin{bmatrix}a_{11}&a_{12}\\a_{21}&a_{22}\end{bmatrix}}}$

où les ${\displaystyle a_{ij}}$ sont des inconnues commutatives et en écrivant les équations du système ${\displaystyle \phi (S)}$ composante par composante. Par le théorème de la base de Hilbert, le système est équivalent à un sous-système fini de ${\displaystyle \phi (S)}$, donc aussi à un sous-système fini de ${\displaystyle S}$.