On PSPACE generation of a solution set of a word equation and its applications

DOI10.1016/j.tcs.2018.10.023zbMath1430.68256OpenAlexW2898856767MaRDI QIDQ2326385

Wojciech Plandowski

Publication date: 7 October 2019

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2018.10.023

zbMATH Keywords

word equationscombinatorics on wordsexpressible relation

Mathematics Subject Classification ID

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

Related Items

Word equations in non-deterministic linear space

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding all solutions of equations in free groups and monoids with involution
• Makanin's algorithm is not primitive recursive
• Equations in free semigroups
• Two-variable word equations
• Satisfiability of word equations with constants is in NEXPTIME
• Recompression
• Minimal and complete word unification
• Satisfiability of word equations with constants is in PSPACE
• ON SYSTEMS OF EQUATIONS IN A FREE GROUP
• Definability in the Existential Theory of Concatenation and Undecidable Extensions of this Theory
• THE PROBLEM OF SOLVABILITY OF EQUATIONS IN A FREE SEMIGROUP
• Complexity of Makanin's algorithm
• The expressibility of languages and relations by word equations
• On the expressibility of languages by word equations with a bounded number of variables
• Makanin's algorithm for word equations-two improvements and a generalization