On the parameterised complexity of string morphism problems
From MaRDI portal
Publication:315525
DOI10.1007/S00224-015-9635-3zbMATH Open1350.68139OpenAlexW797346804MaRDI QIDQ315525FDOQ315525
Authors: Henning Fernau, Markus L. Schmid, Yngve Villanger 
Publication date: 21 September 2016
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2013/4361/
Recommendations
Cites Work
- Title not available (Why is that?)
- Exact exponential algorithms.
- Which problems have strongly exponential complexity?
- Parametrized complexity theory.
- Lower bounds based on the exponential time hypothesis
- On the parameterized complexity of multiple-interval graph problems
- On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
- Parameterized pattern matching: Algorithms and applications
- Generalized function matching
- On the parameterised complexity of string morphism problems
- Finite degrees of ambiguity in pattern languages
- Pattern languages with and without erasing
- Pattern Matching with Variables: A Multivariate Complexity Analysis
- UNAMBIGUOUS MORPHIC IMAGES OF STRINGS
- Finding a homomorphism between two words is NP-complete
- The Turing way to parameterized complexity
- Patterns with Bounded Treewidth
- A polynomial time match test for large classes of extended regular expressions
- Learning relational patterns
- Title not available (Why is that?)
- Title not available (Why is that?)
- Charge and reduce: A fixed-parameter algorithm for string-to-string correction
- A FORMAL STUDY OF PRACTICAL REGULAR EXPRESSIONS
- On product covering in 3-tier supply chain models: natural complete problems for W[3] and W[4]
Cited In (16)
- Distinguishing pattern languages with membership examples
- Blocksequences of \(k\)-local words
- The hardness of solving simple word equations
- Multivariate algorithmics for NP-hard string problems
- On the Solvability Problem for Restricted Classes of Word Equations
- Parameterized dictionary matching and recognition with one gap
- On the parameterised complexity of string morphism problems
- Title not available (Why is that?)
- Matching patterns with variables under Simon's congruence
- Languages generated by conjunctive query fragments of FC[REG]
- Variant Satisfiability of Parameterized Strings
- Title not available (Why is that?)
- Incremental problems in the parameterized complexity setting
- The invariant problem for binary string structures and the parallel complexity theory of queries
- Deterministic regular expressions with back-references
- Matching patterns with variables under edit distance
This page was built for publication: On the parameterised complexity of string morphism problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q315525)
