RAIRO - Theoretical Informatics and Applications (RAIRO: ITA)

DOI: 10.1051/ita:2001123

Theoret. Informatics Appl. 35, 331-350 (2001)

Towards parametrizing word equations

H. Abdulrab¹, P. Goralcík² and G.S. Makanin³

¹ LIR/INSA de Rouen, BP. 08, 76131 Mont-Saint-Aignan Cedex, France.
² LIFAR, Université de Rouen, place E. Blondel, 76821 Mont-Saint-Aignan Cedex, France.
³ Steklov Mathematical Institute, Vavilova 42, 117966 Moscow GSP-1, Russia.

(Received May, 2000. Accepted October, 2001.)

Abstract
Classically, in order to resolve an equation $u\approx v$ over a free monoid X^*, we reduce it by a suitable family $\cal F$ of substitutions to a family of equations $uf\approx vf$ , $f\in\cal F$ , 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 $\cal F$ 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 $\cal F$ de substitutions en une famille d'équations $uf\approx vf$ , $f\in\cal F$ , 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 $\cal F$ 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.

AMS Subject: 68R15, 20M05.

Key words: Equation -- free monoid -- parametrization -- universal family.

© EDP Sciences 2001

What is OpenURL?