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

DOI10.1007/978-3-642-31653-1_9MaRDI QIDQ3167486zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

context-free languageedit-distanceLevenshtein distanceregular language

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

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

Cited in

(12)

• Efficient algorithms for computing the inner edit distance of a regular language via transducers
• How hard is computing the edit distance?
• Approximate matching between a context-free grammar and a finite-state automaton
• Parameterized Prefix Distance between Regular Languages
• Linear-space computation of the edit-distance between a string and a finite automaton
• Approximating Language Edit Distance Beyond Fast Matrix Multiplication: Ultralinear Grammars Are Where Parsing Becomes Hard!
• Approximate matching between a context-free grammar and a finite-state automaton
• Top-down tree edit-distance of regular tree languages
• The edit-distance between a regular language and a context-free language
• Finite Approximations and Similarity of Languages
• Edit distance of finite state transducers
• Characterisation of language intersections using distances

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)