conference paper published yes Krishnendu Chatterjee author 2E5DCA20-F248-11E8-B48F-1D18A9856A870000-0002-4561-241X Thomas A Henzinger author 40876CD8-F248-11E8-B48F-1D18A9856A870000−0002−2985−7724 Rasmus Ibsen-Jensen author 3B699956-F248-11E8-B48F-1D18A9856A870000-0003-4783-0389 Jan Otop author 2FC5DA74-F248-11E8-B48F-1D18A9856A87 KrCh department ToHe department ICALP: Automata, Languages and Programming Quantitative Reactive Modeling project Formal methods for the design and analysis of complex systems project Modern Graph Algorithmic Techniques in Formal Verification project Game Theory project Quantitative Graph Games: Theory and Applications project Microsoft Research Faculty Fellowship project Rigorous Systems Engineering project 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. Springer Nature2015Kyoto, Japan eng 978-3-662-47665-9 1504.08259 00036431790001010.1007/978-3-662-47666-6_10 9135Part II121 - 133 https://research-explorer.ista.ac.at/record/5438 https://research-explorer.ista.ac.at/record/465 Chatterjee, Krishnendu, Thomas A Henzinger, Rasmus Ibsen-Jensen, and Jan Otop. “Edit Distance for Pushdown Automata.” In <i>42nd International Colloquium on Automata, Languages, and Programming</i>, 9135:121–33. Springer Nature, 2015. <a href="https://doi.org/10.1007/978-3-662-47666-6_10">https://doi.org/10.1007/978-3-662-47666-6_10</a>. Chatterjee, Krishnendu, et al. “Edit Distance for Pushdown Automata.” <i>42nd International Colloquium on Automata, Languages, and Programming</i>, vol. 9135, no. Part II, Springer Nature, 2015, pp. 121–33, doi:<a href="https://doi.org/10.1007/978-3-662-47666-6_10">10.1007/978-3-662-47666-6_10</a>. Chatterjee K, Henzinger TA, Ibsen-Jensen R, Otop J. 2015. Edit distance for pushdown automata. 42nd International Colloquium on Automata, Languages, and Programming. ICALP: Automata, Languages and Programming, LNCS, vol. 9135, 121–133. Chatterjee, K., Henzinger, T. A., Ibsen-Jensen, R., &#38; Otop, J. (2015). Edit distance for pushdown automata. In <i>42nd International Colloquium on Automata, Languages, and Programming</i> (Vol. 9135, pp. 121–133). Kyoto, Japan: Springer Nature. <a href="https://doi.org/10.1007/978-3-662-47666-6_10">https://doi.org/10.1007/978-3-662-47666-6_10</a> K. Chatterjee, T. A. Henzinger, R. Ibsen-Jensen, and J. Otop, “Edit distance for pushdown automata,” in <i>42nd International Colloquium on Automata, Languages, and Programming</i>, Kyoto, Japan, 2015, vol. 9135, no. Part II, pp. 121–133. K. Chatterjee, T.A. Henzinger, R. Ibsen-Jensen, J. Otop, in:, 42nd International Colloquium on Automata, Languages, and Programming, Springer Nature, 2015, pp. 121–133. Chatterjee K, Henzinger TA, Ibsen-Jensen R, Otop J. Edit distance for pushdown automata. In: <i>42nd International Colloquium on Automata, Languages, and Programming</i>. Vol 9135. Springer Nature; 2015:121-133. doi:<a href="https://doi.org/10.1007/978-3-662-47666-6_10">10.1007/978-3-662-47666-6_10</a> 16102018-12-11T11:53:01Z2026-07-06T13:27:53Z