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 :

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 :

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é pour tout . 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 . Un couple de mots sur est appelé une équation sur . Un système d'équations est simplement un ensemble d'équations sur . Une solution du système sur un alphabet est un morphisme de dans tel que pour tout de . Deux systèmes et 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.. 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. — Traduction de Matematicheskie Zametki, Vol. 40, No. 3, p. 321–-24, Septembre, 1986. 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 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. Une autre preuve est donnée par Poulsen..

Le plongement d'un monoïde libre finiment engendré sur un alphabet dans le monoïde des matrices carrées d'ordre 2 se fait en deux étapesVoir par exemple (Perrin 1986). : d'abord, on injecte le monoïde dans le monoïde libre engendré par deux lettres , en associant à chaque lettre le mot , puis on représente les lettres et par les matrices

et

L'injectivité vient du fait qu'une matrice

à coefficients non négatifs représente un mot si et seulement si . Si , le mot représenté se termine par la lettre si et par la lettre si .

Un système d'équations de mots est transformé en un système d'équations algébriques en remplaçant chaque lettre par la matrice

où les sont des inconnues commutatives et en écrivant les équations du système composante par composante. Par le théorème de la base de Hilbert, le système est équivalent à un sous-système fini de , donc aussi à un sous-système fini de .

Notes et références

Catégorie:Combinatoire Catégorie:Informatique théorique Ehrenfeucht