2025-07-07
Subsequence covers of words
Publication
Publication
Theoretical Computer Science , Volume 1041 p. 115216:1- 115216:14
We introduce subsequence covers (s-covers, in short), a new type of covers of a word. A word C is an s-cover of a word S if the occurrences of C in S as subsequences cover all the positions in S. The s-covers seem to be computationally much harder than standard covers of words (cf. Apostolico et al. (1991) [1]), but, on the other hand, much easier than the related shuffle powers (Warmuth and Haussler (1984) [6]). We give a linear-time algorithm for testing if a candidate word C is an s-cover of a word S over a polynomially-bounded integer alphabet. We also give an algorithm for finding a shortest s-cover of a word S, which in the case of a constant-sized alphabet, also runs in linear time. The words without proper s-cover are called s-primitive. We complement our algorithmic results with explicit lower and an upper bound on the length of a longest s-primitive word. Both bounds are exponential in the size of the alphabet. The upper bound presented here improves the bound given in the conference version of this paper [SPIRE 2022].
Additional Metadata | |
---|---|
, , , , | |
doi.org/10.1016/j.tcs.2025.115216 | |
Theoretical Computer Science | |
Organisation | Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands |
Charalampopoulos, P., Pissis, S., Radoszewski, J., Rytter, W., Waleń, T., & Zuba, W. (2025). Subsequence covers of words. Theoretical Computer Science, 1041, 115216:1–115216:14. doi:10.1016/j.tcs.2025.115216 |