Conjecture d'Ehrenfeucht

La conjecture d'Ehrenfeucht ou, maintenant qu'elle est démontrée (par Michael H. Albert et John Lawrence et de manière indépendante par Victor S. Guba), le théorème de compacité est un énoncé concernant la combinatoire du monoïde libre ; c'est à la fois un théorème d'informatique théorique et un théorème d'algèbre.

Énoncé

L'énoncé est le suivant :

Conjecture d'Ehrenfeucht, théorème de compacité — Tout sous-ensemble S d'un monoïde libre finiment engendré possède un sous-ensemble fini T avec la propriété que deux morphismes qui coïncident sur T coïncident sur S.

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 :

Autre formulation — Tout sous-ensemble d'un monoïde finiment engendré possède un ensemble de test fini.

Historique

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é $h^{i}(w)=g^{i}(w)$ pour tout $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.

Généralisation

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

Conjecture d'Ehrenfeucht sur les équations — Tout système d'équations sur un monoïde libre ayant un nombre fini de variables est équivalent un de ses sous-systèmes finis.

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

Démonstrations

La forme en équations de la conjecture a été utilisée de manière indépendante par Michael H. Albert et John Lawrence et par Victor S. Guba 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. John R. Stallings 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.

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

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

L'injectivité vient du fait qu'une matrice

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

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

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

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

où les $a_{ij}$ sont des inconnues commutatives et en écrivant les équations du système $\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 $\phi (S)$, donc aussi à un sous-système fini de $S$.