Approximately matching context-free languages

DOI10.1016/0020-0190(95)00007-YzbMath0875.68446MaRDI QIDQ673469

Gene Myers

Publication date: 28 February 1997

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

Sequence comparisonPattern matchingDesign of algorithms

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Parallel algorithms in computer science (68W10)

Related Items (10)

Faster subsequence recognition in compressed strings ⋮ Exact and approximate matching of matrix languages ⋮ If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser ⋮ Approximate matching of XML document with regular hedge grammar ⋮ Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product ⋮ Towards Approximate Matching in Compressed Strings: Local Subsequence Recognition ⋮ Consensus String Problem for Multiple Regular Languages ⋮ Consensus string problem for multiple regular languages ⋮ Fast distance multiplication of unit-Monge matrices ⋮ Approximate matching between a context-free grammar and a finite-state automaton

Cites Work

• Unnamed Item
• A note on two problems in connexion with graphs
• General methods of sequence comparison
• Approximate matching of regular expressions
• Approximate regular expression pattern matching with concave gap penalties
• On a routing problem
• Correcting Counter-Automaton-Recognizable Languages
• Syntax-directed least-errors analysis for context-free languages
• Recognition and parsing of context-free languages in time n3
• An efficient context-free parsing algorithm
• A Minimum Distance Error-Correcting Parser for Context-Free Languages

This page was built for publication: Approximately matching context-free languages