On the Solvability Problem for Restricted Classes of Word Equations

DOI10.1007/978-3-662-53132-7_25zbMath1436.68141OpenAlexW2502441406MaRDI QIDQ2817397

Dirk Nowotka, Florin Manea, Markus L. Schmid

Publication date: 30 August 2016

Published in: Developments in Language Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-662-53132-7_25

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)

The hardness of solving simple word equations

Cites Work

• 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
• Which problems have strongly exponential complexity?
• Pattern matching with variables: a multivariate complexity analysis
• An efficient algorithm for solving word equations
• Recompression
• The complexity of satisfiability problems
• Automata, Languages and Programming
• Parameterized Algorithms

This page was built for publication: On the Solvability Problem for Restricted Classes of Word Equations