The relative edit-distance between two input-driven languages

Hyunjoon Cheon; Yo Sub Han; Sang Ki Ko; Kai Salomaa

doi:10.1007/978-3-030-24886-4_9

The relative edit-distance between two input-driven languages

Hyunjoon Cheon, Yo Sub Han, Sang Ki Ko, Kai Salomaa

College of Computing

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

4 Citations (Scopus)

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.

Original language	English
Title of host publication	Developments in Language Theory - 23rd International Conference, DLT 2019, Proceedings
Editors	Piotrek Hofman, Michał Skrzypczak
Publisher	Springer Verlag
Pages	127-139
Number of pages	13
ISBN (Print)	9783030248857
DOIs	https://doi.org/10.1007/978-3-030-24886-4_9
Publication status	Published - 2019
Event	23rd International Conference on Developments in Language Theory, DLT 2019 - Warsaw, Poland Duration: 2019 Aug 5 → 2019 Aug 9

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	11647 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	23rd International Conference on Developments in Language Theory, DLT 2019
Country/Territory	Poland
City	Warsaw
Period	19/8/5 → 19/8/9

Bibliographical note

Publisher Copyright:
© 2019, Springer Nature Switzerland AG.

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-030-24886-4_9

Cite this

Cheon, H., Han, Y. S., Ko, S. K., & Salomaa, K. (2019). The relative edit-distance between two input-driven languages. In P. Hofman, & M. Skrzypczak (Eds.), Developments in Language Theory - 23rd International Conference, DLT 2019, Proceedings (pp. 127-139). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11647 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-030-24886-4_9

Cheon, Hyunjoon ; Han, Yo Sub ; Ko, Sang Ki et al. / The relative edit-distance between two input-driven languages. Developments in Language Theory - 23rd International Conference, DLT 2019, Proceedings. editor / Piotrek Hofman ; Michał Skrzypczak. Springer Verlag, 2019. pp. 127-139 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{3189ceb2e9df43939a028a5b874ba49c,

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

}

Cheon, H, Han, YS, Ko, SK & Salomaa, K 2019, The relative edit-distance between two input-driven languages. in P Hofman & M Skrzypczak (eds), Developments in Language Theory - 23rd International Conference, DLT 2019, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11647 LNCS, Springer Verlag, pp. 127-139, 23rd International Conference on Developments in Language Theory, DLT 2019, Warsaw, Poland, 19/8/5. https://doi.org/10.1007/978-3-030-24886-4_9

The relative edit-distance between two input-driven languages. / Cheon, Hyunjoon; Han, Yo Sub; Ko, Sang Ki et al.
Developments in Language Theory - 23rd International Conference, DLT 2019, Proceedings. ed. / Piotrek Hofman; Michał Skrzypczak. Springer Verlag, 2019. p. 127-139 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11647 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - The relative edit-distance between two input-driven languages

AU - Cheon, Hyunjoon

AU - Han, Yo Sub

AU - Ko, Sang Ki

AU - Salomaa, Kai

PY - 2019

Y1 - 2019

N2 - 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.

AB - 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.

KW - Algorithm

KW - Complexity

KW - Decidability

KW - Edit-distance

KW - Input-driven languages

KW - Visibly pushdown languages

UR - http://www.scopus.com/inward/record.url?scp=85073906254&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85073906254&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-24886-4_9

DO - 10.1007/978-3-030-24886-4_9

M3 - Conference contribution

AN - SCOPUS:85073906254

SN - 9783030248857

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 127

EP - 139

BT - Developments in Language Theory - 23rd International Conference, DLT 2019, Proceedings

A2 - Hofman, Piotrek

A2 - Skrzypczak, Michał

PB - Springer Verlag

T2 - 23rd International Conference on Developments in Language Theory, DLT 2019

Y2 - 5 August 2019 through 9 August 2019

ER -

Cheon H, Han YS, Ko SK, Salomaa K. The relative edit-distance between two input-driven languages. In Hofman P, Skrzypczak M, editors, Developments in Language Theory - 23rd International Conference, DLT 2019, Proceedings. Springer Verlag. 2019. p. 127-139. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-24886-4_9

The relative edit-distance between two input-driven languages

Abstract

Publication series

Conference

Bibliographical note

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this