Computing the edit-distance between a regular language and a context-free language

DOI10.1007/978-3-642-31653-1_9zbMATH Open1370.68171OpenAlexW2099378921MaRDI QIDQ3167486FDOQ3167486

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

Publication date: 2 November 2012

Published in: Developments in Language Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-31653-1_9

Recommendations

• The edit-distance between a regular language and a context-free language
• Computing the edit distance of a regular language
• How hard is computing the edit distance?
• Approximate matching between a context-free grammar and a finite-state automaton
• How hard is to compute the edit distance

zbMATH Keywords

regular languagecontext-free languageedit-distanceLevenshtein distance

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cited In (6)

• Finite Approximations and Similarity of Languages
• Linear-space computation of the edit-distance between a string and a finite automaton
• Parameterized Prefix Distance between Regular Languages
• How hard is computing the edit distance?
• Approximating Language Edit Distance Beyond Fast Matrix Multiplication: Ultralinear Grammars Are Where Parsing Becomes Hard!
• Efficient algorithms for computing the inner edit distance of a regular language via transducers

This page was built for publication: Computing the edit-distance between a regular language and a context-free language

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