Subsequence Matching and Analysis Problems for Formal Languages

In this paper, we study a series of algorithmic problems related to subsequences occurring in the strings of a given language, under the assumption that the language is succinctly represented by a grammar. In particular, we focus on determining whether a specific string w occurs as a subsequence in some or all strings of a language L , and whether L is k -universal, that is, whether it contains strings that have all strings of length k as subsequences. In the case of regular languages, the first two problems can be solved easily and the complexity of the k -universality problems has been settled [Adamson et al., ISAAC 2023]. We extend that work to larger language classes. First we give general sufficient conditions under which these problems are decidable, based on the constructability of downward closures and intersections with regular languages for the input languages. We show that the problems are undecidable for context-sensitive languages, but can be solved efficiently for context-free languages (CFL). Specifically, we describe polynomial-time algorithmic approaches for deciding if w is a subsequence of some or all strings in a CFL, and for checking if all strings in a CFL are k -universal. For deciding if a CFL contains at least one k -universal string, which inherits NP-hardness from the regular case, we propose two fixed-parameter tractable (FPT) solutions. The first is parameterized by the size of the alphabet, extending previous work on regular languages. The second is a novel approach parameterized by the number of non-terminals in the input grammar, utilizing a tree-based structural analysis of the language.