Word equations over graph products. (English) Zbl 1188.20066

Pandya, Paritosh K. (ed.) et al., FST TCS 2003: Foundations of software technology and theoretical computer science. 23rd conference, Mumbai, India, December 15–17, 2003. Proceedings. Berlin: Springer (ISBN 3-540-20680-9/pbk). Lect. Notes Comput. Sci. 2914, 156-167 (2003).
Summary: For a restricted class of monoids, we prove that the decidability of the existential theory of word equations is preserved under graph products. Furthermore, we show that the positive theory of a graph product of groups can be reduced to the positive theories of some of the factor monoids and the existential theories of the remaining factors. Both results also include suitable constraints for the variables. Larger classes of constraints lead in many cases to undecidability results.
For the entire collection see [Zbl 1029.00064].


20M05 Free semigroups, generators and relations, word problems
03B25 Decidability of theories and sets of sentences
20F10 Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)
20E06 Free products of groups, free products with amalgamation, Higman-Neumann-Neumann extensions, and generalizations
03D35 Undecidability and degrees of sets of sentences
68Q70 Algebraic theory of languages and automata
68Q42 Grammars and rewriting systems
20F70 Algebraic geometry over groups; equations over groups
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI