@inproceedings{10.1007/978-3-031-05578-2_9,
    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.},
    Address = {Berlin, Heidelberg},
    Author = {Cheon, Hyunjoon and Hahn, Joonghyuk and Han, Yo-Sub},
    BookTitle = {Developments in Language Theory: 26th International Conference, DLT 2022, Tampa, FL, USA, May 9--13, 2022, Proceedings},
    ISBN = {978-3-031-05577-5},
    Keywords = {Decidability, Regular languages, Context-free languages, Infix inclusion},
    Location = {Tampa, FL, USA},
    Pages = {115--126},
    Publisher = {Springer-Verlag},
    Title = {On The Decidability Of Infix Inclusion Problem},
    URL = {https://doi.org/10.1007/978-3-031-05578-2\_9},
    Year = {2022},
    bdsk-url-1 = {https://doi.org/10.1007/978-3-031-05578-2\_9},
    date-added = {2023-05-26 11:37:06 +0200},
    date-modified = {2023-05-26 11:38:40 +0200},
    numpages = {12},
    doi = {10.1007/978-3-031-05578-2_9}
}

@inproceedings{10.1007/978-3-031-05578-2_9, 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.}, Address = {Berlin, Heidelberg}, Author = {Cheon, Hyunjoon and Hahn, Joonghyuk and Han, Yo-Sub}, BookTitle = {Developments in Language Theory: 26th International Conference, DLT 2022, Tampa, FL, USA, May 9--13, 2022, Proceedings}, ISBN = {978-3-031-05577-5}, Keywords = {Decidability, Regular languages, Context-free languages, Infix inclusion}, Location = {Tampa, FL, USA}, Pages = {115--126}, Publisher = {Springer-Verlag}, Title = {On The Decidability Of Infix Inclusion Problem}, URL = {https://doi.org/10.1007/978-3-031-05578-2_9}, Year = {2022}, bdsk-url-1 = {https://doi.org/10.1007/978-3-031-05578-2_9}, date-added = {2023-05-26 11:37:06 +0200}, date-modified = {2023-05-26 11:38:40 +0200}, numpages = {12}, doi = {10.1007/978-3-031-05578-2_9} }