Edit-distance between visibly pushdown languages

DOI10.1007/978-3-319-51963-0_30MaRDI QIDQ2971150zbMATH OpenOpenAlexFDO

Authors Yo-Sub Han, Sang-Ki Ko

Publication date 4 April 2017

Published in SOFSEM 2017: Theory and Practice of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-51963-0_30

zbMATH Keywords

decidabilityedit distancevisibly pushdown languages

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Analysis of algorithms (68W40)

Recommendations

• Edit distance for pushdown automata
• Edit distance for pushdown automata
• 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?

Cites work

• Distances between languages and reflexivity of relations
• EDIT-DISTANCE OF WEIGHTED AUTOMATA: GENERAL DEFINITIONS AND ALGORITHMS
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3696500 (Why is no real title available?)
• scientific article; zbMATH DE number 1557065 (Why is no real title available?)
• scientific article; zbMATH DE number 194974 (Why is no real title available?)
• scientific article; zbMATH DE number 2201366 (Why is no real title available?)
• Marrying Words and Trees
• Programming Techniques: Regular expression search algorithm
• Regularity Problems for Visibly Pushdown Languages
• The edit-distance between a regular language and a context-free language
• The String-to-String Correction Problem
• Visibly pushdown languages

Cited in

(10)

• Deciding path size of nondeterministic (and input-driven) pushdown automata
• The relative edit-distance between two input-driven languages
• Edit distance for pushdown automata
• Approximating Language Edit Distance Beyond Fast Matrix Multiplication: Ultralinear Grammars Are Where Parsing Becomes Hard!
• Edit distance for pushdown automata
• Input-driven pushdown automata for edit distance neighborhood
• Edit distance neighbourhoods of input-driven pushdown automata
• Edit distance neighbourhoods of input-driven pushdown automata
• Weak inverse neighborhoods of languages
• Finite Approximations and Similarity of Languages

This page was built for publication: Edit-distance between visibly pushdown languages

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