No Access

SOLVABILITY OF EQUATIONS IN GRAPH GROUPS IS DECIDABLE

Institut für Formale Methoden der Informatik (FMI), Universität Stuttgart, Universitätsstr. 38, D-70569 Stuttgart, Germany

Search for more papers by this author

and

ANCA MUSCHOLL

LIAFA, Université Paris VII, 2, place Jussieu, case 7014, F-75251 Paris Cedex 05, France

Current address: LaBRI, Universite Bordeaux 1, 351, cours de la Liberation, F-33405 Talence.

Search for more papers by this author

https://doi.org/10.1142/S0218196706003372Cited by:21 (Source: Crossref)

Abstract

We show that the existential theory of free partially commutative monoids with involution is decidable. As a consequence the existential theory of graph groups is also decidable. If the underlying alphabet of generators is fixed, we obtain a PSPACE-completeness result, otherwise (in the uniform setting) our decision procedure is in EXPSPACE. Our proof is a reduction to the main result of [6].

Keywords:

AMSC: 68Q25, 68Q70

References

A. V. Anisimov and D. E. Knuth, Int. J. Comput. Inf. Sci. 8, 255 (1979). Crossref, Google Scholar
A. Baudisch, Acta Math. Acad. Sci. Hung. 38, 19 (1981), DOI: 10.1007/BF01917515. Crossref, Web of Science, Google Scholar
M. Benois, C. R. Acad. Sci. Paris, Sér. A 269, 1188 (1969). Web of Science, Google Scholar
N. Brady and J. Meier, Trans. Amer. Math. Soc. 353, 117 (2001), DOI: 10.1090/S0002-9947-00-02506-X. Crossref, Web of Science, Google Scholar
P. Cartier and D. Foata , Problèmes Combinatoires de Commutation et Réarrangements , Lecture Notes in Mathematics 85 ( Springer-Verlag , Berlin Heidelberg , 1969 ) . Crossref, Google Scholar
V. Diekert, C. Gutiérrez and C. Hagenah, The existential theory of equations with rational constraints in free groups is PSPACE-complete, STACS'01, Lecture Notes in Computer Science 2010 (Springer, Berlin, 2001) pp. 170–182. Google Scholar
V. Diekert and M. Lohrey, Word equations over graph products, Proc. 23rd Conf. Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2003), Lecture Notes in Computer Science 2914, eds. P. K. Pandya and J. Radhakrishnan (Springer-Verlag, 2003) pp. 156–167. Google Scholar
V. Diekert and M. Lohrey, Theoret. Comput. Syst. 37, 133 (2004), DOI: 10.1007/s00224-003-1110-x. Crossref, Web of Science, Google Scholar
V. Diekert, Yu. Matiyasevich and A. Muscholl, Theoret. Comput. Sci. 224, 215 (1999), DOI: 10.1016/S0304-3975(98)00313-2. Crossref, Web of Science, Google Scholar
V. Diekert and A. Muscholl, Solvability of equations in free partially commutative groups is decidable, Proc. 28th Int. Colloq. Automata, Languages and Programming (ICALP'01), Lecture Notes in Computer Science 2076, eds. F. Orejas, P. G. Spirakis and J. van Leeuwen (Springer-Verlag, Berlin Heidelberg, 2001) pp. 543–554. Google Scholar
V. Diekert and G. Rozenberg (eds.) , The Book of Traces ( World Scientific , Singapore , 1995 ) . Link, Google Scholar
C. Droms, Proc. Amer. Math. Soc. 100, 407 (1987), DOI: 10.2307/2046419. Crossref, Web of Science, Google Scholar
C. Gutiérrez, Satisfiability of equations in free groups is in PSPACE, Proc. 32nd Ann. ACM Symp. Theory of Computing, STOC'2000 (ACM Press, 2000) pp. 21–27, DOI: 10.1145/335305.335308. Google Scholar
R. M. Keller, J. Assoc. Comput. Mach. 20(3), 514 (1973), DOI: 10.1145/321765.321782. Crossref, Web of Science, Google Scholar
A. Kościelski and L. Pacholski, Theoret. Comput. Sci. 191, 145 (1998), DOI: 10.1016/S0304-3975(96)00321-0. Crossref, Web of Science, Google Scholar
D. Kozen, Lower bounds for natural proof systems, Proc. 18th Ann. Symp. Foundations of Computer Science, FOCS'77 (IEEE Computer Society Press, 1977) pp. 254–266. Google Scholar
G. S. Makanin, Math. Sbornik 103, 147 (1977). Google Scholar
G. S. Makanin, Izv. Akad. Nauk SSR, Ser. Math. 46, 1199 (1982). Google Scholar
Yu. Matiyasevich, Some decision problems for traces, Proc. 4th Int. Symp. Logical Foundations of Computer Science (LFCS'97), Lecture Notes in Computer Science 1234, eds. S. Adian and A. Nerode (Springer-Verlag, Berlin Heidelberg, 1997) pp. 248–257. Google Scholar
A. Mazurkiewicz, Concurrent program schemes and their interpretations, DAIMI Rep. PB 78, Aarhus University, Aarhus, 1977 . Google Scholar
A. Mazurkiewicz, Petri Nets, Applications and Relationship to Other Models of Concurrency, Lecture Notes in Computer Science 255, eds. W. Braueret al. (Springer-Verlag, Berlin Heidelberg, 1987) pp. 279–324. Google Scholar
A. Muscholl, Decision and complexity issues on concurrent systems, Habilitationsschrift (Postdoctoral thesis), Universität Stuttgart, 1999 . Google Scholar
E. Ochmański, Bull. Eur. Assoc. Theoret. Comput. Sci. (EATCS) 27, 56 (1985). Google Scholar
E. Ochmański, The Book of Traces, eds. V. Diekert and G. Rozenberg (World Scientific, Singapore, 1995) pp. 167–204. Link, Google Scholar
W. Plandowski, J. Assoc. Comput. Mach. 51, 483 (2004), DOI: 10.1145/990308.990312. Crossref, Web of Science, Google Scholar
M. Schaefer, E. Sedgwick and D. Štefankovič, J. Comput. Syst. Sci. 365 (2003), DOI: 10.1016/S0022-0000(03)00045-X. Google Scholar
K. U. Schulz, Word Equations and Related Topics, Lecture Notes in Computer Science 572, ed. K. U. Schulz (Springer-Verlag, Berlin, Heidelberg, 1991) pp. 85–150. Google Scholar