Edit distance for pushdown automata
Chatterjee, Krishnendu
Henzinger, Thomas A
Ibsen-Jensen, Rasmus
Otop, Jan
ddc:004
The edit distance between two words w 1 , w 2 is the minimal number of word operations (letter insertions, deletions, and substitutions) necessary to transform w 1 to w 2 . The edit distance generalizes to languages L 1 , L 2 , where the edit distance from L 1 to L 2 is the minimal number k such that for every word from L 1 there exists a word in L 2 with edit distance at most k . We study the edit distance computation problem between pushdown automata and their subclasses. The problem of computing edit distance to a pushdown automaton is undecidable, and in practice, the interesting question is to compute the edit distance from a pushdown automaton (the implementation, a standard model for programs with recursion) to a regular language (the specification). In this work, we present a complete picture of decidability and complexity for the following problems: (1) deciding whether, for a given threshold k , the edit distance from a pushdown automaton to a finite automaton is at most k , and (2) deciding whether the edit distance from a pushdown automaton to a finite automaton is finite.
International Federation of Computational Logic
2017
info:eu-repo/semantics/article
doc-type:article
text
https://research-explorer.app.ist.ac.at/record/465
https://research-explorer.app.ist.ac.at/download/465/5090
https://research-explorer.app.ist.ac.at/download/465/5091
Chatterjee K, Henzinger TA, Ibsen-Jensen R, Otop J. Edit distance for pushdown automata. <i>Logical Methods in Computer Science</i>. 2017;13(3). doi:<a href="https://doi.org/10.23638/LMCS-13(3:23)2017">10.23638/LMCS-13(3:23)2017</a>
eng
info:eu-repo/semantics/altIdentifier/doi/10.23638/LMCS-13(3:23)2017
info:eu-repo/semantics/altIdentifier/issn/18605974
info:eu-repo/grantAgreement/FWF/S11402-N23
info:eu-repo/grantAgreement/FWF/P 23499-N23
info:eu-repo/grantAgreement/FWF/Z211
info:eu-repo/grantAgreement/EC/FP7/267989
info:eu-repo/grantAgreement/EC/FP7/279307
info:eu-repo/grantAgreement/FWF/S11407
cc_by_nd
info:eu-repo/semantics/openAccess