WORD EQUATIONS OVER GRAPH PRODUCTS

DOI10.1142/S0218196708004548zbMath1186.20041MaRDI QIDQ3521473

Volker Diekert, Markus Lohrey

Publication date: 26 August 2008

Published in: International Journal of Algebra and Computation (Search for Journal in Brave)

zbMATH Keywords

algorithms; decidability; graph products; logical theories; equations in groups; solvability of equations; existential theories; positive theories; equations in monoids

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

20M05: Free semigroups, generators and relations, word problems

03D35: Undecidability and degrees of sets of sentences

68Q70: Algebraic theory of languages and automata

03B25: Decidability of theories and sets of sentences

68Q42: Grammars and rewriting systems

20E06: Free products of groups, free products with amalgamation, Higman-Neumann-Neumann extensions, and generalizations

20F10: Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)

20F70: Algebraic geometry over groups; equations over groups

Related Items

COMPRESSED DECISION PROBLEMS FOR GRAPH PRODUCTS AND APPLICATIONS TO (OUTER) AUTOMORPHISM GROUPS, On systems of equations over free products of groups., Existential questions in (relatively) hyperbolic groups.

Cites Work

• Unnamed Item
• Graph groups, coherence, and three-manifolds
• Existential and positive theories of equations in graph products
• Elementary theory of free non-abelian groups.
• Diophantine theories of free inverse semigroups
• On regular trace languages
• Preperfectness is undecidable for Thue systems containing only length- reducing rules and a single commutation rule
• Positive theories of free inverse semigroups
• The complexity of logical theories
• Automatic groups and amalgams
• Algorithms and geometry for graph products of groups
• Canonical representatives and equations in hyperbolic groups
• Solving word equations modulo partial commutations
• On graph products of automatic and biautomatic monoids.
• Kleene quotient theorems
• Combinatorial problems of commutation and rearrangements
• The existential theory of equations with rational constraints in free groups is PSPACE-complete
• On theories with a combinatorial definition of 'equivalence'
• GRAPH PRODUCTS AND CANNON PAIRS
• On graph products of automatic monoids
• SOLVABILITY OF EQUATIONS IN GRAPH GROUPS IS DECIDABLE
• Satisfiability of word equations with constants is in PSPACE
• DECIDABILITY OF THE POSITIVE THEORY OF A FREE COUNTABLY GENERATED SEMIGROUP
• Kommutationsgleichungen in semifreien gruppen
• Connectivity at infinity for right angled Artin groups
• Characterizations of the decidability of some problems for regular trace languages
• A NOTE ON THE EXISTENTIAL THEORY OF EQUATIONS IN PLAIN GROUPS
• ON POSITIVE THEORIES OF GROUPS WITH REGULAR FREE LENGTH FUNCTIONS
• LOGICAL ASPECTS OF CAYLEY-GRAPHS: THE MONOID CASE
• Concatenation as a basis for arithmetic
• Graph products of monoids