Computing the Shortest String and the Edit-Distance for Parsing Expression Languages

Hyunjoon Cheon; Yo Sub Han

doi:10.1007/978-3-030-48516-0_4

Computing the Shortest String and the Edit-Distance for Parsing Expression Languages

Hyunjoon Cheon, Yo Sub Han

College of Computing

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

3 Citations (Scopus)

Abstract

A distance between two languages is a useful tool to measure the language similarity, and is closely related to the intersection problem as well as the shortest string problem. A parsing expression grammar (PEG) is an unambiguous grammar such that the choice operator selects the first matching in PEG while it can be ambiguous in a context-free grammar. PEGs are also closely related to top-down parsing languages. We consider two problems on parsing expression languages (PELs). One is the r-shortest string problem that decides whether or not a given PEL contains a string of length shorter than r. The other problem is the edit-distance problem of PELs with respect to other language families such as finite languages or regular languages. We show that the r-shortest string problem and the edit-distance problem with respect to finite languages are NEXPTIME-complete, and the edit-distance problem with respect to regular languages is undecidable. In addition, we prove that it is impossible to compute a length bound B(G) of a PEG G such that L(G) has a string w of length at most B(G).

Original language	English
Title of host publication	Developments in Language Theory - 24th International Conference, DLT 2020, Proceedings
Editors	Nataša Jonoska, Dmytro Savchuk
Publisher	Springer
Pages	43-54
Number of pages	12
ISBN (Print)	9783030485153
DOIs	https://doi.org/10.1007/978-3-030-48516-0_4
Publication status	Published - 2020
Event	24th International Conference on Developments in Language Theory, DLT 2020 - Tampa, United States Duration: 2020 May 11 → 2020 May 15

Publication series

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

Conference

Conference	24th International Conference on Developments in Language Theory, DLT 2020
Country/Territory	United States
City	Tampa
Period	20/5/11 → 20/5/15

Bibliographical note

Publisher Copyright:
© Springer Nature Switzerland AG 2020.

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-030-48516-0_4

Cite this

Cheon, H., & Han, Y. S. (2020). Computing the Shortest String and the Edit-Distance for Parsing Expression Languages. In N. Jonoska, & D. Savchuk (Eds.), Developments in Language Theory - 24th International Conference, DLT 2020, Proceedings (pp. 43-54). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12086 LNCS). Springer. https://doi.org/10.1007/978-3-030-48516-0_4

Cheon, Hyunjoon ; Han, Yo Sub. / Computing the Shortest String and the Edit-Distance for Parsing Expression Languages. Developments in Language Theory - 24th International Conference, DLT 2020, Proceedings. editor / Nataša Jonoska ; Dmytro Savchuk. Springer, 2020. pp. 43-54 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{1df85dc5b68b486683f823eb4367c09f,

title = "Computing the Shortest String and the Edit-Distance for Parsing Expression Languages",

abstract = "A distance between two languages is a useful tool to measure the language similarity, and is closely related to the intersection problem as well as the shortest string problem. A parsing expression grammar (PEG) is an unambiguous grammar such that the choice operator selects the first matching in PEG while it can be ambiguous in a context-free grammar. PEGs are also closely related to top-down parsing languages. We consider two problems on parsing expression languages (PELs). One is the r-shortest string problem that decides whether or not a given PEL contains a string of length shorter than r. The other problem is the edit-distance problem of PELs with respect to other language families such as finite languages or regular languages. We show that the r-shortest string problem and the edit-distance problem with respect to finite languages are NEXPTIME-complete, and the edit-distance problem with respect to regular languages is undecidable. In addition, we prove that it is impossible to compute a length bound B(G) of a PEG G such that L(G) has a string w of length at most B(G).",

keywords = "Edit-distance, Formal languages, Parsing expression grammars",

author = "Hyunjoon Cheon and Han, {Yo Sub}",

note = "Publisher Copyright: {\textcopyright} Springer Nature Switzerland AG 2020.; 24th International Conference on Developments in Language Theory, DLT 2020 ; Conference date: 11-05-2020 Through 15-05-2020",

year = "2020",

doi = "10.1007/978-3-030-48516-0_4",

language = "English",

isbn = "9783030485153",

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

publisher = "Springer",

pages = "43--54",

editor = "Nata{\v s}a Jonoska and Dmytro Savchuk",

booktitle = "Developments in Language Theory - 24th International Conference, DLT 2020, Proceedings",

}

