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

DOI10.1016/j.ic.2016.02.001zbMath1336.68317OpenAlexW2258074816MaRDI QIDQ259082

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

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

context-free grammarsfinite-state automataapproximate matchingedit distancegap penalty

Mathematics Subject Classification ID

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

Related Items (4)

On the Simon's congruence neighborhood of languages ⋮ Finite Approximations and Similarity of Languages ⋮ Edit distance neighbourhoods of input-driven pushdown automata ⋮ Edit distance neighbourhoods of input-driven pushdown automata

Uses Software

• Algorithm 97

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximately matching context-free languages
• 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
• Syntax-directed least-errors analysis for context-free languages
• THE EDIT-DISTANCE BETWEEN A REGULAR LANGUAGE AND A CONTEXT-FREE LANGUAGE
• 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

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