# Towards parametrizing word equations

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

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2001)

- Volume: 35, Issue: 4, page 331-350
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topAbdulrab, H., Goralčík, P., and Makanin, G. S.. "Towards parametrizing word equations." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 35.4 (2001): 331-350. <http://eudml.org/doc/92669>.

@article{Abdulrab2001,

abstract = {Classically, in order to resolve an equation $u\approx v$ over a free monoid $X^*$, we reduce it by a suitable family $\mathcal \{F\}$ of substitutions to a family of equations $uf\approx vf$, $f\in \mathcal \{F\}$, each involving less variables than $u\approx v$, and then combine solutions of $uf\approx vf$ into solutions of $u\approx v$. The problem is to get $\mathcal \{F\}$ 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.},

author = {Abdulrab, H., Goralčík, P., Makanin, G. S.},

journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},

keywords = {equation; free monoid; parametrization; universal family},

language = {eng},

number = {4},

pages = {331-350},

publisher = {EDP-Sciences},

title = {Towards parametrizing word equations},

url = {http://eudml.org/doc/92669},

volume = {35},

year = {2001},

}

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

PB - EDP-Sciences

VL - 35

IS - 4

SP - 331

EP - 350

AB - Classically, in order to resolve an equation $u\approx v$ over a free monoid $X^*$, we reduce it by a suitable family $\mathcal {F}$ of substitutions to a family of equations $uf\approx vf$, $f\in \mathcal {F}$, each involving less variables than $u\approx v$, and then combine solutions of $uf\approx vf$ into solutions of $u\approx v$. The problem is to get $\mathcal {F}$ 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.

LA - eng

KW - equation; free monoid; parametrization; universal family

UR - http://eudml.org/doc/92669

ER -

## References

top- [1] J. Jaffar, Minimal and Complete Word Unification. J. ACM 37 (1990) 47-85. Zbl0697.68052MR1072430
- [2] Yu.I. Hmelevskiĭ, Equations in free semigroups. Trudy Mat. Inst. Steklova 107 (1971); English Translation in Proc. Steklov Inst. Math. 107 (1971) 1976. Zbl0326.02032MR393284
- [3] A. Lentin, Équations dans les monoïdes libres. Gautier-Villars, Paris (1972). Zbl0258.20058MR333034
- [4] M. Lothaire, Combinatorics on Words. Addison-Wesley (1983). Zbl0514.20045MR675953
- [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. Zbl0396.20037MR470107
- [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. Zbl0925.20067
- [7] G. Plotkin, Building-in Equational Theories. Machine intelligence 7 (1972) 73-90. Zbl0262.68036