Satisfiability of word equations with constants is in PSPACE
From MaRDI portal
Publication:3583578
DOI10.1145/990308.990312zbMath1192.68372MaRDI QIDQ3583578
Publication date: 17 August 2010
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/990308.990312
68Q25: Analysis of algorithms and problem complexity
08A50: Word problems (aspects of algebraic structures)
Related Items
POLYNOMIAL-TIME COMPLEXITY FOR INSTANCES OF THE ENDOMORPHISM PROBLEM IN FREE GROUPS, On the complexity of decidable cases of the commutation problem of languages, \(\forall \exists^{5}\)-equational theory of context unification is undecidable, The complexity of compressed membership problems for finite automata, On systems of word equations over three unknowns with at most six occurrences of one of the unknowns, On maximal chains of systems of word equations, The existential theory of equations with rational constraints in free groups is PSPACE-complete, The non-parametrizability of the word equation \(xyz=zvx\): a short proof, Equations in the Partial Semigroup of Words with Overlapping Products, SOLVABILITY OF EQUATIONS IN GRAPH GROUPS IS DECIDABLE, ON NON-PERIODIC SOLUTIONS OF INDEPENDENT SYSTEMS OF WORD EQUATIONS OVER THREE UNKNOWNS, WORD EQUATIONS OVER GRAPH PRODUCTS, An Analysis and a Reproof of Hmelevskii’s Theorem, Towards Decidability of Conjugacy of Pairs and Triples, Solving one-variable equations in free groups, On the Complexity of Hmelevskii’s Theorem and Satisfiability of Three Unknown Equations
