Hostname: page-component-cd9895bd7-p9bg8 Total loading time: 0 Render date: 2024-12-23T13:07:26.439Z Has data issue: false hasContentIssue false

Towards parametrizing word equations

Published online by Cambridge University Press:  15 April 2002

H. Abdulrab
Affiliation:
LIR/INSA de Rouen, BP. 08, 76131 Mont-Saint-Aignan Cedex, France.
P. Goralčík
Affiliation:
LIFAR, Université de Rouen, place E. Blondel, 76821 Mont-Saint-Aignan Cedex, France.
G. S. Makanin
Affiliation:
Steklov Mathematical Institute, Vavilova 42, 117966 Moscow GSP-1, Russia.
Get access

Abstract

Classically, in order to resolve an equation uv over a free monoid X*, we reduce it by a suitable family $\cal F$ of substitutions to a family of equations ufvf, $f\in\cal F$, each involving less variables than uv, and then combine solutions of ufvf into solutions of uv. 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 uv. We carry out such a parametrization in the case the prime equations in the graph involve at most three variables.

Type
Research Article
Copyright
© EDP Sciences, 2001

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Jaffar, J., Minimal and Complete Word Unification. J. ACM 37 (1990) 47-85. CrossRef
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.
Plotkin, G., Building-in Equational Theories. Machine intelligence 7 (1972) 73-90.