Towards parametrizing word equations

Abdulrab, H. ; Goralčík, P. ; Makanin, G. S.

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 35 (2001) no. 4, pp. 331-350

Abstract (VO)

Classically, in order to resolve an equation $u\approx v$ over a free monoid $X^{*}$, we reduce it by a suitable family $ℱ$ of substitutions to a family of equations $uf\approx vf$, $f\in ℱ$, each involving less variables than $u\approx v$, and then combine solutions of $uf\approx vf$ into solutions of $u\approx v$. The problem is to get $ℱ$ in a handy parametrized form. The method we propose consists in parametrizing the path traces in the so called graph of prime equations associated to $u\approx v$. We carry out such a parametrization in the case the prime equations in the graph involve at most three variables.

Résumé

De façon classique, on résout une équation $u\approx v$ dans le monoïde libre $X^{*}$ en la réduisant par une famille convenable $ℱ$ de substitutions en une famille d’équations $uf\approx vf$, $f\in ℱ$, chacune en moins de variables que $u\approx v$, et ensuite en combinant des solutions des $uf\approx vf$ pour obtenir des solutions de $u\approx v$. Le problème qui se pose alors est d’obtenir $ℱ$ sous une forme commode paramétrisée. La méthode que nous proposons est basée sur la paramétrisation des traces des chemins dans le graphe des équations premières associé à $u\approx v$. Nous effectuons une telle paramétrisation dans le cas où les équations premières dans le graphe contiennent au plus trois variables.

Détail

Classification : 68R15, 20M05
Keywords: equation, free monoid, parametrization, universal family