SOLVABILITY OF EQUATIONS IN GRAPH GROUPS IS DECIDABLE

DOI10.1142/S0218196706003372zbMath1112.03009OpenAlexW2027103910MaRDI QIDQ3430310

Volker Diekert, Anca Muscholl

Publication date: 21 March 2007

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

Full work available at URL: https://doi.org/10.1142/s0218196706003372

zbMATH Keywords

free partially commutative monoidsequationsgraph groups

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Free semigroups, generators and relations, word problems (20M05) Decidability of theories and sets of sentences (03B25) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (16)

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. ⋮ The Diophantine problem in some metabelian groups ⋮ Knapsack in graph groups ⋮ WORD EQUATIONS OVER GRAPH PRODUCTS ⋮ Equations in Algebras ⋮ The submonoid and rational subset membership problems for graph groups. ⋮ Undecidability of equations in free Lie algebras ⋮ Partially commutative inverse monoids. ⋮ Equations in groups that are virtually direct products ⋮ On systems of equations over free partially commutative groups ⋮ Logspace computations in graph products ⋮ Diophantine problems in solvable groups ⋮ Limit groups over partially commutative groups and group actions on real cubings ⋮ Rational subsets and submonoids of wreath products.

Cites Work

• Existential and positive theories of equations in graph products
• Makanin's algorithm is not primitive recursive
• Solving word equations modulo partial commutations
• Combinatorial problems of commutation and rearrangements
• Satisfiability of word equations with constants is in PSPACE
• Connectivity at infinity for right angled Artin groups
• Parallel Program Schemata and Maximal Parallelism I. Fundamental Results
• Inhomogeneous sorting

This page was built for publication: SOLVABILITY OF EQUATIONS IN GRAPH GROUPS IS DECIDABLE