TY - GEN

T1 - The Gapped k-Deck Problem

AU - Golm, Rebecca

AU - Nahvi, Mina

AU - Gabrys, Ryan

AU - Milenkovic, Olgica

N1 - Funding Information:
The work was funded by NSF grant 2008125, Coded String Reconstruction Problems in Molecular Storage. In the author list, ; denotes equal contribution.
Publisher Copyright:
© 2022 IEEE.

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 -