Subsequence Covers of Words
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918136816599040 |
|---|---|
| author | Charalampopoulos, Panagiotis Pissis, Solon P. Radoszewski, Jakub Rytter, Wojciech Waleń, Tomasz Zuba, Wiktor |
| author_facet | Charalampopoulos, Panagiotis Pissis, Solon P. Radoszewski, Jakub Rytter, Wojciech Waleń, Tomasz Zuba, Wiktor |
| contents | 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.
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]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_05827 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Subsequence Covers of Words Charalampopoulos, Panagiotis Pissis, Solon P. Radoszewski, Jakub Rytter, Wojciech Waleń, Tomasz Zuba, Wiktor Data Structures and Algorithms 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. 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]. |
| title | Subsequence Covers of Words |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2509.05827 |