Towards parametrizing word equations

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

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

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 35 (2001), p. 331-350 / Harvested from Numdam

Access to full text
Full (PDF)
Full (DJVU)

Résumé
Abstract

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 $u f \approx v f$ , $f \in ℱ$ , chacune en moins de variables que $u \approx v$ , et ensuite en combinant des solutions des $u f \approx v f$ 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.

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 $u f \approx v f$ , $f \in ℱ$ , each involving less variables than $u \approx v$ , and then combine solutions of $u f \approx v f$ 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.

Publié le : 2001-01-01

MR 1880803 | Zbl 1112.68434

Classification: 68R15, 20M05

@article{ITA_2001__35_4_331_0,
     author = {Abdulrab, Habib and Goral\v c\'\i k, P. and Makanin, G. S.},
     title = {Towards parametrizing word equations},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {35},
     year = {2001},
     pages = {331-350},
     mrnumber = {1880803},
     zbl = {1112.68434},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2001__35_4_331_0}
}

Abdulrab, H.; Goralčík, P.; Makanin, G. S. Towards parametrizing word equations. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 35 (2001) pp. 331-350. http://gdmltest.u-ga.fr/item/ITA_2001__35_4_331_0/

Bibliographie

[1] J. Jaffar, Minimal and Complete Word Unification. J. ACM 37 (1990) 47-85. | MR 1072430 | Zbl 0697.68052

[2] Yu.I. Hmelevskiĭ, Equations in free semigroups. Trudy Mat. Inst. Steklova 107 (1971); English Translation in Proc. Steklov Inst. Math. 107 (1971) 1976. | MR 393284 | Zbl 0326.02032

[3] A. Lentin, Équations dans les monoïdes libres. Gautier-Villars, Paris (1972). | MR 333034 | Zbl 0258.20058

[4] M. Lothaire, Combinatorics on Words. Addison-Wesley (1983). | MR 675953 | Zbl 0514.20045

[5] G.S. Makanin, The problem of solvability of equations in a free semigroup. Mat. Sbornik 103 (1977) 147-236 (in Russian); English Translation in Math. USSR Sbornik 32 (1977) 128-198. | MR 470107 | Zbl 0396.20037

[6] G.S. Makanin, On general solution of equations in free semigroups, in Proc. of IWWERT'91, edited by H. Abdulrab and J.P. Pécuchet. Springer, Lecture Notes in Comput. Sci. 677, 1-5. | Zbl 0925.20067

[7] G. Plotkin, Building-in Equational Theories. Machine intelligence 7 (1972) 73-90. | Zbl 0262.68036