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

DOI10.1016/J.IC.2016.02.001MaRDI QIDQ259082zbMATH OpenOpenAlexFDO

Authors Sang-Ki Ko, Yo-Sub Han, Kai Salomaa

Publication date 10 March 2016

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ic.2016.02.001

zbMATH Keywords

approximate matchingcontext-free grammarsedit distancefinite-state automatagap penalty

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Grammars and rewriting systems (68Q42) Algorithms on strings (68W32)

Recommendations

• Approximate matching between a context-free grammar and a finite-state automaton
• Computing the edit-distance between a regular language and a context-free language
• Approximately matching context-free languages
• Computing the edit distance of a regular language
• The edit-distance between a regular language and a context-free language

Cites work

• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 193480 (Why is no real title available?)
• scientific article; zbMATH DE number 194974 (Why is no real title available?)
• scientific article; zbMATH DE number 2201366 (Why is no real title available?)
• scientific article; zbMATH DE number 3240929 (Why is no real title available?)
• scientific article; zbMATH DE number 3254900 (Why is no real title available?)
• A Minimum Distance Error-Correcting Parser for Context-Free Languages
• An efficient context-free parsing algorithm
• Approximate regular expression pattern matching with concave gap penalties
• Approximately matching context-free languages
• Computing the edit distance of a regular language
• Distances between languages and reflexivity of relations
• EDIT-DISTANCE OF WEIGHTED AUTOMATA: GENERAL DEFINITIONS AND ALGORITHMS
• Sequence comparison with concave weighting functions
• Syntax-directed least-errors analysis for context-free languages
• The edit-distance between a regular language and a context-free language

Cited in

(8)

• On the Simon's congruence neighborhood of languages
• Edit distance neighbourhoods of input-driven pushdown automata
• Computing the edit-distance between a regular language and a context-free language
• Approximate matching between a context-free grammar and a finite-state automaton
• Edit distance neighbourhoods of input-driven pushdown automata
• Exact and approximate matching of matrix languages
• Finite Approximations and Similarity of Languages
• Linear-space computation of the edit-distance between a string and a finite automaton

Describes a project that uses

Uses Software

• Algorithm 97

This page was built for publication: Approximate matching between a context-free grammar and a finite-state automaton

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