On the parameterised complexity of string morphism problems

DOI10.1007/s00224-015-9635-3zbMath1350.68139OpenAlexW797346804MaRDI QIDQ315525

Yngve Villanger, Markus L. Schmid, Henning Fernau

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/

zbMATH Keywords

exponential time hypothesisstring morphismsparameterised complexitypattern languagesstring problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items

Blocksequences of \(k\)-local words ⋮ Distinguishing pattern languages with membership examples ⋮ Matching patterns with variables under edit distance ⋮ Parameterized dictionary matching and recognition with one gap ⋮ Incremental problems in the parameterized complexity setting ⋮ Unnamed Item ⋮ On the Solvability Problem for Restricted Classes of Word Equations ⋮ Deterministic regular expressions with back-references ⋮ The hardness of solving simple word equations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Charge and reduce: A fixed-parameter algorithm for string-to-string correction
• Finding a homomorphism between two words is NP-complete
• Exact exponential algorithms.
• On product covering in 3-tier supply chain models: natural complete problems for W[3 and W[4]]
• On the parameterized complexity of multiple-interval graph problems
• Which problems have strongly exponential complexity?
• The Turing way to parameterized complexity
• 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
• Parametrized complexity theory.
• Patterns with Bounded Treewidth
• A Polynomial Time Match Test for Large Classes of Extended Regular Expressions
• Learning Relational Patterns
• 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
• A FORMAL STUDY OF PRACTICAL REGULAR EXPRESSIONS