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

DOI10.1007/978-3-642-39274-0_14zbMATH Open1298.68137OpenAlexW1779305186MaRDI QIDQ5327490FDOQ5327490

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

Publication date: 7 August 2013

Published in: Implementation and Application of Automata (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-39274-0_14

Recommendations

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

zbMATH Keywords

approximate matchingcontext-free grammarsfinite-state automataedit-distance

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Cited In (3)

• Decidability of involution hypercodes
• Finite Approximations and Similarity of Languages
• Efficient algorithms for computing the inner edit distance of a regular language via transducers

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 Q5327490)