The hardness of solving simple word equations

DOI10.4230/LIPICS.MFCS.2017.18zbMath1441.68089arXiv1702.07922OpenAlexW2591974499MaRDI QIDQ5111232

Florin Manea, Joel D. Day, Dirk Nowotka

Publication date: 26 May 2020

Full work available at URL: https://arxiv.org/abs/1702.07922

zbMATH Keywords

word equationsregular constraintsregular patterns

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics on words (68R15) Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (7)

Word equations in the context of string solving ⋮ Languages generated by conjunctive query fragments of FC[REG] ⋮ Unnamed Item ⋮ Languages generated by conjunctive query fragments of FC[REG] ⋮ Unnamed Item ⋮ On the structure of solution-sets to regular word equations ⋮ Program specialization as a tool for solving word equations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• One-variable word equations in linear time
• On the parameterised complexity of string morphism problems
• Patterns with bounded treewidth
• Finding a homomorphism between two words is NP-complete
• Word unification and transformation of generalized equations
• Pattern matching with variables: a multivariate complexity analysis
• On the Solvability Problem for Restricted Classes of Word Equations
• An efficient algorithm for solving word equations
• Recompression
• Minimal and complete word unification
• Equations in Free Groups
• Complexity of Makanin's algorithm
• The expressibility of languages and relations by word equations
• Context Unification is in PSPACE
• Document Spanners: From Expressive Power to Decision Problems.
• Automata, Languages and Programming

This page was built for publication: The hardness of solving simple word equations