Équation entre mots

En mathématiques et en informatique théorique, 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. 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 é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 Matiassevitch 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.

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ïde $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 plus naturel 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 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 équation être 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}}$ et ${\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 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 ; en 1999, Plandowski 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. 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, 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.

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.

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.
• Ju. I. Hmelevskii, Equations in free semigroups, American Mathematical Society, Proceedings of the Steklov Institute of Mathematics 107 (1971), 1976 (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
• G. 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.
• G. 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)
• (en) Youri Matiassevitch, Hilbert’s Tenth Problem, Cambridge, Mass., MIT Press, 1993, 288 p. (ISBN 9780262132954)
• Youri Matiassevitch, Le dixième problème de Hilbert : son indécidabilite, Paris, Masson, 1995 (ISBN 2225848351) — Traduction française
• W. 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.

Articles connexes

• Combinatoire des mots