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

DOI10.1016/J.IC.2016.02.001zbMATH Open1336.68317OpenAlexW2258074816MaRDI QIDQ259082FDOQ259082

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

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

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)

Cites Work

• Title not available (Why is that?)
• Sequence comparison with concave weighting functions
• Distances between languages and reflexivity of relations
• Approximate regular expression pattern matching with concave gap penalties
• Computing the edit distance of a regular language
• Title not available (Why is that?)
• Title not available (Why is that?)
• Syntax-directed least-errors analysis for context-free languages
• Title not available (Why is that?)
• THE EDIT-DISTANCE BETWEEN A REGULAR LANGUAGE AND A CONTEXT-FREE LANGUAGE
• Title not available (Why is that?)
• Title not available (Why is that?)
• An efficient context-free parsing algorithm
• A Minimum Distance Error-Correcting Parser for Context-Free Languages
• EDIT-DISTANCE OF WEIGHTED AUTOMATA: GENERAL DEFINITIONS AND ALGORITHMS
• Approximately matching context-free languages

Cited In (6)

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

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)