TY - GEN
T1 - The Gapped k-Deck Problem
AU - Golm, Rebecca
AU - Nahvi, Mina
AU - Gabrys, Ryan
AU - Milenkovic, Olgica
N1 - The work was funded by NSF grant 2008125, Coded String Reconstruction Problems in Molecular Storage. In the author list, ; denotes equal contribution.
PY - 2022
Y1 - 2022
N2 - 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 Gs(k) such that there exist at least two distinct strings of length Gs(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 G2(k). Second, we further improve this bound using the approach by Dudik and Schulman [6].
AB - 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 Gs(k) such that there exist at least two distinct strings of length Gs(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 G2(k). Second, we further improve this bound using the approach by Dudik and Schulman [6].
KW - Gapped subsequences
KW - Morse-Thue sequences
KW - String reconstruction
KW - k-deck
UR - http://www.scopus.com/inward/record.url?scp=85136314237&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85136314237&partnerID=8YFLogxK
U2 - 10.1109/ISIT50566.2022.9834537
DO - 10.1109/ISIT50566.2022.9834537
M3 - Conference contribution
AN - SCOPUS:85136314237
T3 - IEEE International Symposium on Information Theory - Proceedings
SP - 49
EP - 54
BT - 2022 IEEE International Symposium on Information Theory, ISIT 2022
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2022 IEEE International Symposium on Information Theory, ISIT 2022
Y2 - 26 June 2022 through 1 July 2022
ER -