Weak Inverse Neighborhoods of Languages

Hyunjoon Cheon; Yo Sub Han

doi:10.1007/978-3-031-33264-7_6

Weak Inverse Neighborhoods of Languages

Hyunjoon Cheon, Yo Sub Han

College of Computing

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

Abstract

While the edit-distance neighborhood is useful for approximate pattern matching, it is not suitable for the negative lookahead feature for the practical regex matching engines. This motivates us to introduce a new operation. We define the edit-distance interior operation on a language L to compute the largest subset I(L) of L such that the edit-distance neighborhood of I(L) is in L. In other words, L includes the edit-distance neighborhood of the largest edit-distance interior language. Given an edit-distance value r, we show that the radius-r edit-distance interior operation is a weak inverse of the radius-r edit-distance neighborhood operation, and vice versa. In addition, we demonstrate that regular languages are closed under the edit-distance interior operation whereas context-free languages are not. Then, we characterize the edit-distance interior languages and present a proper hierarchy with respect to the radius of operations. The family of edit-distance interior languages is closed under intersection, but not closed under union, complement and catenation.

Original language	English
Title of host publication	Developments in Language Theory - 27th International Conference, DLT 2023, Proceedings
Editors	Frank Drewes, Mikhail Volkov
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	61-73
Number of pages	13
ISBN (Print)	9783031332630
DOIs	https://doi.org/10.1007/978-3-031-33264-7_6
Publication status	Published - 2023
Event	27th International Conference on Developments in Language Theory, DLT 2023 - Umeå, Sweden Duration: 2023 Jun 12 → 2023 Jun 16

Publication series

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

Conference

Conference	27th International Conference on Developments in Language Theory, DLT 2023
Country/Territory	Sweden
City	Umeå
Period	23/6/12 → 23/6/16

Bibliographical note

Publisher Copyright:
© 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-031-33264-7_6

Cite this

Cheon, H., & Han, Y. S. (2023). Weak Inverse Neighborhoods of Languages. In F. Drewes, & M. Volkov (Eds.), Developments in Language Theory - 27th International Conference, DLT 2023, Proceedings (pp. 61-73). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13911 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-33264-7_6

Cheon, Hyunjoon ; Han, Yo Sub. / Weak Inverse Neighborhoods of Languages. Developments in Language Theory - 27th International Conference, DLT 2023, Proceedings. editor / Frank Drewes ; Mikhail Volkov. Springer Science and Business Media Deutschland GmbH, 2023. pp. 61-73 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{788b27a6b62b44daa01407705981d65e,

title = "Weak Inverse Neighborhoods of Languages",

abstract = "While the edit-distance neighborhood is useful for approximate pattern matching, it is not suitable for the negative lookahead feature for the practical regex matching engines. This motivates us to introduce a new operation. We define the edit-distance interior operation on a language L to compute the largest subset I(L) of L such that the edit-distance neighborhood of I(L) is in L. In other words, L includes the edit-distance neighborhood of the largest edit-distance interior language. Given an edit-distance value r, we show that the radius-r edit-distance interior operation is a weak inverse of the radius-r edit-distance neighborhood operation, and vice versa. In addition, we demonstrate that regular languages are closed under the edit-distance interior operation whereas context-free languages are not. Then, we characterize the edit-distance interior languages and present a proper hierarchy with respect to the radius of operations. The family of edit-distance interior languages is closed under intersection, but not closed under union, complement and catenation.",

keywords = "Edit-distance, Formal languages, Interior operation, Neighborhood languages",

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

note = "Publisher Copyright: {\textcopyright} 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.; 27th International Conference on Developments in Language Theory, DLT 2023 ; Conference date: 12-06-2023 Through 16-06-2023",

year = "2023",

doi = "10.1007/978-3-031-33264-7_6",

language = "English",

isbn = "9783031332630",

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

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "61--73",

editor = "Frank Drewes and Mikhail Volkov",

booktitle = "Developments in Language Theory - 27th International Conference, DLT 2023, Proceedings",

address = "Germany",

}

Cheon, H & Han, YS 2023, Weak Inverse Neighborhoods of Languages. in F Drewes & M Volkov (eds), Developments in Language Theory - 27th International Conference, DLT 2023, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13911 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 61-73, 27th International Conference on Developments in Language Theory, DLT 2023, Umeå, Sweden, 23/6/12. https://doi.org/10.1007/978-3-031-33264-7_6

Weak Inverse Neighborhoods of Languages. / Cheon, Hyunjoon; Han, Yo Sub.
Developments in Language Theory - 27th International Conference, DLT 2023, Proceedings. ed. / Frank Drewes; Mikhail Volkov. Springer Science and Business Media Deutschland GmbH, 2023. p. 61-73 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13911 LNCS).

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

TY - GEN

T1 - Weak Inverse Neighborhoods of Languages

AU - Cheon, Hyunjoon

AU - Han, Yo Sub

PY - 2023

Y1 - 2023

N2 - While the edit-distance neighborhood is useful for approximate pattern matching, it is not suitable for the negative lookahead feature for the practical regex matching engines. This motivates us to introduce a new operation. We define the edit-distance interior operation on a language L to compute the largest subset I(L) of L such that the edit-distance neighborhood of I(L) is in L. In other words, L includes the edit-distance neighborhood of the largest edit-distance interior language. Given an edit-distance value r, we show that the radius-r edit-distance interior operation is a weak inverse of the radius-r edit-distance neighborhood operation, and vice versa. In addition, we demonstrate that regular languages are closed under the edit-distance interior operation whereas context-free languages are not. Then, we characterize the edit-distance interior languages and present a proper hierarchy with respect to the radius of operations. The family of edit-distance interior languages is closed under intersection, but not closed under union, complement and catenation.

AB - While the edit-distance neighborhood is useful for approximate pattern matching, it is not suitable for the negative lookahead feature for the practical regex matching engines. This motivates us to introduce a new operation. We define the edit-distance interior operation on a language L to compute the largest subset I(L) of L such that the edit-distance neighborhood of I(L) is in L. In other words, L includes the edit-distance neighborhood of the largest edit-distance interior language. Given an edit-distance value r, we show that the radius-r edit-distance interior operation is a weak inverse of the radius-r edit-distance neighborhood operation, and vice versa. In addition, we demonstrate that regular languages are closed under the edit-distance interior operation whereas context-free languages are not. Then, we characterize the edit-distance interior languages and present a proper hierarchy with respect to the radius of operations. The family of edit-distance interior languages is closed under intersection, but not closed under union, complement and catenation.

KW - Edit-distance

KW - Formal languages

KW - Interior operation

KW - Neighborhood languages

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

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

U2 - 10.1007/978-3-031-33264-7_6

DO - 10.1007/978-3-031-33264-7_6

M3 - Conference contribution

AN - SCOPUS:85161231426

SN - 9783031332630

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

SP - 61

EP - 73

BT - Developments in Language Theory - 27th International Conference, DLT 2023, Proceedings

A2 - Drewes, Frank

A2 - Volkov, Mikhail

PB - Springer Science and Business Media Deutschland GmbH

T2 - 27th International Conference on Developments in Language Theory, DLT 2023

Y2 - 12 June 2023 through 16 June 2023

ER -

Cheon H, Han YS. Weak Inverse Neighborhoods of Languages. In Drewes F, Volkov M, editors, Developments in Language Theory - 27th International Conference, DLT 2023, Proceedings. Springer Science and Business Media Deutschland GmbH. 2023. p. 61-73. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-33264-7_6