Quadratic algorithm for computing for the general solution of word equations in one variable. (Algorithme quadratique de calcul de la solution générale d’équations en mots à une variable.) (French) Zbl 0838.68049

Summary: We propose an algorithm computing all the solutions of word equations in one variable with quadratic complexity.


68W10 Parallel algorithms in computer science
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI EuDML


[1] 1. W. CHARATONIC et L. PACHOLSKI, Solving Word Equations in Two Variables, Lecture Notes in Computer Sciences, IWWERT’91, Proceedings, Springer-verlag, 1991, p. 43-56. Zbl0925.20082 · Zbl 0925.20082
[2] 2. J.-P. DUVAL, Contribution à la combinatoire du monoïde libre, Thèse, Université de Rouen, 1980.
[3] 3. N. J. FINE et H. S. WILF, Uniqueness Theorem for Periodic Function, Proc. Am. Math. Soc., 1965, 16. Zbl0131.30203 MR174934 · Zbl 0131.30203
[4] 4. J. I. KHMELEVSKIÏ, Equations in Free Semigroups, Trudy Mat Inst. Steklov, 1971, 107. Zbl0224.02037 · Zbl 0224.02037
[5] 5. A. A. MARKOV, The Theory of Algorithms, Trudy Mat. Inst. Steklov, 1954, 42. Zbl0058.00501 MR77473 · Zbl 0058.00501
[6] 6. J. H. MORRIS et V. R. PRATT, A Linear Pattern Matching Algorithm, Technical Report N^\circ 40, Computing Center, University of California, Berkeley, 1970.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.