Edit Distance for Pushdown Automata

摘要

The edit distance between two words $w_1, w_2$ is the minimal number of wordoperations (letter insertions, deletions, and substitutions) necessary totransform $w_1$ to $w_2$. The edit distance generalizes to languages$mathcal{L}_1, mathcal{L}_2$, where the edit distance from $mathcal{L}_1$ to$mathcal{L}_2$ is the minimal number $k$ such that for every word from$mathcal{L}_1$ there exists a word in $mathcal{L}_2$ with edit distance atmost $k$. We study the edit distance computation problem between pushdownautomata and their subclasses. The problem of computing edit distance to apushdown automaton is undecidable, and in practice, the interesting question isto compute the edit distance from a pushdown automaton (the implementation, astandard model for programs with recursion) to a regular language (thespecification). In this work, we present a complete picture of decidability andcomplexity for the following problems: (1)~deciding whether, for a giventhreshold $k$, the edit distance from a pushdown automaton to a finiteautomaton is at most $k$, and (2)~deciding whether the edit distance from apushdown automaton to a finite automaton is finite.