On the parameterised complexity of string morphism problems
type: Item
instance of: scholarly article
title: On the parameterised complexity of string morphism problems
zbMATH Open document ID: 1350.68139
author: Henning Fernau
author: Markus L. Schmid
author: Yngve Villanger
published in: Theory of Computing Systems
publication date: 2016-09-21T00:00:00Z
full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2013/4361/
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 6628963
zbMATH Keywords: string problems
zbMATH Keywords: string morphisms
zbMATH Keywords: parameterised complexity
zbMATH Keywords: exponential time hypothesis
zbMATH Keywords: pattern languages
MaRDI profile type: Publication
OpenAlex ID: W797346804
cites work: Charge and reduce: A fixed-parameter algorithm for string-to-string correction
cites work: Q4449230
cites work: Generalized function matching
cites work: Parameterized pattern matching: Algorithms and applications
cites work: A FORMAL STUDY OF PRACTICAL REGULAR EXPRESSIONS
cites work: The Turing way to parameterized complexity
cites work: On product covering in 3-tier supply chain models: natural complete problems for W[3] and W[4]
cites work: Q4501141
cites work: Finding a homomorphism between two words is NP-complete
cites work: On the parameterized complexity of multiple-interval graph problems
cites work: Pattern Matching with Variables: A Multivariate Complexity Analysis
cites work: Q2963897
cites work: Parametrized complexity theory.
cites work: Exact exponential algorithms.
cites work: UNAMBIGUOUS MORPHIC IMAGES OF STRINGS
cites work: Learning Relational Patterns
cites work: Q4714446
cites work: Which problems have strongly exponential complexity?
cites work: Pattern languages with and without erasing
cites work: Q4904144
cites work: Finite degrees of ambiguity in pattern languages
cites work: On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
cites work: A Polynomial Time Match Test for Large Classes of Extended Regular Expressions
cites work: Patterns with Bounded Treewidth
DOI: 10.1007/S00224-015-9635-3
description: scientific article; zbMATH DE number 6628963