Approximately matching context-free languages

DOI10.1016/0020-0190(95)00007-YMaRDI QIDQ673469zbMATH OpenFDO

Authors Gene Myers

Publication date 28 February 1997

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

zbMATH Keywords

Pattern matchingSequence comparisonDesign of algorithms

Mathematics Subject Classification ID

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

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

Cites work

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

Cited in

(16)

• Fast distance multiplication of unit-Monge matrices
• Towards approximate matching in compressed strings: local subsequence recognition
• Consensus string problem for multiple regular languages
• If the current clique algorithms are optimal, so is Valiant's parser
• scientific article; zbMATH DE number 2087044 (Why is no real title available?)
• Weighted edit distance computation: strings, trees, and Dyck
• Consensus string problem for multiple regular languages
• String editing under pattern constraints
• Approximate matching between a context-free grammar and a finite-state automaton
• Developments in Language Theory
• Exact and approximate matching of matrix languages
• Approximate matching of XML document with regular hedge grammar
• Faster subsequence recognition in compressed strings
• scientific article; zbMATH DE number 4035186 (Why is no real title available?)
• Approximate matching between a context-free grammar and a finite-state automaton
• Truly subcubic algorithms for language edit distance and RNA folding via fast bounded-difference min-plus product

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)