Satisfiability of word equations with constants is in NEXPTIME
From MaRDI portal
Publication:2819601
DOI10.1145/301250.301443zbMath1346.68113MaRDI QIDQ2819601
Publication date: 29 September 2016
Published in: Proceedings of the thirty-first annual ACM symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/301250.301443
Related Items
One-variable word equations in linear time, Finding all solutions of equations in free groups and monoids with involution, On word equations in one variable, Simplifying the signature in second-order unification, Equations in free semigroups with involution and their relation to equations in free groups., Decidability of bounded second order unification, 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, Equations over free inverse monoids with idempotent variables, 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, On systems of equations over free partially commutative groups, On Conjugacy of Languages, Equations on partial words, Matching Trace Patterns with Regular Policies
