2022-11-01
Subsequence covers of words
Publication
Publication
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., Inf. Process. Lett. 1991), but, on the other hand, much easier than the related shuffle powers (Warmuth and Haussler, J. Comput. Syst. Sci. 1984). 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. Furthermore, we complement our algorithmic results with a lower and an upper bound on the length of a longest word without non-trivial s-covers, which are both exponential in the size of the alphabet.
| Additional Metadata | |
|---|---|
| , , , , | |
| doi.org/10.1007/978-3-031-20643-6_1 | |
| Lecture Notes in Computer Science/Lecture Notes in Artificial Intelligence | |
| String Processing and Information Retrieval. SPIRE 2022 | |
| Organisation | Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands |
|
Charalampopoulos, P., Pissis, S., Radoszewski, J., Rytter, W., Waleń, T., & Zuba, W. (2022). Subsequence covers of words. In Proceedings of the International Symposium on String Processing and Information Retrieval (pp. 3–15). doi:10.1007/978-3-031-20643-6_1 |
|
