On the Decidability of Infix Inclusion Problem

Hyunjoon Cheon; Joonghyuk Hahn; Yo Sub Han

doi:10.1007/978-3-031-05578-2_9

On the Decidability of Infix Inclusion Problem

Hyunjoon Cheon, Joonghyuk Hahn, Yo Sub Han

College of Computing

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

1 Citation (Scopus)

Abstract

We introduce the infix inclusion problem of two languages S and T that decides whether or not S is a subset of the set of all infixes of T. This problem is motivated from intrusion detection systems that identify malicious patterns according to their semantics, which are often disguised with additional information surrounding the patterns. In other words, malicious patterns are embedded as an infix of the whole patterns. We examine the infix inclusion problem, where a source S and a target T are finite, regular or context-free languages. We prove that the problem is 1) co-NP-complete when one of the languages is finite, 2) PSPACE-complete when S, T are regular, 3) EXPTIME-complete when S is context-free and T is regular and 4) undecidable for when S is either regular or context-free and T is context-free.

Original language	English
Title of host publication	Developments in Language Theory - 26th International Conference, DLT 2022, Proceedings
Editors	Volker Diekert, Mikhail Volkov
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	115-126
Number of pages	12
ISBN (Print)	9783031055775
DOIs	https://doi.org/10.1007/978-3-031-05578-2_9
Publication status	Published - 2022
Event	26th International Conference on Developments in Language Theory, DLT 2022 - Tampa, United States Duration: 2022 May 9 → 2022 May 13

Publication series

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

Conference

Conference	26th International Conference on Developments in Language Theory, DLT 2022
Country/Territory	United States
City	Tampa
Period	22/5/9 → 22/5/13

Bibliographical note

Publisher Copyright:
© 2022, Springer Nature Switzerland AG.

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-031-05578-2_9

Cite this

Cheon, H., Hahn, J., & Han, Y. S. (2022). On the Decidability of Infix Inclusion Problem. In V. Diekert, & M. Volkov (Eds.), Developments in Language Theory - 26th International Conference, DLT 2022, Proceedings (pp. 115-126). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13257 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-05578-2_9

Cheon, Hyunjoon ; Hahn, Joonghyuk ; Han, Yo Sub. / On the Decidability of Infix Inclusion Problem. Developments in Language Theory - 26th International Conference, DLT 2022, Proceedings. editor / Volker Diekert ; Mikhail Volkov. Springer Science and Business Media Deutschland GmbH, 2022. pp. 115-126 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{a549fba8bc9a4dea9ea1e0383e2525d0,

title = "On the Decidability of Infix Inclusion Problem",

abstract = "We introduce the infix inclusion problem of two languages S and T that decides whether or not S is a subset of the set of all infixes of T. This problem is motivated from intrusion detection systems that identify malicious patterns according to their semantics, which are often disguised with additional information surrounding the patterns. In other words, malicious patterns are embedded as an infix of the whole patterns. We examine the infix inclusion problem, where a source S and a target T are finite, regular or context-free languages. We prove that the problem is 1) co-NP-complete when one of the languages is finite, 2) PSPACE-complete when S, T are regular, 3) EXPTIME-complete when S is context-free and T is regular and 4) undecidable for when S is either regular or context-free and T is context-free.",

keywords = "Context-free languages, Decidability, Infix inclusion, Regular languages",

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

note = "Publisher Copyright: {\textcopyright} 2022, Springer Nature Switzerland AG.; 26th International Conference on Developments in Language Theory, DLT 2022 ; Conference date: 09-05-2022 Through 13-05-2022",

year = "2022",

doi = "10.1007/978-3-031-05578-2_9",

language = "English",

isbn = "9783031055775",

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 = "115--126",

editor = "Volker Diekert and Mikhail Volkov",

booktitle = "Developments in Language Theory - 26th International Conference, DLT 2022, Proceedings",

address = "Germany",

}

Cheon, H, Hahn, J & Han, YS 2022, On the Decidability of Infix Inclusion Problem. in V Diekert & M Volkov (eds), Developments in Language Theory - 26th International Conference, DLT 2022, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13257 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 115-126, 26th International Conference on Developments in Language Theory, DLT 2022, Tampa, United States, 22/5/9. https://doi.org/10.1007/978-3-031-05578-2_9

On the Decidability of Infix Inclusion Problem. / Cheon, Hyunjoon; Hahn, Joonghyuk; Han, Yo Sub.
Developments in Language Theory - 26th International Conference, DLT 2022, Proceedings. ed. / Volker Diekert; Mikhail Volkov. Springer Science and Business Media Deutschland GmbH, 2022. p. 115-126 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13257 LNCS).

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

TY - GEN

T1 - On the Decidability of Infix Inclusion Problem

AU - Cheon, Hyunjoon

AU - Hahn, Joonghyuk

AU - Han, Yo Sub

PY - 2022

Y1 - 2022

N2 - We introduce the infix inclusion problem of two languages S and T that decides whether or not S is a subset of the set of all infixes of T. This problem is motivated from intrusion detection systems that identify malicious patterns according to their semantics, which are often disguised with additional information surrounding the patterns. In other words, malicious patterns are embedded as an infix of the whole patterns. We examine the infix inclusion problem, where a source S and a target T are finite, regular or context-free languages. We prove that the problem is 1) co-NP-complete when one of the languages is finite, 2) PSPACE-complete when S, T are regular, 3) EXPTIME-complete when S is context-free and T is regular and 4) undecidable for when S is either regular or context-free and T is context-free.

AB - We introduce the infix inclusion problem of two languages S and T that decides whether or not S is a subset of the set of all infixes of T. This problem is motivated from intrusion detection systems that identify malicious patterns according to their semantics, which are often disguised with additional information surrounding the patterns. In other words, malicious patterns are embedded as an infix of the whole patterns. We examine the infix inclusion problem, where a source S and a target T are finite, regular or context-free languages. We prove that the problem is 1) co-NP-complete when one of the languages is finite, 2) PSPACE-complete when S, T are regular, 3) EXPTIME-complete when S is context-free and T is regular and 4) undecidable for when S is either regular or context-free and T is context-free.

KW - Context-free languages

KW - Decidability

KW - Infix inclusion

KW - Regular languages

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

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

U2 - 10.1007/978-3-031-05578-2_9

DO - 10.1007/978-3-031-05578-2_9

M3 - Conference contribution

AN - SCOPUS:85130305949

SN - 9783031055775

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

SP - 115

EP - 126

BT - Developments in Language Theory - 26th International Conference, DLT 2022, Proceedings

A2 - Diekert, Volker

A2 - Volkov, Mikhail

PB - Springer Science and Business Media Deutschland GmbH

T2 - 26th International Conference on Developments in Language Theory, DLT 2022

Y2 - 9 May 2022 through 13 May 2022

ER -

Cheon H, Hahn J, Han YS. On the Decidability of Infix Inclusion Problem. In Diekert V, Volkov M, editors, Developments in Language Theory - 26th International Conference, DLT 2022, Proceedings. Springer Science and Business Media Deutschland GmbH. 2022. p. 115-126. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-05578-2_9