Équation entre mots

En mathématiques et en informatique théorique, et tout particulièrement en combinatoire des mots, une équation de mots ou une équation entre mots (en anglais word equation) est un couple $(U,V)$ de mots, usuellement écrit sous la forme d'une équation

U=V

Ici, $U$ et $V$ sont des mots composés de lettres qui sont des constantes ou des variables. Les constantes sont écrites en minuscules et les variables en majuscules, ou aussi fréquemment en minuscules d'« inconnues », comme $x,y,z$ etc. Par exemple, l'équation

abXbX=XbXba

contient quatre occurrences de la variable $X$ , et des constantes $a$ et $b$ . Une solution d'une équation est un ensemble de mots sans variables, un pour chaque variable, tel que la substitution des mots aux variables rend les deux composantes de l’équation identiques. Par exemple, pour $X=a$ (et plus généralement pour $X=(ab)^{k}a$ avec $k\geq 0$ , les deux côtés de l'équation précédentes deviennent égaux, à $ababa$ (et plus généralement à $(ab)^{2k+2}a$ ).

On considère le problème qui consiste à trouver une solution à équation de mots, ou plus généralement un ensemble d'équations de mots. Un célèbre théorème de Makanin[1] - [2] établit que ce problème est décidable. En cela, les équations de mots se distinguent des équations diophantiennes pour lesquels l'existence de solutions est indécidable par le théorème de Matiiassevitch résolvant le dixième problème de Hilbert.

Un problème lié est la description de toutes les solutions d'une équation donnée, sous forme paramétrée en général. La première étude systématique dans cette direction est faite par Hmelevskii[3].

Formulation

Une équation est un couple de mots $(U,V)$ sur un alphabet composé de constantes et de variables. Une solution est un morphisme de monoïdes $f$ qui associe à chaque variable X un mot f(X), et qui laisse inchangé les constantes, et qui vérifie

f(U)=f(V)

Ainsi, pour l'exemple de l'équation $(abXbX,XbXba)$ donné dans l'introduction, le morphisme défini par $f(X)=a$ est une solution. On écrit aussi parfois $S$ pour ce morphisme, la lettre choisie devant rappeler le mot « solution », ou plus simplement $X=a$ .

Une équation sans constante est une équation où ne figurent que des variables, comme l'équation $(XY,YX)$ .

Il est d'usage d'identifier les variables (notées par des majuscules) avec les solutions (notées par des lettres minuscules). Ainsi, au lieu de parler de l'équation $(XY,YX)$ , on parle de mots $x,y$ vérifiant $xy=yx$ . Il est plus naturel aussi d'écrire $U=V$ au lieu de $(U,V)$ .

Une solution d'une équation est dite cyclique (ou périodique) si tous ses mots sont puissances d'un même mot. Par exemple, les solutions de l'équation

XY=YX

sont toutes cycliques.

Une équation est dite quadratique si toute variable apparaît au plus deux fois. Voici un exemple[2] d’une équation quadratique en 4 variables $X,Y,Z,T$ :

XaTZaT=YZbXaabY

Une solution est donnée par :

X=abb,Y=ab,Z=ba,T=bab

et en effet on a :

(abb)a(bab)(ba)a(bab)=abbababbaabab=(ab)(ba)b(abb)aab(ab)

Équations entre mots et équations diophantiennes

Les équations entre mots sont liées aux équations diophantiennes. On peut coder simplement une équation entre mots en équation diophantienne, en se basant sur le fait que les matrices

{\begin{pmatrix}1&0\\1&1\end{pmatrix}}

{\begin{pmatrix}1&1\\0&1\end{pmatrix}}

engendrent une monoïde libre, et de plus ce sont exactement les matrices d’ordre 2 du groupe spécial linéaire $\operatorname {SL} (2,\mathbb {Z} )$ à coefficients entiers naturels.

Ainsi, l’équation

abX=Yba

