Towards parametrizing word equations

¹ 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 ≈ v over a free monoid X*, we reduce it by a suitable family of substitutions to a family of equations uf ≈ vf, , each involving less variables than u ≈ v, and then combine solutions of uf ≈ vf into solutions of u ≈ 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 ≈ 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 ≈ v dans le monoïde libre X* en la réduisant par une famille convenable de substitutions en une famille d'équations uf ≈ vf, , chacune en moins de variables que u ≈ v, et ensuite en combinant des solutions des uf ≈ vf pour obtenir des solutions de u ≈ 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 ≈ v. Nous effectuons une telle paramétrisation dans le cas où les équations premières dans le graphe contiennent au plus trois variables.