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

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.

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.

Classification: 68R15, 20M05
Keywords: equation, free monoid, parametrization, universal family
@article{ITA_2001__35_4_331_0,
     author = {Abdulrab, H. 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},
     mrnumber = {1880803},
     zbl = {1112.68434},
     language = {en},
     url = {http://archive.numdam.org/item/ITA_2001__35_4_331_0/}
}
TY  - JOUR
AU  - Abdulrab, H.
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
SP  - 331
EP  - 350
VL  - 35
IS  - 4
PB  - EDP-Sciences
UR  - http://archive.numdam.org/item/ITA_2001__35_4_331_0/
LA  - en
ID  - ITA_2001__35_4_331_0
ER  - 
%0 Journal Article
%A Abdulrab, H.
%A Goralčík, P.
%A Makanin, G. S.
%T Towards parametrizing word equations
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2001
%P 331-350
%V 35
%N 4
%I EDP-Sciences
%U http://archive.numdam.org/item/ITA_2001__35_4_331_0/
%G en
%F 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, Volume 35 (2001) no. 4, pp. 331-350. http://archive.numdam.org/item/ITA_2001__35_4_331_0/

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

[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 | Zbl

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

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

[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 | Zbl

[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

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