Subsequence Matching and Analysis Problems for Formal Languages
<|reference_start|>Subsequence Matching and Analysis Problems for Formal Languages: In this paper, we study a series of algorithmic problems related to the subsequences occurring in the strings of a given language, under the assumption that this language is succinctly represented by a grammar generating it, or an automaton accepting it. In particular, we focus on the following problems: Given a string $w$ and a language $L$, does there exist a word of $L$ which has $w$ as subsequence? Do all words of $L$ have $w$ as a subsequence? Given an integer $k$ alongside $L$, does there exist a word of $L$ which has all strings of length $k$, over the alphabet of $L$, as subsequences? Do all words of $L$ have all strings of length $k$ as subsequences? For the last two problems, efficient algorithms were already presented in [Adamson et al., ISAAC 2023] for the case when $L$ is a regular language, and efficient solutions can be easily obtained for the first two problems. We extend that work as follows: we give sufficient conditions on the class of input-languages, under which these problems are decidable; we provide efficient algorithms for all these problems in the case when the input language is context-free; we show that all problems are undecidable for context-sensitive languages. Finally, we provide a series of initial results related to a class of languages that strictly includes the regular languages and is strictly included in the class of context-sensitive languages, but is incomparable to the of class context-free languages; these results deviate significantly from those reported for language-classes from the Chomsky hierarchy.<|reference_end|>
@article{fazekas2024subsequence,
    title={Subsequence Matching and Analysis Problems for Formal Languages},
    author={Szil'ard Zsolt Fazekas, Tore Ko{ss}, Florin Manea, Robert
  Mercac{s}, Timo Specht},
    journal={arXiv preprint arXiv:2410.07992},
    year={2024},
    archivePrefix={arXiv},
    eprint={2410.07992},
    primaryClass={cs.FL cs.DS}
}