Cheon, H & Han, YS 2020, Computing the Shortest String and the Edit-Distance for Parsing Expression Languages. in N Jonoska & D Savchuk (eds), Developments in Language Theory - 24th International Conference, DLT 2020, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12086 LNCS, Springer, pp. 43-54, 24th International Conference on Developments in Language Theory, DLT 2020, Tampa, United States, 20/5/11. https://doi.org/10.1007/978-3-030-48516-0_4

Computing the Shortest String and the Edit-Distance for Parsing Expression Languages. / Cheon, Hyunjoon; Han, Yo Sub.
Developments in Language Theory - 24th International Conference, DLT 2020, Proceedings. ed. / Nataša Jonoska; Dmytro Savchuk. Springer, 2020. p. 43-54 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12086 LNCS).

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

TY - GEN

T1 - Computing the Shortest String and the Edit-Distance for Parsing Expression Languages

AU - Cheon, Hyunjoon

AU - Han, Yo Sub

N1 - Publisher Copyright: © Springer Nature Switzerland AG 2020.

PY - 2020

Y1 - 2020

N2 - A distance between two languages is a useful tool to measure the language similarity, and is closely related to the intersection problem as well as the shortest string problem. A parsing expression grammar (PEG) is an unambiguous grammar such that the choice operator selects the first matching in PEG while it can be ambiguous in a context-free grammar. PEGs are also closely related to top-down parsing languages. We consider two problems on parsing expression languages (PELs). One is the r-shortest string problem that decides whether or not a given PEL contains a string of length shorter than r. The other problem is the edit-distance problem of PELs with respect to other language families such as finite languages or regular languages. We show that the r-shortest string problem and the edit-distance problem with respect to finite languages are NEXPTIME-complete, and the edit-distance problem with respect to regular languages is undecidable. In addition, we prove that it is impossible to compute a length bound B(G) of a PEG G such that L(G) has a string w of length at most B(G).

AB - A distance between two languages is a useful tool to measure the language similarity, and is closely related to the intersection problem as well as the shortest string problem. A parsing expression grammar (PEG) is an unambiguous grammar such that the choice operator selects the first matching in PEG while it can be ambiguous in a context-free grammar. PEGs are also closely related to top-down parsing languages. We consider two problems on parsing expression languages (PELs). One is the r-shortest string problem that decides whether or not a given PEL contains a string of length shorter than r. The other problem is the edit-distance problem of PELs with respect to other language families such as finite languages or regular languages. We show that the r-shortest string problem and the edit-distance problem with respect to finite languages are NEXPTIME-complete, and the edit-distance problem with respect to regular languages is undecidable. In addition, we prove that it is impossible to compute a length bound B(G) of a PEG G such that L(G) has a string w of length at most B(G).

KW - Edit-distance

KW - Formal languages

KW - Parsing expression grammars

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

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

U2 - 10.1007/978-3-030-48516-0_4

DO - 10.1007/978-3-030-48516-0_4

M3 - Conference contribution

AN - SCOPUS:85086181563

SN - 9783030485153

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

SP - 43

EP - 54

BT - Developments in Language Theory - 24th International Conference, DLT 2020, Proceedings

A2 - Jonoska, Nataša

A2 - Savchuk, Dmytro

PB - Springer

T2 - 24th International Conference on Developments in Language Theory, DLT 2020

Y2 - 11 May 2020 through 15 May 2020

ER -

Cheon H, Han YS. Computing the Shortest String and the Edit-Distance for Parsing Expression Languages. In Jonoska N, Savchuk D, editors, Developments in Language Theory - 24th International Conference, DLT 2020, Proceedings. Springer. 2020. p. 43-54. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-48516-0_4

Computing the Shortest String and the Edit-Distance for Parsing Expression Languages

Abstract

Publication series

Conference

Bibliographical note

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this