On the Complexity of Solving Restricted Word Equations

DOI10.1142/S0129054118420108zbMath1403.68176OpenAlexW2888400000MaRDI QIDQ4683237

Florin Manea, Markus L. Schmid, Dirk Nowotka

Publication date: 20 September 2018

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054118420108

zbMATH Keywords

NP-hardnessword equationsregular constraints

Mathematics Subject Classification ID

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

Related Items (1)

Word equations in the context of string solving

Cites Work

• One-variable word equations in linear time
• Patterns with bounded treewidth
• On word equations in one variable
• Which problems have strongly exponential complexity?
• Pattern matching with variables: a multivariate complexity analysis
• An efficient algorithm for solving word equations
• Recompression
• Efficient solving of the word equations in one variable
• The complexity of satisfiability problems
• Automata, Languages and Programming
• Parameterized Algorithms
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the Complexity of Solving Restricted Word Equations