Satisfiability of word equations with constants is in PSPACE

DOI10.1145/990308.990312zbMath1192.68372MaRDI QIDQ3583578

Wojciech Plandowski

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

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

08A50: Word problems (aspects of algebraic structures)

Related Items

Graph Logics with Rational Relations, Unnamed Item, POLYNOMIAL-TIME COMPLEXITY FOR INSTANCES OF THE ENDOMORPHISM PROBLEM IN FREE GROUPS, One-variable word equations in linear time, Finding all solutions of equations in free groups and monoids with involution, An efficient SMT solver for string constraints, Z3str2: an efficient solver for strings, regular expressions, and length constraints, On the complexity of decidable cases of the commutation problem of languages, An SMT solver for regular expressions and linear arithmetic over string length, \(\forall \exists^{5}\)-equational theory of context unification is undecidable, Systems of word equations, polynomials and linear algebra: a new approach, On equations and first-order theory of one-relator monoids, Word equations in non-deterministic linear space, 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 PSPACE generation of a solution set of a word equation and its applications, On the complexity of computation maximal exponent of periodicity of word equations and expressible relations (note), Equations over free inverse monoids with idempotent variables, 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, More Than 1700 Years of Word Equations, A Decision Procedure for Regular Membership and Length Constraints over Unbounded Strings, Equations in the Partial Semigroup of Words with Overlapping Products, Chain-Free String Constraints, Solutions to twisted word equations and equations in virtually free groups, What Is Essential Unification?, 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