Équation entre mots

Modèle:Article principal 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 Modèle:Lang) 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\ge 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 MakaninModèle:, é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.

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

$\left(\begin{array}{cc}1& 0\\ 1& 1\end{array}\right)$ et $\left(\begin{array}{cc}1& 1\\ 0& 1\end{array}\right)$

engendrent une monoïde libre, et de plus ce sont exactement les matrices d’ordre 2 du groupe spécial linéaire $\mathrm{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,\dots ,Y_4$ a une solution en nombres entiers :

$\begin{array}{cc}\left(\begin{array}{cc}1& 0\\ 1& 1\end{array}\right)\cdot \left(\begin{array}{cc}1& 1\\ 0& 1\end{array}\right)\cdot \left(\begin{array}{cc}{X}_1& X_2\\ X_3& X_4\end{array}\right)& =\left(\begin{array}{cc}{Y}_1& Y_2\\ Y_3& Y_4\end{array}\right)\left(\begin{array}{cc}1& 1\\ 0& 1\end{array}\right)\cdot \left(\begin{array}{cc}1& 0\\ 1& 1\end{array}\right)\\ X_1{X}_4-X_2{X}_3& =1\\ Y_1{Y}_4-Y_2{Y}_3& =1\\ X_i\ge 0,Y_i\ge 0& (1\le i\le 4)\end{array}$

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 MakaninModèle:Refm 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\ge 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.

É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\ge 2$ sont des entiers. Dans un article de 1962, 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) : Modèle:Théorème

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 ; Christian Choffrut a donné une preuve dans le « Lothaire » en 1997. Une preuve plus courte, de Tero Harju et Dirk Nowotka, est parue en 2004, et une autre, plus détaillée de Pál Dömösi et Géza Horváth en 2006. Une démonstration complète figure aussi dans le manuel de Jeffrey Shallit.

Extensions et généralisations

Des extensions et généralisations ont été données par la suite. André Lentin en 1965 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

Kenneth I. Appel et Frans M. Djorup é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\le n$. Tero Harju et Dirk Nowotka en 2005 é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. 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. 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 18Modèle:,.

Bibliographie

• Modèle:Chapitre
• Modèle:Chapitre.
• Modèle:Ouvrage Modèle:Commentaire biblio SRL.
• Modèle:Chapitre
• Modèle:Article.
• Modèle:Article — Traduction anglaise de l’annonce du résultat. En russe : Dokl. Akad. Nauk SSSR 233 (1977), no. 2, 287–290.
• Modèle:Article — Article complet, en russe. Traduction anglaise : Math. USSR Sbornik 32 (1977)
• Modèle:Ouvrage
• Modèle:Ouvrage — Traduction française
• Modèle:Article — Version « journal » de la communication de 1999.
• Modèle:Article

Articles connexes

• Combinatoire des mots