Accueil🇫🇷Chercher

Conjecture d'Ehrenfeucht

La conjecture d'Ehrenfeucht ou, maintenant qu'elle est démontrée (par Michael H. Albert et John Lawrence[1] et de manière indépendante par Victor S. Guba[2]), 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é 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[3].

Généralisation

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 . 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 :

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[5]. La propriété de compacité s'étend à d'autres monoïdes que les monoïdes libres[6] - [7].

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[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é sur un alphabet 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 , 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

  1. Michael H. Albert et John Lawrence, « A proof of Ehrenfeucht's Conjecture », Theoretical Computer Science, vol. 41,‎ , p. 121-123 (DOI 10.1016/0304-3975(85)90066-0, lire en ligne).
  2. Victor S. Guba, « Equivalence of infinite systems of equations in free groups and semigroups to finite subsystems », Mathematical Notes of the Academy of Sciences of the USSR, vol. 40, no 3,‎ , p. 688–690 (ISSN 0001-4346, DOI 10.1007/BF01142470). — Traduction de Matematicheskie Zametki, Vol. 40, No. 3, p. 321–-24, Septembre, 1986.
  3. Juhani Karhumäki, « The Ehrenfeucht conjecture: a compactness claim for finitely generated free monoids », Theoretical Computer Science, vol. 29, no 3,‎ , p. 285-308 (DOI 10.1016/0304-3975(84)90004-5, lire en ligne)
  4. « Ehrenfeucht conjecture », Encyclopedia of Mathematics, Springer et Société mathématique européenne (consulté le ).
  5. Karel Culik et Juhani Karhumäki, « Systems of equations over a free monoid and Ehrenfeucht's conjecture », Discrete Mathematics, vol. 43, nos 2-3,‎ , p. 139-153 (DOI 10.1016/0012-365X(83)90152-8, lire en ligne).
  6. Tero Harju et Juhani Karhumäki, « Morphisms », dans G. Rozenberg et A. Salomaa (éditeurs), Handbook of Formal Languages, vol. 1, Springer, , p. 438-510.
  7. Tero Harju, Juhani Karhumäki et W. Plandowski, « Independent Systems of Equations », dans M. Lothaire, Algebraic Combinatorics of Words.
  8. Dominique Perrin, « On the solution of Ehrenfeucht's Conjecture », BulL EATCS, no 27,‎ , p. 68-70.
  9. Arto Salomaa, « The Ehrenfeucht Conjecture: A proof for language theorists », BulL EATCS, no 27,‎ , p. 71-82.
  10. John R. Stallings, « Finiteness Properties of Matrix Representations », The Annals of Mathematics, vol. 124, no 2,‎ , p. 337 (DOI 10.2307/1971282, JSTOR 1971282).
  11. Ebbe Thue Poulsen, « The Ehrenfeucht Conjecture: An algebra-framework for its proof », Theoretical Computer Science, vol. 44,‎ , p. 333-339 (DOI 10.1016/0304-3975(86)90126-X, lire en ligne).
  12. Voir par exemple (Perrin 1986).
Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.