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) no. 4, pp. 331-350.

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.

MR Zbl

Classification : 68R15, 20M05
Mots clés : 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, Tome 35 (2001) no. 4, pp. 331-350. http://archive.numdam.org/item/ITA_2001__35_4_331_0/

Bibliographie
Cité par

[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