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

algorithmsdecidabilitygraph productslogical theoriesequations in groupssolvability of equationsexistential theoriespositive theoriesequations in monoids

Mathematics Subject Classification ID

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

Related Items (15)

The Diophantine problem in the classical matrix groups ⋮ Finding all solutions of equations in free groups and monoids with involution ⋮ Existential questions in (relatively) hyperbolic groups. ⋮ Effective construction of covers of canonical Hom-diagrams for equations over torsion-free hyperbolic groups ⋮ Centralizers in graph products of semigroups ⋮ On graph products of monoids ⋮ Knapsack in graph groups ⋮ On systems of equations over free products of groups. ⋮ Closure properties of knapsack semilinear groups ⋮ Word equations in non-deterministic linear space ⋮ COMPRESSED DECISION PROBLEMS FOR GRAPH PRODUCTS AND APPLICATIONS TO (OUTER) AUTOMORPHISM GROUPS ⋮ Equations in groups that are virtually direct products ⋮ On equations and first-order theory of one-relator monoids ⋮ Logspace computations in graph products ⋮ Diophantine problems in solvable 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

This page was built for publication: WORD EQUATIONS OVER GRAPH PRODUCTS