On the Solvability Problem for Restricted Classes of Word Equations
DOI10.1007/978-3-662-53132-7_25zbMATH Open1436.68141OpenAlexW2502441406MaRDI QIDQ2817397FDOQ2817397
Authors: Florin Manea, Dirk Nowotka, 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
Recommendations
- On the complexity of solving restricted word equations
- On the Solution Sets of Entire Systems of Word Equations
- Solutions of word equations over partially commutative structures
- An optimal bound on the solution sets of one-variable word equations and its consequences
- An optimal bound on the solution sets of one-variable word equations and its consequences
- Solvability of symmetric word equations in positive definite letters
- scientific article; zbMATH DE number 4016226
- Solutions of systems consisting of word equations and inequalities in lengths of words
- Solving equations on words with morphisms and antimorphisms
- scientific article; zbMATH DE number 17526
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorics on words (68R15)
Cites Work
- Title not available (Why is that?)
- Which problems have strongly exponential complexity?
- One-variable word equations in linear time
- An efficient algorithm for solving word equations
- Title not available (Why is that?)
- The complexity of satisfiability problems
- Automata, Languages and Programming
- Parameterized algorithms
- Patterns with bounded treewidth
- On the parameterised complexity of string morphism problems
- Pattern matching with variables: a multivariate complexity analysis
- Recompression: a simple and powerful technique for word equations
- Pattern matching with variables: fast algorithms and new hardness results
- Title not available (Why is that?)
Cited In (10)
- The hardness of solving simple 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
- On the complexity of solving restricted word equations
- On maximal chains of systems of word equations
- On the Solution Sets of Entire Systems of Word Equations
- Languages generated by conjunctive query fragments of FC[REG]
- Solving equations on words with morphisms and antimorphisms
This page was built for publication: On the Solvability Problem for Restricted Classes of Word Equations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2817397)