possède une solution si et seulement si le système suivant d’équations diophantiennes à 8 inconnues $X_{1},\ldots ,Y_{4}$ a une solution en nombres entiers :

{\begin{aligned}{\begin{pmatrix}1&0\\1&1\end{pmatrix}}\cdot {\begin{pmatrix}1&1\\0&1\end{pmatrix}}\cdot {\begin{pmatrix}X_{1}&X_{2}\\X_{3}&X_{4}\end{pmatrix}}&={\begin{pmatrix}Y_{1}&Y_{2}\\Y_{3}&Y_{4}\end{pmatrix}}{\begin{pmatrix}1&1\\0&1\end{pmatrix}}\cdot {\begin{pmatrix}1&0\\1&1\end{pmatrix}}\\X_{1}X_{4}-X_{2}X_{3}&=1\\Y_{1}Y_{4}-Y_{2}Y_{3}&=1\\X_{i}\geq 0,Y_{i}\geq 0&\quad (1\leq i\leq 4)\end{aligned}}

Mais alors que le dixième problème de Hilbert, à savoir déterminer si une équation diophantienne a une solution, est indécidable, trouver une solution d’une équation entre mots est décidable par le théorème de Makanin.

Complexité

Le théorème de Makanin[1] - [2] dit que le problème de déterminer si une équation a une solution décidable. La complexité de l'algorithme de décision a fait l'objet de nombreuses recherches[4] ; en 1999, Plandowski[5] a montré que le problème est dans la classe de complexité nommée PSPACE.

Une nouvelle approche du problème est présentée par Artur Jeż en 2013[6]. Il utilise une méthode de modification locale de variables qui consiste d'une part à remplacer une variable $X$ par $aX$ ou $Xa$ selon le cas, et d'autre part à remplacer une paire de lettres apparaissant dans l'équation par une nouvelle lettre. Avec cette technique, il obtient un algorithme non déterministe en espace $O(n\log n)$ et en temps polynomial en $N$ et $n$ , où $n$ est la longueur de l'équation et $N$ est la taille de la solution la plus courte de l'équation. Cette taille $N$ est elle-même doublement exponentielle en $n$ .

Exemples d'équations sans constantes

Dans ces exemples, on ne considère que des solutions composées de mots non vides. Les équations les plus simples et sans constantes ont souvent des solutions assez facile à décrire.

Équations en deux variables

Pour deux variables, on a le résultat général :

Les solutions d'une équation sans constantes en deux variables sont toutes cycliques

On peut être plus précis : Pour une équation sans constantes

U=V

où $U$ contient $n$ occurrences de $X$ et $m$ occurrences de $Y$ et où $V$ contient $p$ occurrences de $X$ et $q$ occurrences de $Y$ , les solutions sont toutes de la forme $X=t^{i},Y=t^{j}$ , pour un mot $t$ et des entiers $i,j$ avec $ni+mj=pi+qj$ .

Équations en trois variables

Le cas des équations en trois variables est plus complexe. Un premier exemple est l'équation

XZ=ZY

Les solutions de cette équation sont de la forme $X=pq,Y=qpZ=(pq)^{n}p$ pour des mots $p,q$ et un entier $n\geq 0$ . Les mots solutions pour $X$ et $Y$ sont donc des mots conjugués.

Les solutions de l'équation

XYZ=ZYX

