We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
On the Decidability of Infix Inclusion Problem.
- Authors
Cheon, Hyunjoon; Hahn, Joonghyuk; Han, Yo-Sub
- 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 by the need for identifying malicious computation patterns according to their semantics, which are often disguised with additional sub-patterns surrounding information. In other words, malicious patterns are embedded as an infix of the whole pattern. We examine the infix inclusion problem for the case 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 both S and T are regular, 3) EXPTIME-complete when S is context-free and T is regular, 4) undecidable when S is either regular or context-free and T is context-free and 5) undecidable when one of S and T is in a language class where the emptiness of its languages is undecidable, even if the other is finite. We, furthermore, explore the infix inclusion problem for visibly pushdown languages, a subclass of context-free languages.
- Subjects
FOREIGN language education; FORMAL languages
- Publication
Theory of Computing Systems, 2024, Vol 68, Issue 3, p301
- ISSN
1432-4350
- Publication type
Article
- DOI
10.1007/s00224-023-10160-w