Towards parametrizing word equations

Issue		RAIRO-Theor. Inf. Appl. Volume 35, Number 4, July-August 2001


Page(s)		331 - 350
DOI		10.1051/ita:2001123

DOI: 10.1051/ita:2001123

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

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?

The OpenURL standard is a protocol for transmission of metadata describing the resource that you wish to access. An OpenURL link contains article metadata and directs it to the OpenURL server of your choice. The OpenURL server can provide access to the resource and also offer complementary services (specific search engine, export of references...). The OpenURL link can be generated by different means.

If your librarian has set up your subscription with an OpenURL resolver, OpenURL links appear automatically on the abstract pages.
You can define your own OpenURL resolver with your EDPS Account. In this case your choice will be given priority over that of your library.
You can use an add-on for your browser (Firefox or I.E.) to display OpenURL links on a page (see http://www.openly.com/openurlref/). You should disable this module if you wish to use the OpenURL server that you or your library have defined.