# Towards parametrizing word equations

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

RAIRO - Theoretical Informatics and Applications (2010)

- 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 35.4 (2010): 331-350. <http://eudml.org/doc/222084>.

@article{Abdulrab2010,

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

keywords = {Equation; free monoid; parametrization; universal family.; universal family},

language = {eng},

month = {3},

number = {4},

pages = {331-350},

publisher = {EDP Sciences},

title = {Towards parametrizing word equations},

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

volume = {35},

year = {2010},

}

TY - JOUR

AU - Abdulrab, H.

AU - Goralčík, P.

AU - Makanin, G. S.

TI - Towards parametrizing word equations

JO - RAIRO - Theoretical Informatics and Applications

DA - 2010/3//

PB - EDP Sciences

VL - 35

IS - 4

SP - 331

EP - 350

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

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

ER -

## References

top- J. Jaffar, Minimal and Complete Word Unification. J. ACM37 (1990) 47-85.
- Yu.I. Hmelevskii, Equations in free semigroups. Trudy Mat. Inst. Steklova 107 (1971); English Translation in Proc. Steklov Inst. Math. 107 (1971) 1976.
- A. Lentin, Équations dans les monoïdes libres. Gautier-Villars, Paris (1972).
- M. Lothaire, Combinatorics on Words. Addison-Wesley (1983).
- 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.
- 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.
- G. Plotkin, Building-in Equational Theories. Machine intelligence7 (1972) 73-90.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.