On the Decidability of Infix Inclusion Problem

Hyunjoon Cheon, Joonghyuk Hahn, Yo Sub Han

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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 languageEnglish
Title of host publicationDevelopments in Language Theory - 26th International Conference, DLT 2022, Proceedings
EditorsVolker Diekert, Mikhail Volkov
PublisherSpringer Science and Business Media Deutschland GmbH
Number of pages12
ISBN (Print)9783031055775
Publication statusPublished - 2022
Event26th International Conference on Developments in Language Theory, DLT 2022 - Tampa, United States
Duration: 2022 May 92022 May 13

Publication series

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


Conference26th International Conference on Developments in Language Theory, DLT 2022
Country/TerritoryUnited States

Bibliographical note

Publisher Copyright:
© 2022, Springer Nature Switzerland AG.

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'On the Decidability of Infix Inclusion Problem'. Together they form a unique fingerprint.

Cite this