Edit Distance for Pushdown Automata

Abstract

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 ${\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 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.

An extended version of a paper accepted to ICALP 2015 with the same title. The paper has been accepted to the LMCS journal

References in corpus (1)

• Edit Distance for Pushdown Automata

Cited by in corpus (3)

• Semantically-informed distance and similarity measures for paraphrase plagiarism identification
• Edit Distance for Pushdown Automata
• Average Stack Cost of Buechi Pushdown Automata