On the complexity of solving restricted word equations

DOI10.1142/S0129054118420108MaRDI QIDQ4683237zbMATH OpenOpenAlexFDO

Authors Florin Manea, Dirk Nowotka, Markus L. Schmid

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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorics on words (68R15)

Recommendations

• On the Solvability Problem for Restricted Classes of Word Equations
• The hardness of solving simple word equations
• scientific article; zbMATH DE number 1304322
• scientific article; zbMATH DE number 1408356
• scientific article; zbMATH DE number 1500512

Cites work

• scientific article; zbMATH DE number 4070305 (Why is no real title available?)
• scientific article; zbMATH DE number 3577484 (Why is no real title available?)
• scientific article; zbMATH DE number 1304322 (Why is no real title available?)
• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• An efficient algorithm for solving word equations
• Automata, Languages and Programming
• Efficient solving of the word equations in one variable
• On word equations in one variable
• One-variable word equations in linear time
• Parameterized algorithms
• Pattern matching with variables: a multivariate complexity analysis
• Pattern matching with variables: fast algorithms and new hardness results
• Patterns with bounded treewidth
• Recompression: a simple and powerful technique for word equations
• The complexity of satisfiability problems
• Which problems have strongly exponential complexity?

Cited in

(17)

• scientific article; zbMATH DE number 1408356 (Why is no real title available?)
• On the complexity of computation maximal exponent of periodicity of word equations and expressible relations (note)
• Quadratic word equations with length constraints, counter systems, and Presburger arithmetic with divisibility
• The hardness of solving simple word equations
• On the Solvability Problem for Restricted Classes of Word Equations
• Two-variable word equations
• The satisfiability of word equations: decidable and undecidable theories
• On PSPACE generation of a solution set of a word equation and its applications
• Word equations in synergy with regular constraints
• On the structure of solution-sets to regular word equations
• Complexity results on restricted instances of a paint shop problem for words
• On the structure of solution sets to regular word equations
• Word equations in the context of string solving
• Satisfiability of word equations with constants is in NEXPTIME
• Solving equations on words with morphisms and antimorphisms
• Makanin's algorithm for word equations-two improvements and a generalization
• The Restricted Word Shadow Problem

This page was built for publication: On the complexity of solving restricted word equations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4683237)