×

zbMATH — the first resource for mathematics

The existential theory of equations with rational constraints in free groups is PSPACE-complete. (English) Zbl 1101.68649
Summary: It is well-known that the existential theory of equations in free groups is decidable. This is a celebrated result of Makanin which was published 1982. Makanin did not discuss complexity issues, but later it was shown that the scheme of his algorithm is not primitive recursive. In this paper we present an algorithm that works in polynomial space. This improvement is based upon an extension of Plandowski’s techniques for solving word equations. We present a pspace-algorithm in a more general setting where each variable has a rational constraint, that is, the solution has to respect a specification given by a regular word language. We obtain our main result about the existential theory in free groups as a corollary of the corresponding statement in free monoids with involution.

MSC:
68Q45 Formal languages and automata
PDF BibTeX Cite
Full Text: DOI
References:
[1] Benois, M., Parties rationelles du groupe libre, C.R. acad. sci. Paris, Sér. A, 269, 1188-1190, (1969) · Zbl 0214.03903
[2] Berstel, J., Transductions and context-free languages, (1979), Teubner Studienbücher Stuttgart · Zbl 0424.68040
[3] Diekert, V., Makanin’s algorithm, (), 387-442, Chapter 12
[4] V. Diekert, C. Gutierrez, C. Hagenah, The existential theory of equations with rational constraints in free groups is PSPACE-complete, in: A. Ferreira, H. Reichel (Eds.), Proceedings of the 18th Annual Symposium on Theoretical Aspects of Computer Science (STACS’01), Dresden (Germany), 2001, Lecture Notes in Computer Science, vol. 2010, Springer-Verlag, Berlin, 2001, pp. 170-182. · Zbl 0976.68095
[5] V. Diekert, M. Lohrey. Word equations over graph products, in: P.K. Pandya, J. Radhakrishnan (Eds.), Proceedings of the 23rd Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2003), Mumbai (India), Lecture Notes in Computer Science, vol. 2914, Springer-Verlag, Berlin, 2003, pp. 156-167. · Zbl 1188.20066
[6] Diekert, V.; Lohrey, M., Existential and positive theories of equations in graph products, Theory comput. syst., 37, 133-156, (2004) · Zbl 1067.03017
[7] Diekert, V.; Matiyasevich, Yu.; Muscholl, A., Solving word equations modulo partial commutations, Theoretical comput. sci., 224, 215-235, (1999), Special issue of LFCS’97 · Zbl 0930.68074
[8] V. Diekert, A. Muscholl. Solvability of equations in free partially commutative groups is decidable, in: F. Orejas, P.G. Spirakis, J. van Leeuwen (Eds.), Proceedings of the 28th International Colloquium on Automata, Languages and Programming (ICALP’01), Lecture Notes in Computer Science, vol. 2076, Springer-Verlag, Berlin Heidelberg, 2001, pp. 543-554. · Zbl 0986.20036
[9] V.G. Durnev, Undecidability of the positive \(\forall \exists^3\)-theory of a free semi-group. Sibirsky Matematicheskie Jurnal, 36(5) (1995) 1067-1080 (In Russian; English translation: Sib. Math. J. 36(5) (1995) 917-929).
[10] S. Eilenberg, Automata, Languages, and Machines, volume A. Academic Press, New York and London, 1974. · Zbl 0317.94045
[11] Garey, M.R.; Johnson, D.S., Computers and intractability: A guide to the theory of NP-completeness, (1979), W.H. Freeman and Company San Francisco · Zbl 0411.68039
[12] von zur Gathen, J.; Sieveking, M., A bound on solutions of linear integer equalities and inequalities, Proc. am. math. soc., 72, 1, 155-158, (1978) · Zbl 0397.90071
[13] Y. Gurevich, A. Voronkov, Monadic simultaneous rigid E-unification and related problems, in: P. Degano, R. Gorrieri, A. Marchetti-Spaccamela (Eds.), Proceedings of the 24th International Colloquium on Automata, Languages and Programming (ICALP’97), Bologna, Lecture Notes in Computer Science, vol. 1256, Springer-Verlag, Berlin Heidelberg, 1997, pp. 154-165. · Zbl 1401.03037
[14] C. Gutierrez, Satisfiability of word equations with constants is in exponential space, in: Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS’98), Los Alamitos (California), EEE Computer Society Press, 1998, pp. 112-119.
[15] C. Gutierrez, Equations in free semigroups with anti-involution and their relation to equations in free groups, in: G.H. Gonnet, D. Panario, A. Viola (Eds.), Proceedings Latin American Theoretical INformatics, LATIN’2000, Lecture Notes in Computer Science, vol. 1776, Springer-Verlag, Berlin, 2000, pp. 387-396. · Zbl 0982.20041
[16] C. Gutierrez, Satisfiability of equations in free groups is in PSPACE, in: Proceedings 32nd Annual ACM Symposium on Theory of Computing, STOC’2000, ACM Press, 2000, pp. 21-27. · Zbl 1296.68079
[17] C. Hagenah, Gleichungen mit regulären Randbedingungen über freien Gruppen, Ph.D. thesis, Institut für Informatik, Universität Stuttgart, 2000. · Zbl 1020.20023
[18] Hopcroft, J.E.; Ullman, J.D., Introduction to automata theory, languages, and computation, (1979), Addison-Wesley Reading, MA · Zbl 0196.01701
[19] Karhumäki, J.; Mignosi, F.; Plandowski, W., The expressibility of languages and relations by word equations, J. assoc. comput. machinery, 47, 483-505, (2000) · Zbl 1094.68618
[20] Kościelski, A.; Pacholski, L., Complexity of makanin’s algorithm, J. assoc. comput. machinery, 43, 4, 670-684, (1996) · Zbl 0882.68073
[21] Kościelski, A.; Pacholski, L., Makanin’s algorithm is not primitive recursive, Theoretical comput. sci., 191, 145-156, (1998) · Zbl 0908.68107
[22] D. Kozen, Lower bounds for natural proof systems, in: Proceedings of the 18th Annual Symposium on Foundations of Computer Science, FOCS’77, Providence, Rhode Island, IEEE Computer Society Press, 1977, pp. 254-266.
[23] M. Lothaire, Combinatorics on words, in: Encyclopedia of Mathematics and its Applications, vol. 17 Addison-Wesley, Reading, MA, 1983, Reprinted by Cambridge University Press, 1997. · Zbl 0514.20045
[24] G.S. Makanin, The problem of solvability of equations in a free semigroup. Math. Sbornik, 103 (1977) 147-236. English transl. in Math. USSR Sbornik 32 (1977). · Zbl 0371.20047
[25] G.S. Makanin, Equations in a free group. Izv. Akad. Nauk SSR, Ser. Math. 46 (1982) 1199-1273. English transl. in Math. USSR Izv. 21 (1983). · Zbl 0511.20019
[26] G.S. Makanin, Decidability of the universal and positive theories of a free group. Izv. Akad. Nauk SSSR, Ser. Mat. 48 (1984) 735-749. In Russian; English translation in: Math. USSR Izvestija, 25 (1985) 75-88.
[27] Marchenkov, S.S., Unsolvability of positive \(\forall \exists\)-theory of a free semi-group, Sibirsky matematicheskie jurnal, 23, 1, 196-198, (1982), In Russian · Zbl 0578.03024
[28] Markowsky, G., Bounds on the index and period of a binary relation on a finite set, Semigroup forum, 13, 253-259, (1977) · Zbl 0353.20055
[29] Yu. Matiyasevich, Reduction of trace equations to word equations. Talk given at the “Colloquium on Computability, Complexity, and Logic”, Institut für Informatik, Universität Stuttgart, Germany, Dec. 5-6, 1996.
[30] Yu. Matiyasevich, Some decision problems for traces, in: S. Adian, A. Nerode (Eds.), Proceedings of the 4th International Symposium on Logical Foundations of Computer Science (LFCS’97), Yaroslavl, Russia, July 6-12, 1997, Lecture Notes in Computer Science, vol. 1234, Springer-Verlag, Berlin Heidelberg, 1997, pp. 248-257 (Invited lecture). · Zbl 0899.20030
[31] Merzlyakov, Yu.I., Positive formulae over free groups, Algebra i logika, 5, 4, 25-42, (1966), In Russian · Zbl 0216.29402
[32] W. Plandowski, Testing equivalence of morphisms on context-free languages, in: J. van Leeuwen (Ed.), Algorithms—ESA’94, Second Annual European Symposium, Lecture Notes in Computer Science, vol. 855, Utrecht, The Netherlands, Springer, 1994, pp. 460-470.
[33] W. Plandowski, Satisfiability of word equations with constants is in NEXPTIME, in: Proceedings of the 31st Annual ACM Symposium on Theory of Computing, STOC’99, ACM Press, 1999, pp. 721-725. · Zbl 1346.68113
[34] W. Plandowski, Satisfiability of word equations with constants is in PSPACE, in: Proceedings of the 40th Annual Symposium on Foundations of Computer Science, FOCS’99, IEEE Computer Society Press, 1999, pp. 495-500. · Zbl 1346.68113
[35] Plandowski, W., Satisfiability of word equations with constants is in PSPACE, J. assoc. comput. machinery, 51, 483-496, (2004) · Zbl 1192.68372
[36] W. Plandowski, W. Rytter, Application of Lempel-Ziv encodings to the solution of word equations, in: K.G. Larsen et al., (Eds.), Proceedings of the 25th International Colloquium on Automata, Languages and Programming (ICALP’98), Aalborg (Denmark), 1998, Lecture Notes in Computer Science, vol. 1443, Springer-Verlag, Berlin Heidelberg, 1998, pp. 731-742. · Zbl 0909.68134
[37] A.A. Razborov, On systems of equations in a free group. Izv. Akad. Nauk SSSR, Ser. Mat. 48:779-832, 1984. In Russian; English translation in: Math. USSR Izvestija, 25 (1985) 115-162.
[38] K.U. Schulz, Makanin’s algorithm for word equations—Two improvements and a generalization, in: K.U. Schulz (Ed.), Word Equations and Related Topics, Lecture Notes in Computer Science, vol. 572, Springer-Verlag, Berlin Heidelberg, 1991, pp. 85-150.
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.