Computing the Shortest String and the Edit-Distance for Parsing Expression Languages

DOI10.1007/978-3-030-48516-0_4MaRDI QIDQ5041248zbMATH OpenOpenAlexFDO

Authors Hyunjoon Cheon, Yo-Sub Han

Publication date 13 October 2022

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

Full work available at URL https://doi.org/10.1007/978-3-030-48516-0_4

zbMATH Keywords

edit-distanceformal languagesparsing expression grammars

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• The edit-distance between a regular language and a context-free language
• How hard is to compute the edit distance
• How hard is computing the edit distance?
• Edit distance for pushdown automata
• Edit distance for pushdown automata

Cites work

• Computing the edit distance of a regular language
• Context-freeness of parsing expression languages is undecidable
• EDIT-DISTANCE OF WEIGHTED AUTOMATA: GENERAL DEFINITIONS AND ALGORITHMS
• Error detecting and error correcting codes
• scientific article; zbMATH DE number 1747449 (Why is no real title available?)
• scientific article; zbMATH DE number 3240929 (Why is no real title available?)
• Packrat parsing: simple, powerful, lazy, linear time
• Parsing algorithms with backtrack
• Parsing expression grammars: a recognition-based syntactic foundation
• State complexity of neighbourhoods and approximate pattern matching
• The edit-distance between a regular language and a context-free language
• Unambiguous Boolean grammars

Cited in

(6)

• Approximating Language Edit Distance Beyond Fast Matrix Multiplication: Ultralinear Grammars Are Where Parsing Becomes Hard!
• Weak inverse neighborhoods of languages
• Absent Subsequences in Words
• A weak inverse of language neighborhoods and its properties
• The edit distance to k-subsequence universality
• The edit distance to \(k\)-subsequence universality

This page was built for publication: Computing the Shortest String and the Edit-Distance for Parsing Expression Languages

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