Edit-distance between visibly pushdown languages

Yo Sub Han; Sang Ki Ko

doi:10.1007/978-3-319-51963-0_30

Edit-distance between visibly pushdown languages

Yo Sub Han, Sang Ki Ko

College of Computing

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

6 Citations (Scopus)

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.

Original language	English
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
Publisher	Springer Verlag
Pages	387-401
Number of pages	15
ISBN (Print)	9783319519623
DOIs	https://doi.org/10.1007/978-3-319-51963-0_30
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

Publication series

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

Other

Other	43rd Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2017
Country/Territory	Ireland
City	Limerick
Period	17/1/16 → 17/1/20

Bibliographical note

Publisher Copyright:
© Springer International Publishing AG 2017.

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-319-51963-0_30

Cite this

Han, Y. S., & Ko, S. K. (2017). Edit-distance between visibly pushdown languages. In C. Baier, M. van den Brand, J. Eder, M. Hinchey, T. Margaria, & B. Steffen (Eds.), SOFSEM 2017: Theory and Practice of Computer Science - 43rd International Conference on Current Trends in Theory and Practice of Computer Science, Proceedings (pp. 387-401). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10139 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-51963-0_30

Han, Yo Sub ; Ko, Sang Ki. / Edit-distance between visibly pushdown languages. SOFSEM 2017: Theory and Practice of Computer Science - 43rd International Conference on Current Trends in Theory and Practice of Computer Science, Proceedings. editor / Christel Baier ; Mark van den Brand ; Johann Eder ; Mike Hinchey ; Tiziana Margaria ; Bernhard Steffen. Springer Verlag, 2017. pp. 387-401 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{fff1b597be47422cbf1850f5db5e32e5,

title = "Edit-distance between visibly pushdown languages",

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

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

author = "Han, {Yo Sub} and Ko, {Sang Ki}",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing AG 2017.; 43rd Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2017 ; Conference date: 16-01-2017 Through 20-01-2017",

year = "2017",

doi = "10.1007/978-3-319-51963-0_30",

language = "English",

isbn = "9783319519623",

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

publisher = "Springer Verlag",

pages = "387--401",

editor = "Christel Baier and {van den Brand}, Mark and Johann Eder and Mike Hinchey and Tiziana Margaria and Bernhard Steffen",

booktitle = "SOFSEM 2017",

address = "Germany",

}

Han, YS & Ko, SK 2017, Edit-distance between visibly pushdown languages. in C Baier, M van den Brand, J Eder, M Hinchey, T Margaria & B Steffen (eds), SOFSEM 2017: Theory and Practice of Computer Science - 43rd International Conference on Current Trends in Theory and Practice of Computer Science, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10139 LNCS, Springer Verlag, pp. 387-401, 43rd Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2017, Limerick, Ireland, 17/1/16. https://doi.org/10.1007/978-3-319-51963-0_30

Edit-distance between visibly pushdown languages. / Han, Yo Sub; Ko, Sang Ki.
SOFSEM 2017: Theory and Practice of Computer Science - 43rd International Conference on Current Trends in Theory and Practice of Computer Science, Proceedings. ed. / Christel Baier; Mark van den Brand; Johann Eder; Mike Hinchey; Tiziana Margaria; Bernhard Steffen. Springer Verlag, 2017. p. 387-401 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10139 LNCS).

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

TY - GEN

T1 - Edit-distance between visibly pushdown languages

AU - Han, Yo Sub

AU - Ko, Sang Ki

N1 - Publisher Copyright: © Springer International Publishing AG 2017.

PY - 2017

Y1 - 2017

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

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

KW - Algorithm

KW - Decidability

KW - Edit-distance

KW - Visibly pushdown languages

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

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

U2 - 10.1007/978-3-319-51963-0_30

DO - 10.1007/978-3-319-51963-0_30

M3 - Conference contribution

AN - SCOPUS:85010653608

SN - 9783319519623

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

SP - 387

EP - 401

BT - SOFSEM 2017

A2 - Baier, Christel

A2 - van den Brand, Mark

A2 - Eder, Johann

A2 - Hinchey, Mike

A2 - Margaria, Tiziana

A2 - Steffen, Bernhard

PB - Springer Verlag

T2 - 43rd Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2017

Y2 - 16 January 2017 through 20 January 2017

ER -

Han YS, Ko SK. Edit-distance between visibly pushdown languages. In Baier C, van den Brand M, Eder J, Hinchey M, Margaria T, Steffen B, editors, SOFSEM 2017: Theory and Practice of Computer Science - 43rd International Conference on Current Trends in Theory and Practice of Computer Science, Proceedings. Springer Verlag. 2017. p. 387-401. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-51963-0_30

Edit-distance between visibly pushdown languages

Abstract

Publication series

Other

Bibliographical note

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this