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].

For the entire collection see [Zbl 1029.00064].

##### 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 |