Satisfiability of equations in free groups is in PSPACE
From MaRDI portal
Publication:3191967
DOI10.1145/335305.335308zbMath1296.68079MaRDI 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
68Q25: Analysis of algorithms and problem complexity
20F10: Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)
Related Items
Quadratic equations in hyperbolic groups are NP-complete, Finding all solutions of equations in free groups and monoids with involution, Simplifying the signature in second-order unification, Equations in free semigroups with involution and their relation to equations in free groups., Equations over free inverse monoids with idempotent variables, The existential theory of equations with rational constraints in free groups is PSPACE-complete, More Than 1700 Years of Word Equations, Solutions to twisted word equations and equations in virtually free groups