Classically, in order to resolve an equation over a free monoid , we reduce it by a suitable family of substitutions to a family of equations , , each involving less variables than , and then combine solutions of into solutions of . 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 . 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 dans le monoïde libre en la réduisant par une famille convenable de substitutions en une famille d’équations , , chacune en moins de variables que , et ensuite en combinant des solutions des pour obtenir des solutions de . 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é à . Nous effectuons une telle paramétrisation dans le cas où les équations premières dans le graphe contiennent au plus trois variables.
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] Minimal and Complete Word Unification. J. ACM 37 (1990) 47-85. | MR | Zbl
,[2] Equations in free semigroups. Trudy Mat. Inst. Steklova 107 (1971); English Translation in Proc. Steklov Inst. Math. 107 (1971) 1976. | MR | Zbl
,[3] Équations dans les monoïdes libres. Gautier-Villars, Paris (1972). | MR | Zbl
,[4] Combinatorics on Words. Addison-Wesley (1983). | MR | Zbl
,[5] 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] 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] Building-in Equational Theories. Machine intelligence 7 (1972) 73-90. | Zbl
,