@inproceedings{b7ec8b55ca1940bea1516d407961f73d,

title = "The relative edit-distance between two input-driven languages",

abstract = "We study the relative edit-distance problem between two input-driven languages. The relative edit-distance is closely related to the language inclusion problem, which is a crucial problem in formal verification. Input-driven languages are a robust subclass of context-free languages that enable to model program analysis questions within tractable time complexity. For instance, the language inclusion (or equivalence) problem is undecidable for context-free languages whereas the problem is solvable in polynomial time for input-driven languages specified by deterministic input-driven pushdown automata (IDPDAs) and is EXPTIME-complete for nondeterministic IDPDAs. Our main contribution is to prove that the relative edit-distance problem for two input-driven languages is decidable by designing a polynomial time IDPDA construction, based on the edit-distance, that recognizes a neighbourhood of a given input-driven language. In fact, the relative edit-distance problem between two input-driven languages turns out to be EXPTIME-complete when the neighbourhood distance threshold is fixed as a constant.",

keywords = "Algorithm, Complexity, Decidability, Edit-distance, Input-driven languages, Visibly pushdown languages",

author = "Hyunjoon Cheon and Han, {Yo Sub} and Ko, {Sang Ki} and Kai Salomaa",

note = "Publisher Copyright: {\textcopyright} 2019, Springer Nature Switzerland AG.; 23rd International Conference on Developments in Language Theory, DLT 2019 ; Conference date: 05-08-2019 Through 09-08-2019",

year = "2019",

doi = "10.1007/978-3-030-24886-4_9",

language = "English",

isbn = "9783030248857",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "127--139",

editor = "Piotrek Hofman and Micha{\l} Skrzypczak",

booktitle = "Developments in Language Theory - 23rd International Conference, DLT 2019, Proceedings",

address = "Germany",

}