Abstract
In 1977 G.S. Makanin [Mak] proved that it is decidable whether a word equation has a solution or not. Here we describe two improvements of Makanin's algorithm which bring it nearer to the area of practical applicability: a simple pre-algorithm is suggested which decides the solvability of word equations with not more than two occurrences of each variable and which partially solves and simplifies the decision procedure for all other equations. A new transformation procedure is given which applies to arbitrary position equations and has several advantages. In a separate part we generalize Makanin's result and show that the solvability of word equations with variables x1,...,xn remains decidable when we specify regular languages L1,...,Ln over the coefficient alphabet and ask for solutions where the i-th components belongs to Li.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
H.Abdulrab, Résolution d'équations sur les mots: Etude et implémentation LISP de l'algorithme de MAKANIN, Thèse de doctorat-Laboratoire d'informatique, Rouen 1987.
V.K.Bulitko, Equations and Inequalities in a Free Group and a Free Semigroup, Tul. Cos. Ped. Inst. Učen. Zap. Mat. Kafedr Vyp.2, Geometr. i Algebra (1970), pp. 242–252 (Russian).
D.C.Cooper, Theorem-proving in Arithmetic without Multiplication, Machine Intelligence 7 (1972), 82–95.
Z.Farkas, Listlog — A Prolog Extension for List Processing, Proc. TAPSOFT 1987, March 1987, LNCS 250, Vol. 2, 82–95.
L.Fribourg, List Concatenation via Extended Unification, Programmation en Logique, Actes du Séminaire 1987, Trégastel 1987, 45–59.
J.I.Hmelevskii, Equations in Free Semigroups, Trudy Mat. Inst. Steklov. 107 (1971); English transl. Proc. Steklov Inst. Math. 107 (1971).
J.Jaffar, Minimal and Complete Word Unification, JACM 37 (1), 47–85.
A.Kościelski,L.Pacholski, Complexity of Unification in free groups and free semigroups, Proc. 3st Annual IEEE Symposium on Foundations of Computer Science, Los Alamitos 1990, 824–829.
A.Lentin, Equations in Free Monoids, in Automata Languages and Programming, (M. Nivat, ed.) North Holland Publishers, Amsterdam 1972, 67–85.
A.Lentin,M.P.Schützenberger, A Combinatorial Problem in the Theory of Free Monoids, Proc. of the University of North-Carolina (1967), 128–144.
M.Livesey,J.Siekmann, Termination and Decidability Results for String Unification, Essex University, Memo, 1975.
M.Lothaire, Combinatorics on words, Addison Wesley, 1983.
G.S.Makanin, The problem of solvability of equations in a free semigroup, Math. USSR Sbornik 32, 2 (1977), 129–198.
G.S.Makanin, Recognition of the Rank of Equations in a Free Semigroup, Math. USSR Izvestija 14, 3 (1980), 499–545.
J.P.Pécuchet, Equations avec constantes et algorithme de Makanin, Thèse de doctorat, Laboratoire d' informatique, Rouen 1981.
G.Plotkin, Building-in Equational Theories, Machine Intelligence 7 (1972), 73–90.
J.A.Robinson, A Machine-Oriented Logic based on the Resolution Principle, Journal of the ACM 12 (1965), 32–41.
A.Roussel, Programmation de l'algorithme de Makanin en PROLOG II, Memoire de D.E.A., Université Aix-Marseille II, 1987.
K.U.Schulz, A Guide to Makanin's Algorithm, SNS-Bericht 88-39, Seminar für natürlich-sprachliche Systeme, University of Tübingen 1989.
K.U.Schulz, A Note on Makanin's Algorithm, SNS-Bericht 89-53, Seminar für natürlich-sprachliche Systeme, University of Tübingen 1989.
K.U.Schulz, Makanin's Algorithm — Two Improvements and a Generalization, CIS-Report 91-39, Centrum für Informations-und Sprachverarbeitung, University of Munique,1991.
J.Siekmannn, A Modification of Robinson's Unification Procedure, M.Sc.Thesis, 1972.
J. Siekmannn, Unification and Matching Problems, Ph.D.Thesis, Essex University, Memo CSA-4-78, 1978.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1992 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Schulz, K.U. (1992). Makanin's algorithm for word equations-two improvements and a generalization. In: Schulz, K.U. (eds) Word Equations and Related Topics. IWWERT 1990. Lecture Notes in Computer Science, vol 572. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-55124-7_4
Download citation
DOI: https://doi.org/10.1007/3-540-55124-7_4
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-55124-9
Online ISBN: 978-3-540-46737-3
eBook Packages: Springer Book Archive