sont de la forme $X=(pq)^{i}p,Y=(q(pq)^{j},Z=(pq)^{k}p$ .

Les solutions de l'équatio $XYZ=ZXY$ sont de la forme $X=(pq)^{i},Y=q(pq)^{j},Z=(pq)^{k}$ .

Un théorème général, démontré par Hmelevskii[3], est le suivant :

Les solutions d’une équation sans constantes en trois variables sont finiment paramétrisables, c’est-à- dire peuvent être exprimées par une collection finie de formules contenant des mots et des paramètres numériques entiers.

Les expressions pour les équations ci-dessus en sont des exemples. La démonstration originale du théorème a été considérablement simplifiée depuis[7].

La taille de la représentation est bornée par une fonction qui est exponentielle en la taille de l’équation. De plus, la taille de la plus petite solution non triviale de l’équation, si elle existe, est elle-même exponentielle, et le problème de l'existence peut être résolu en temps non déterministe exponentiel[7].

Équation de Lyndon et Schützenberger

L'équation dite de Lyndon et Schützenberger est l'équation en trois variables

x^{n}=y^{m}z^{p}

entre mots $x,y,z$ et où $n,m,p\geq 2$ sont des entiers. Dans un article de 1962[8], Roger C. Lyndon et Marcel-Paul Schützenberger résolvent cette équation dans le cadre du groupe libre. Ils montrent que si $x,y,z$ sont solutions de cette équation, ils sont puissances d'un même élément. Ils ramènent l'étude dans le groupe libre à l’étude de deux équations dans le monoïde libre faisant intervenir des conjugués de mots.

Le même résultat vaut dans le monoïde libre (ou plutôt dans le demi-groupe libre, c'est-à-dire le monoïde libre privé du mot vide) :

Théorème de Lyndon-Schützenberger — L'équation $x^{n}=y^{m}z^{p}$ dans le demi-groupe libre n'a que des solutions cycliques, c'est-à-dire qui sont puissances d'un même mot.

Plusieurs démonstrations directes de ce théorème ont été données. Historiquement la première, après celle des auteurs, est de Danny D. Chu et Hsiang-Sheng Town[9] ; Christian Choffrut a donné une preuve dans le « Lothaire » en 1997[10]. Une preuve plus courte, de Tero Harju et Dirk Nowotka[11], est parue en 2004, et une autre, plus détaillée de Pál Dömösi et Géza Horváth[12] en 2006. Une démonstration complète figure aussi dans le manuel de Jeffrey Shallit[13].

Extensions et généralisations

Des extensions et généralisations ont été données par la suite. André Lentin en 1965[14] considère l’équation

x^{m}=y^{n}z^{p}t^{q}

en 4 variables, et il démontre, sous réserve que les exposants sont au moins égal à 3, que dans toute solution, $x$ et l'un des mots $y,z,t$ sont puissances d'un même mot. Une autre extension est de Barbin-Le Rest et Le Rest[15]

Kenneth I. Appel et Frans M. Djorup[16] étudient l'équation

z_{1}^{n}z_{2}^{n}\cdots z_{k}^{n}=y^{n}

où les variables apparaissent avec le même exposant ; ils prouvent notamment que les solutions sont toutes puissances d'un même mot dans le cas où $k\leq n$ . Tero Harju et Dirk Nowotka en 2005[17] étudient l’équation plus générale

x^{k}=z_{1}^{k_{1}}z_{2}^{k_{2}}\cdots z_{n}^{k_{n}}

Une variante de ces équations est considérée par Aleksi Saarela[18]. Ce sont les équations de la forme

x^{k}u=u_{1}x_{1}^{k}\cdots u_{n}x_{n}^{k}

évaluées pour plusieurs valeurs de l'exposant $k$ . Il montre que si l'équation est vérifiée pour trois valeurs positives de $k$ , alors elle vaut pour toutes les valeurs de $k$ . En particulier, si

x^{k}=x_{1}^{k}\cdots x_{n}^{k}

pour trois valeurs de $k$ , alors $x$ et les $x_{i}$ sont puissances d'un même mot. Une extension à des monoïdes libres équipés d'un anti-isomorphisme involutif est donnée par Manea et. al[19]. Un tel morphisme est une bijection $f$ d'une monoïde libre sur lui-même qui est involutif ( $f(f(x))=x$ pour tout $x$ ) et une anti-morphisme ( $f(xy)=f(y)f(x)$ pour tout $x,y$ ).

Systèmes d'équations

Un système d'équations est un ensemble d'équations. Un système est dit indépendant s'il n'est équivalent à aucun de ses sous-systèmes propres. Le théorème de compacité d'Ehrenfeucht affirme que tout système infini est équivalent à un sous-système fini, et par conséquent un système indépendant ne peut pas être infini.

La taille maximale d'un système indépendant d'équations de mots sans constante est facile à déterminer dans le cas d'une et deux variables, mais les autres cas restent ouverts, même le cas de trois variables, où la réponse conjecturée est trois. Il a été démontré que la taille maximale d'un système indépendant d'équations à trois variables est d'au plus 18[20] - [21].

Notes et références

Makanin 1977.
Diekert 2002.
Hmelevskii 1976.
Diekert 2015.
Plandowski 2004.
Jeż 2013.
Aleksi Saarela, « On the Complexity of Hmelevskii’s Theorem and Satisfiability of Three Unknown Equations », dans Volker Diekert et Dirk Nowotka (éditeurs), Developments in Language Theory (Proceedings de DLT 2009, Stuttgart), Springer Verlag, coll. « Lecture Notes in Computer Science » (n^o 5583), 2009 (ISBN 978-3-642-02736-9, DOI 10.1007/978-3-642-02737-6_36), p. 443-453.
(en) Roger C. Lyndon et Marcel-Paul Schützenberger, « The equation $a^{M}=b^{N}c^{P}$ in a free group », The Michigan Mathematical Journal, vol. 9, n^o 4,‎ 1962, p. 289–298 (DOI 10.1307/mmj/1028998766, lire en ligne).
(en) Danny D. Chu et Hsiang-Sheng Town, « Another proof on a theorem of Lyndon and Schützenberger in a free monoid », Soochow J. Math., vol. 4,‎ 1978, p. 143-146 (lire en ligne).
Lothaire, Combinatorics on Words, Cambridge University Press, 1997, Section 9.2 : A Classical Equation: $(x^{n}y^{m},z^{p})$ .
(en) Tero Harju et Dirk Nowotka, « The equation $x^{i}=y^{j}z^{k}$ in a free semigroup », Semigroup Forum, vol. 68, n^o 3,‎ 2004, p. 488-490 (MR 2050904).
(en) Pál Dömösi et Géza Horváth, « Alternative proof of the Lyndon–Schützenberger Theorem », Theoretical Computer Science, vol. 366, n^o 3,‎ 2006, p. 194–198 (ISSN 0304-3975, DOI 10.1016/j.tcs.2006.08.023).
(en) Jeffrey Shallit, A Second Course in Formal Languages and Automata Theory, Cambridge University Press, 2009, 240 p. (ISBN 978-0-521-86572-2 et 0521865727), Section 2.3 The theorems of Lyndon–Schützenberger.
(en) André Lentin, « Sur l'équation $a^{M}=b^{N}c^{P}d^{Q}$ dans un monoïde libre », C. R. Math. Acad. Sci. Paris, vol. 260, n^o 4,‎ 1965, p. 3242–3244 (MR 0176949, lire en ligne).
Evelyne Barbin-Le Rest et Michel Le Rest, « Sur la combinatoire des codes à deux mots », Theoretical Computer Science, vol. 41,‎ 1985, p. 61–80 (DOI 10.1016/0304-3975(85)90060-X).
(en) Kenneth Ira Appel et Frans Martin Djorup, « On the equation $z_{1}^{n}z_{2}^{n}\cdots z_{k}^{n}=y^{n}$ in a free semigroup », Trans. Amer. Math. Soc., vol. 134,‎ 1968, p. 461–470.
(en) Tero Harju et Dirk Nowotka, « On the equation $x^{k}=z_{1}^{k_{1}}z_{2}^{k_{2}}\cdots z_{n}^{k_{n}}$ in a free semigroup », Theoret. Comput. Sci., vol. 330, n^o 1,‎ 2005, p. 117–121.
Aleksi Saarela, « Word equations with kth powers of variables », Journal of Combinatorial Theory, Series A, vol. 165,‎ 2019, p. 15–31 (DOI 10.1016/j.jcta.2019.01.004).
(en) Florin Manea, Mike Müller, Dirk Nowotka et Shinnosuke Seki, « The extended equation of Lyndon and Schützenberger », Journal of Computer and System Sciences, vol. 85,‎ 2017, p. 132–167 (DOI 10.1016/j.jcss.2016.11.003).
Aleksi Saarela, « Independent Systems of Word Equations: From Ehrenfeucht to Eighteen », Lecture Notes in Computer Science, n^o 11682,‎ 2019, p. 60–67 (ISSN 0302-9743, DOI 10.1007/978-3-030-28796-2_4)
Dirk Nowotka et Aleksi Saarela, « An Optimal Bound on the Solution Sets of One-Variable Word Equations and its Consequences », dans 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), coll. « Leibniz International Proceedings in Informatics (LIPIcs) » (n^o 107), 2018, 136:1-136:13 (DOI 10.4230/LIPIcs.ICALP.2018.136, lire en ligne).

Bibliographie

Volker Diekert, « More than 1700 years of word equations », dans Conference on Algebraic Informatics, Springer, coll. « Lecture Notes in Computer Science » (n^o 9270), 2015 (ISBN 978-3-319-23020-7, DOI 10.1007/978-3-319-23021-4_2, arXiv 1507.03215), p. 22-28
Volker Diekert, chap. 12 « Makanin's Algorithm », dans M. Lothaire, Algebraic Combinatorics on Words, Cambridge University Press, coll. « Encyclopedia of Mathematics and its Applications » (n^o 90), 2002, p. 387–442.
Youri I. Hmelevskii, Equations in free semigroups, American Mathematical Society, Proceedings of the Steklov Institute of Mathematics 107 (1971), 1976, 270 p. (ISBN 978-0-8218-3007-9, MR 0393284, zbMATH 0326.02032, présentation en ligne) — Traduit de l’original russe, paru en 1971, par G. A. Kandall.
Artur Jeż, « Recompression: a simple and powerful technique for word equations », dans Natacha Portier et Thomas Wilke (éditeurs), 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013), coll. « Leibniz International Proceedings in Informatics (LIPIcs) », 2013 (ISBN 978-3-939897-50-7, DOI 10.4230/LIPIcs.STACS.2013.233, lire en ligne), p. 233-244
Artur Jeż, « Word equations in non-deterministic linear space », Journal of Computer and System Sciences, vol. 123,‎ février 2022, p. 122-142 (arXiv 1702.00736).
Gennadiĭ S. Makanin, « The problem of solvability of equations in a free semigroup », Soviet Math. Dokl., vol. 18, n^o 2,‎ 1977, p. 330-334 — Traduction anglaise de l’annonce du résultat. En russe : Dokl. Akad. Nauk SSSR 233 (1977), no. 2, 287–290.
Gennadiĭ S. Makanin, « The problem of solvability of equations in a free semigroup », Math. Sbornik (N.S.), vol. 103, n^o 2,‎ 1977, p. 147-236, 319 (MR 0470107) — Article complet, en russe. Traduction anglaise : Math. USSR Sbornik 32 (1977)
Yuri V. Matiyassevich, Hilbert’s Tenth Problem, Cambridge, Mass., MIT Press, 1993, 288 p. (ISBN 978-0-262-13295-4, lire en ligne)
Youri Matiiassevitch, Le dixième problème de Hilbert : son indécidabilite, Paris, Masson, 1995, 307 p. (ISBN 2-225-84835-1) — Traduction française
Wojciech Plandowski, « Satisfiability of word equations with constants is in PSPACE. », Journal of the Association for Computing Machinery, vol. 51,‎ 2004, p. 483–496 — Version « journal » de la communication de 1999.
Wojciech Plandowski, « On PSPACE generation of a solution set of a word equation and its applications », Theoretical Computer Science, vol. 792,‎ 2019, p. 20–61 (DOI 10.1016/j.tcs.2018.10.023)