Satisfiability of word equations with constants is in PSPACE

DOI10.1145/990308.990312zbMath1192.68372OpenAlexW2028685566MaRDI 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

Analysis of algorithms and problem complexity (68Q25) Word problems (aspects of algebraic structures) (08A50)

Related Items (40)

The complexity of solution sets to equations in hyperbolic groups ⋮ An SMT solver for regular expressions and linear arithmetic over string length ⋮ Equations in the Partial Semigroup of Words with Overlapping Products ⋮ Systems of word equations, polynomials and linear algebra: a new approach ⋮ POLYNOMIAL-TIME COMPLEXITY FOR INSTANCES OF THE ENDOMORPHISM PROBLEM IN FREE GROUPS ⋮ Finding all solutions of equations in free groups and monoids with involution ⋮ Word equations in the context of string solving ⋮ Equations over free inverse monoids with idempotent variables ⋮ More Than 1700 Years of Word Equations ⋮ Regular matching and inclusion on compressed tree patterns with constrained context variables ⋮ ON NON-PERIODIC SOLUTIONS OF INDEPENDENT SYSTEMS OF WORD EQUATIONS OVER THREE UNKNOWNS ⋮ A solver for arrays with concatenation ⋮ A Decision Procedure for Regular Membership and Length Constraints over Unbounded Strings ⋮ WORD EQUATIONS OVER GRAPH PRODUCTS ⋮ An Analysis and a Reproof of Hmelevskii’s Theorem ⋮ Chain-Free String Constraints ⋮ Solutions to twisted word equations and equations in virtually free groups ⋮ What Is Essential Unification? ⋮ Word equations in non-deterministic linear space ⋮ An efficient SMT solver for string constraints ⋮ Z3str2: an efficient solver for strings, regular expressions, and length constraints ⋮ The complexity of compressed membership problems for finite automata ⋮ On the complexity of decidable cases of the commutation problem of languages ⋮ On systems of word equations over three unknowns with at most six occurrences of one of the unknowns ⋮ Towards Decidability of Conjugacy of Pairs and Triples ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On maximal chains of systems of word equations ⋮ Solving one-variable equations in free groups ⋮ Graph Logics with Rational Relations ⋮ On equations and first-order theory of one-relator monoids ⋮ Unnamed Item ⋮ On the Complexity of Hmelevskii’s Theorem and Satisfiability of Three Unknown Equations ⋮ 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) ⋮ 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 ⋮ SOLVABILITY OF EQUATIONS IN GRAPH GROUPS IS DECIDABLE ⋮ \(\forall \exists^{5}\)-equational theory of context unification is undecidable ⋮ One-variable word equations in linear time

This page was built for publication: Satisfiability of word equations with constants is in PSPACE