A parameterized study of maximum generalized pattern matching problems

DOI10.1007/s00453-015-0008-8zbMath1345.68179arXiv1409.2398OpenAlexW1558603395MaRDI QIDQ300450

Alexandru Popa, Sebastian Ordyniak

Publication date: 28 June 2016

Published in: Algorithmica, Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1409.2398

zbMATH Keywords

parameterized complexitygeneralized pattern matchingstring morphisms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms on strings (68W32)

Related Items (3)

Partition on trees with supply and demand: kernelization and algorithms ⋮ Efficient solution of time-fractional differential equations with a new adaptive multi-term discretization of the generalized Caputo-Dzherbashyan derivative ⋮ Unnamed Item

Cites Work

• Patterns with bounded treewidth
• Finding a homomorphism between two words is NP-complete
• A non-learnable class of E-pattern languages
• Developments from enquiries into the learnability of the pattern languages from positive data
• Discontinuities in pattern inference
• Finding patterns common to a set of strings
• On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
• A note on the complexity of matching patterns with variables
• Generalized function matching
• Parametrized complexity theory.
• 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
• Unnamed Item
• Unnamed Item

This page was built for publication: A parameterized study of maximum generalized pattern matching problems