@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",

}