On the parameterised complexity of string morphism problems

DOI10.1007/S00224-015-9635-3MaRDI QIDQ315525zbMATH OpenOpenAlexFDO

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/

zbMATH Keywords

exponential time hypothesisstring morphismsparameterised complexitypattern languagesstring problems

Mathematics Subject Classification ID

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

Recommendations

• On the parameterised complexity of string morphism problems
• Multivariate algorithmics for NP-hard string problems
• Pattern matching with variables: a multivariate complexity analysis
• Algorithms for detecting morphic images of a word
• Pattern Matching with Variables: A Multivariate Complexity Analysis

Cites work

• scientific article; zbMATH DE number 2038765 (Why is no real title available?)
• scientific article; zbMATH DE number 1499087 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• A FORMAL STUDY OF PRACTICAL REGULAR EXPRESSIONS
• A polynomial time match test for large classes of extended regular expressions
• Charge and reduce: A fixed-parameter algorithm for string-to-string correction
• Exact exponential algorithms.
• Finding a homomorphism between two words is NP-complete
• Finite degrees of ambiguity in pattern languages
• Generalized function matching
• Learning relational patterns
• Lower bounds based on the exponential time hypothesis
• On product covering in 3-tier supply chain models: natural complete problems for W[3] and W[4]
• On the parameterised complexity of string morphism problems
• 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
• Parametrized complexity theory.
• Pattern Matching with Variables: A Multivariate Complexity Analysis
• Pattern languages with and without erasing
• Patterns with Bounded Treewidth
• The Turing way to parameterized complexity
• UNAMBIGUOUS MORPHIC IMAGES OF STRINGS
• Which problems have strongly exponential complexity?

Cited in

(16)

• Matching patterns with variables under edit distance
• 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
• Graph and string parameters: connections between pathwidth, cutwidth and the locality number
• scientific article; zbMATH DE number 6851884 (Why is no real title available?)
• Matching patterns with variables under Simon's congruence
• Languages generated by conjunctive query fragments of FC[REG]
• Incremental problems in the parameterized complexity setting
• The invariant problem for binary string structures and the parallel complexity theory of queries
• Variant Satisfiability of Parameterized Strings
• Deterministic regular expressions with back-references

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)