Approximate regular expression pattern matching with concave gap penalties

DOI10.1007/BF01300375zbMath0837.68039OpenAlexW1977902724MaRDI QIDQ1894715

J. R. Knight, Eugene W. Myers

Publication date: 16 April 1996

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01300375

zbMATH Keywords

pattern-matching algorithm

Mathematics Subject Classification ID

Pattern recognition, speech recognition (68T10) Parallel algorithms in computer science (68W10)

Related Items (2)

Approximately matching context-free languages ⋮ Approximate matching between a context-free grammar and a finite-state automaton

Cites Work

• Unnamed Item
• Unnamed Item
• General methods of sequence comparison
• A linear-time algorithm for concave one-dimensional dynamic programming
• Geometric applications of a matrix-searching algorithm
• Sequence comparison with concave weighting functions
• Approximate matching of regular expressions
• Speeding up dynamic programming with applications to molecular biology
• An Almost Linear Time Algorithm for Generalized Matrix Searching
• Sequence comparison with mixed convex and concave costs
• Self-adjusting binary search trees
• The Least Weight Subsequence Problem
• The concave least-weight subsequence problem revisited
• A Simple Algorithm for Global Data Flow Analysis Problems
• Sparse dynamic programming II
• The String-to-String Correction Problem
• Matching Sequences under Deletion/Insertion Constraints

This page was built for publication: Approximate regular expression pattern matching with concave gap penalties