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.
|Title of host publication||SOFSEM 2017|
|Subtitle of host publication||Theory and Practice of Computer Science - 43rd International Conference on Current Trends in Theory and Practice of Computer Science, Proceedings|
|Editors||Christel Baier, Mark van den Brand, Johann Eder, Mike Hinchey, Tiziana Margaria, Bernhard Steffen|
|Number of pages||15|
|Publication status||Published - 2017|
|Event||43rd Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2017 - Limerick, Ireland|
Duration: 2017 Jan 16 → 2017 Jan 20
|Name||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|
|Other||43rd Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2017|
|Period||17/1/16 → 17/1/20|
Bibliographical notePublisher Copyright:
© Springer International Publishing AG 2017.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Computer Science(all)