@inproceedings{35b903a99d4f48ff8d9deb987b7b6cc9,
title = "Edit-distance between visibly pushdown languages",
abstract = "We study the edit-distance between two visibly pushdown languages. It is well-known that the edit-distance between two context-free languages is undecidable. The class of visibly pushdown languages is a robust subclass of context-free languages since it is closed under intersection and complementation whereas context-free languages are not. We show that the edit-distance problem is decidable for visibly pushdown languages and present an algorithm for computing the edit-distance based on the construction of an alignment PDA. Moreover, we show that the edit-distance can be computed in polynomial time if we assume that the edit-distance is bounded by a fixed integer k.",
keywords = "Algorithm, Decidability, Edit-distance, Visibly pushdown languages",
author = "Han, {Yo Sub} and Ko, {Sang Ki}",
note = "Publisher Copyright: {\textcopyright} Springer International Publishing AG 2017.; 43rd Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2017 ; Conference date: 16-01-2017 Through 20-01-2017",
year = "2017",
doi = "10.1007/978-3-319-51963-0_30",
language = "English",
isbn = "9783319519623",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "387--401",
editor = "Christel Baier and {van den Brand}, Mark and Johann Eder and Mike Hinchey and Tiziana Margaria and Bernhard Steffen",
booktitle = "SOFSEM 2017",
address = "Germany",
}