Edit-Distance Between Visibly Pushdown Languages

Han, Yo-Sub and Ko, Sang-Ki (2017) Edit-Distance Between Visibly Pushdown Languages. .

Text VPL.pdf - Author Accepted Manuscript Download (124kB)

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.

Item Type:	Conference or Workshop Item (Unspecified)
Depositing User:	Symplectic Admin
Date Deposited:	10 Mar 2017 10:45
Last Modified:	19 Jan 2023 07:14
DOI:	10.1007/978-3-319-51963-0_30
Related URLs:	Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3006316