Author(s):

Chatterjee, Krishnendu; Henzinger, Thomas A; IbsenJensen, Rasmus; Otop, Jan

Title: 
Edit distance for pushdown automata

Title Series: 
LNCS

Affiliation 
IST Austria 
Abstract: 
The edit distance between two words w1, w2 is the minimal number of word operations (letter insertions, deletions, and substitutions) necessary to transform w1 to w2. The edit distance generalizes to languages L1,L2, where the edit distance is the minimal number k such that for every word from L1 there exists a word in L2 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 pushdown automata 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 deciding whether, for a given threshold k, the edit distance from a pushdown automaton to a finite automaton is at most k.

Keywords: 
Standard model; Edit distance; Recursions; Computational linguistics; Pushdown automata

Conference Title:

ICALP: Automata, Languages and Programming

Volume: 
9135

Issue 
Part II

Conference Dates:

July 610, 2015

Publisher:

Springer

Date Published:

20150701

Start Page: 
121

End Page:

133

URL: 

DOI: 
10.1007/9783662476666_10

Notes: 
This research was funded in part by the European Research Council (ERC) under grant agreement 267989 (QUAREM), by the Austrian Science Fund (FWF) projects S11402N23 (RiSE) and Z211N23 (Wittgenstein Award), FWF Grant No P23499N23, FWF NFN Grant No S11407N23 (RiSE), ERC Start grant (279307: Graph Games), and MSR faculty fellows award.

Open access: 
yes (repository) 