Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2201.12671 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915577600147456 |
|---|---|
| author | Golm, Jonas Nahvi, Mina Gabrys, Ryan Milenkovic, Olgica |
| author_facet | Golm, Jonas Nahvi, Mina Gabrys, Ryan Milenkovic, Olgica |
| contents | The $k$-deck problem is concerned with finding the smallest positive integer $S(k)$ such that there exist at least two strings of length $S(k)$ that share the same $k$-deck, i.e., the multiset of subsequences of length $k$. We introduce the new problem of gapped $k$-deck reconstruction: For a given gap parameter $s$, we seek the smallest positive integer $G_s(k)$ such that there exist at least two distinct strings of length $G_s(k)$ that cannot be distinguished based on a "gapped" set of $k$-subsequences. The gap constraint requires the elements in the subsequences to be at least $s$ positions apart within the original string. Our results are as follows. First, we show how to construct sequences sharing the same $2$-gapped $k$-deck using a nontrivial modification of the recursive Morse-Thue string construction procedure. This establishes the first known constructive upper bound on $G_2(k)$. Second, we further improve this bound using the approach by Dudik and Schulman. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2201_12671 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | The Gapped $k$-Deck Problem Golm, Jonas Nahvi, Mina Gabrys, Ryan Milenkovic, Olgica Combinatorics The $k$-deck problem is concerned with finding the smallest positive integer $S(k)$ such that there exist at least two strings of length $S(k)$ that share the same $k$-deck, i.e., the multiset of subsequences of length $k$. We introduce the new problem of gapped $k$-deck reconstruction: For a given gap parameter $s$, we seek the smallest positive integer $G_s(k)$ such that there exist at least two distinct strings of length $G_s(k)$ that cannot be distinguished based on a "gapped" set of $k$-subsequences. The gap constraint requires the elements in the subsequences to be at least $s$ positions apart within the original string. Our results are as follows. First, we show how to construct sequences sharing the same $2$-gapped $k$-deck using a nontrivial modification of the recursive Morse-Thue string construction procedure. This establishes the first known constructive upper bound on $G_2(k)$. Second, we further improve this bound using the approach by Dudik and Schulman. |
| title | The Gapped $k$-Deck Problem |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2201.12671 |