Maksimenko, Marianne 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 RAIRO, Inform. Théor. Appl. 29, No. 4, 277-284 (1995). Summary: We propose an algorithm computing all the solutions of word equations in one variable with quadratic complexity. MSC: 68W10 Parallel algorithms in computer science 68Q25 Analysis of algorithms and problem complexity Keywords:word equations; quadratic complexity PDF BibTeX XML Cite \textit{M. Maksimenko}, RAIRO, Inform. Théor. Appl. 29, No. 4, 277--284 (1995; Zbl 0838.68049) Full Text: DOI EuDML OpenURL References: [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.