10.23638/LMCS-13(3:23)2017
Chatterjee, Krishnendu
Krishnendu
Chatterjee0000-0002-4561-241X
Henzinger, Thomas A
Thomas A
Henzinger0000−0002−2985−7724
Ibsen-Jensen, Rasmus
Rasmus
Ibsen-Jensen
Otop, Jan
Jan
Otop
Edit distance for pushdown automata
International Federation of Computational Logic
2017
2018-12-11T11:46:37Z
2020-01-21T13:20:35Z
journal_article
https://research-explorer.app.ist.ac.at/record/465
https://research-explorer.app.ist.ac.at/record/465.json
18605974
279071 bytes
279071 bytes
application/pdf
application/pdf
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.