Diekert, Volker; Lohrey, Markus 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]. Cited in 3 Documents MSC: 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 Keywords:equations in groups; equations in monoids; logical theories; graph products; decidability; algorithms; solvability of equations; existential theories; positive theories PDFBibTeX XMLCite \textit{V. Diekert} and \textit{M. Lohrey}, Lect. Notes Comput. Sci. 2914, 156--167 (2003; Zbl 1188.20066) Full Text: DOI