Edit distance for pushdown automata Conference Paper


Author(s): Chatterjee, Krishnendu; Henzinger, Thomas A; Ibsen-Jensen, 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; Push-down automata
Conference Title: ICALP: Automata, Languages and Programming
Volume: 9135
Issue Part II
Conference Dates: July 6-10, 2015
Publisher: Springer  
Date Published: 2015-07-01
Start Page: 121
End Page: 133
URL:
DOI: 10.1007/978-3-662-47666-6_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 S11402-N23 (RiSE) and Z211-N23 (Wittgenstein Award), FWF Grant No P23499-N23, FWF NFN Grant No S11407-N23 (RiSE), ERC Start grant (279307: Graph Games), and MSR faculty fellows award.
Open access: yes (repository)
IST Austria Authors
  1. Thomas A. Henzinger
    415 Henzinger
  2. Jan Otop
    16 Otop
Related IST Austria Work