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

De façon classique, on résout une équation uv dans le monoïde libre X * en la réduisant par une famille convenable de substitutions en une famille d’équations ufvf, f, chacune en moins de variables que uv, et ensuite en combinant des solutions des ufvf pour obtenir des solutions de uv. 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é à uv. 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 uv over a free monoid X * , we reduce it by a suitable family of substitutions to a family of equations ufvf, f, each involving less variables than uv, and then combine solutions of ufvf into solutions of uv. 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 uv. We carry out such a parametrization in the case the prime equations in the graph involve at most three variables.

Classification : 68R15,  20M05
Mots clés : equation, free monoid, parametrization, universal family
@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},
     pages = {331--350},
     publisher = {EDP-Sciences},
     volume = {35},
     number = {4},
     year = {2001},
     zbl = {1112.68434},
     mrnumber = {1880803},
     language = {en},
     url = {http://www.numdam.org/item/ITA_2001__35_4_331_0/}
}
TY  - JOUR
AU  - Abdulrab, Habib
AU  - Goralčík, P.
AU  - Makanin, G. S.
TI  - Towards parametrizing word equations
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2001
DA  - 2001///
SP  - 331
EP  - 350
VL  - 35
IS  - 4
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/ITA_2001__35_4_331_0/
UR  - https://zbmath.org/?q=an%3A1112.68434
UR  - https://www.ams.org/mathscinet-getitem?mr=1880803
LA  - en
ID  - ITA_2001__35_4_331_0
ER  - 
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) no. 4, pp. 331-350. http://www.numdam.org/item/ITA_2001__35_4_331_0/

[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