Satisfiability of word equations with constants is in NEXPTIME

DOI10.1145/301250.301443zbMath1346.68113OpenAlexW1989660382MaRDI QIDQ2819601

Wojciech Plandowski

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics on words (68R15)

Related Items

Decidability of bounded second order unification ⋮ Simplifying the signature in second-order unification ⋮ 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 ⋮ Equations in free semigroups with involution and their relation to equations in free groups. ⋮ Word equations in synergy with regular constraints ⋮ Equations on partial words ⋮ Word equations in non-deterministic linear space ⋮ On word equations in one variable ⋮ On systems of word equations over three unknowns with at most six occurrences of one of the unknowns ⋮ Unnamed Item ⋮ Matching Trace Patterns with Regular Policies ⋮ On systems of equations over free partially commutative groups ⋮ On PSPACE generation of a solution set of a word equation and its applications ⋮ 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 ⋮ On Conjugacy of Languages ⋮ One-variable word equations in linear time

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