Chatterjee, Krishnendu, Henzinger, Thomas A, Ibsen-Jensen, Rasmus and Otop, Jan
(2015)
Edit Distance for Pushdown Automata.
Automata, Languages, and Programming, 9135 (3).
pp. 121-133.
This is the latest version of this item.
Text
edtpda.pdf - Submitted version Download (268kB) |
|
Text
main.pdf - Author Accepted Manuscript Download (324kB) | Preview |
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.
Item Type: | Article |
---|---|
Uncontrolled Keywords: | Turing Machine, Target Language, Edit Distance, Regular Language, Context Free Grammar |
Depositing User: | Symplectic Admin |
Date Deposited: | 17 Dec 2019 09:07 |
Last Modified: | 19 Jan 2023 00:12 |
DOI: | 10.1007/978-3-662-47666-6_10 |
Related URLs: | |
URI: | https://livrepository.liverpool.ac.uk/id/eprint/3066683 |
Available Versions of this Item
-
Edit Distance for Pushdown Automata. (deposited 06 Dec 2018 09:21)
- Edit Distance for Pushdown Automata. (deposited 17 Dec 2019 09:07) [Currently Displayed]