WORD EQUATIONS OVER GRAPH PRODUCTS
Authors:
- 1 May 2008
- journal article
- research article
- Published by World Scientific Pub Co Pte Ltd in International Journal of Algebra and Computation
- Vol. 18 (03) , 493-533
Abstract
For monoids that satisfy a weak cancellation condition, it is shown that the decidability of the existential theory of word equations is preserved under graph products. Furthermore, it is shown that the positive theory of a graph product of groups can be reduced to the positive theories of those factors, which commute with all other factors, 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.Keywords
This publication has 40 references indexed in Scilit:
- Satisfiability of word equations with constants is in PSPACEJournal of the ACM, 2004
- On graph products of automatic monoidsRAIRO - Theoretical Informatics and Applications, 2001
- Solving word equations modulo partial commutationsTheoretical Computer Science, 1999
- Canonical representatives and equations in hyperbolic groupsInventiones Mathematicae, 1995
- Characterizations of the decidability of some problems for regular trace languagesTheory of Computing Systems, 1989
- DECIDABILITY OF THE POSITIVE THEORY OF A FREE COUNTABLY GENERATED SEMIGROUPMathematics of the USSR-Sbornik, 1983
- Subgroups of semifree groupsActa Mathematica Hungarica, 1981
- Kleene quotient theoremsPacific Journal of Mathematics, 1964
- Concatenation as a basis for arithmeticThe Journal of Symbolic Logic, 1946
- On Theories with a Combinatorial Definition of "Equivalence"Annals of Mathematics, 1942