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