On the Solvability Problem for Restricted Classes of Word Equations

DOI10.1007/978-3-662-53132-7_25MaRDI QIDQ2817397zbMATH OpenOpenAlexFDO

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

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 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

Cites work

• 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
• On the parameterised complexity of string morphism problems
• 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

(10)

• The hardness of solving simple word equations
• On the structure of solution-sets to regular word equations
• The satisfiability of word equations: decidable and undecidable theories
• Word equations in synergy with regular constraints
• On maximal chains of systems of word equations
• On PSPACE generation of a solution set of a word equation and its applications
• On the Solution Sets of Entire Systems of Word Equations
• Solving equations on words with morphisms and antimorphisms
• Languages generated by conjunctive query fragments of FC[REG]
• On the complexity of solving restricted word equations

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)