×

Towards parametrizing word equations. (English) Zbl 1112.68434

Summary: 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 fewer 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 for the case in which the prime equations in the graph involve at most three variables.

MSC:

68R15 Combinatorics on words
PDFBibTeX XMLCite
Full Text: DOI Numdam Numdam EuDML

References:

[1] J. Jaffar , Minimal and Complete Word Unification . J. ACM 37 ( 1990 ) 47 - 85 . MR 1072430 | Zbl 0697.68052 · Zbl 0697.68052 · doi:10.1145/78935.78938
[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 393284 | Zbl 0326.02032 · Zbl 0326.02032
[3] A. Lentin , Équations dans les monoïdes libres . Gautier-Villars, Paris ( 1972 ). MR 333034 | Zbl 0258.20058 · Zbl 0258.20058
[4] M. Lothaire , Combinatorics on Words . Addison-Wesley ( 1983 ). MR 675953 | Zbl 0514.20045 · Zbl 0514.20045
[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 470107 | Zbl 0396.20037 · Zbl 0396.20037 · doi:10.1070/SM1977v032n02ABEH002376
[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 0925.20067 · Zbl 0925.20067
[7] G. Plotkin , Building-in Equational Theories . Machine intelligence 7 ( 1972 ) 73 - 90 . Zbl 0262.68036 · Zbl 0262.68036
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.