Earlier Version

Edit distance for pushdown automata

K. Chatterjee, T.A. Henzinger, R. Ibsen-Jensen, J. Otop, Edit Distance for Pushdown Automata, IST Austria, 2015.

Download
OA IST-2015-334-v1+1_report.pdf 422.57 KB

Technical Report | Published | English
Department
Series Title
IST Austria Technical Report
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 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 deciding whether, for a given threshold k, the edit distance from a pushdown automaton to a finite automaton is at most k.
Publishing Year
Date Published
2015-05-05
Page
15
ISSN
IST-REx-ID

Cite this

Chatterjee K, Henzinger TA, Ibsen-Jensen R, Otop J. Edit Distance for Pushdown Automata. IST Austria; 2015. doi:10.15479/AT:IST-2015-334-v1-1
Chatterjee, K., Henzinger, T. A., Ibsen-Jensen, R., & Otop, J. (2015). Edit distance for pushdown automata. IST Austria. https://doi.org/10.15479/AT:IST-2015-334-v1-1
Chatterjee, Krishnendu, Thomas A Henzinger, Rasmus Ibsen-Jensen, and Jan Otop. Edit Distance for Pushdown Automata. IST Austria, 2015. https://doi.org/10.15479/AT:IST-2015-334-v1-1.
K. Chatterjee, T. A. Henzinger, R. Ibsen-Jensen, and J. Otop, Edit distance for pushdown automata. IST Austria, 2015.
Chatterjee K, Henzinger TA, Ibsen-Jensen R, Otop J. 2015. Edit distance for pushdown automata, IST Austria, 15p.
Chatterjee, Krishnendu, et al. Edit Distance for Pushdown Automata. IST Austria, 2015, doi:10.15479/AT:IST-2015-334-v1-1.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Main File(s)
File Name
Access Level
OA Open Access
Date Uploaded
2018-12-12
MD5 Checksum
8a5f2d77560e552af87eb1982437a43b


Material in IST:
Later Version
Later Version

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar