Approximately matching context-free languages

DOI10.1016/0020-0190(95)00007-YzbMATH Open0875.68446MaRDI QIDQ673469FDOQ673469

Authors: Gene Myers 

Publication date: 28 February 1997

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

Recommendations

• Approximate matching between a context-free grammar and a finite-state automaton
• Approximate matching between a context-free grammar and a finite-state automaton
• Approximate regular expression pattern matching with concave gap penalties
• Publication:4206395
• Exact and approximate matching of matrix languages

zbMATH Keywords

Pattern matchingSequence comparisonDesign of algorithms

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (16)

• Approximate matching between a context-free grammar and a finite-state automaton
• Developments in Language Theory
• Approximate matching between a context-free grammar and a finite-state automaton
• Towards approximate matching in compressed strings: local subsequence recognition
• Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product
• If the current clique algorithms are optimal, so is Valiant's parser
• Exact and approximate matching of matrix languages
• Fast distance multiplication of unit-Monge matrices
• Consensus string problem for multiple regular languages
• String editing under pattern constraints
• Approximate matching of XML document with regular hedge grammar
• Weighted edit distance computation: strings, trees, and Dyck
• Title not available (Why is that?)
• Title not available (Why is that?)
• Consensus string problem for multiple regular languages
• Faster subsequence recognition in compressed strings

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q673469)