Satisfiability of equations in free groups is in PSPACE
From MaRDI portal
Publication:3191967
DOI10.1145/335305.335308zbMath1296.68079OpenAlexW2022620380MaRDI QIDQ3191967
Publication date: 26 September 2014
Published in: Proceedings of the thirty-second annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/335305.335308
Analysis of algorithms and problem complexity (68Q25) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)
Related Items
Simplifying the signature in second-order unification ⋮ Finding all solutions of equations in free groups and monoids with involution ⋮ Equations over free inverse monoids with idempotent variables ⋮ More Than 1700 Years of Word Equations ⋮ Equations in free semigroups with involution and their relation to equations in free groups. ⋮ Solutions to twisted word equations and equations in virtually free groups ⋮ The existential theory of equations with rational constraints in free groups is PSPACE-complete ⋮ Quadratic equations in hyperbolic groups are NP-complete
This page was built for publication: Satisfiability of equations in free groups is in PSPACE