{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/120117"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/120117","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"The gapped k-deck problem","abstract":"Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2023-09-01 without embargo terms","abstract_html":"Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2023-09-01 without embargo terms","abstract_has_math":false,"creators":["Golm, Rebecca"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Electrical & Computer Engr","degree_department":null,"school":null,"contributors":["Milenkovic, Olgica"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2023,"date_issued":"2023-05","date_published":"2023-05","updated_at":"2026-07-22T22:24:56Z","subjects":["Gapped Subsequences","K-deck","Morse-thue Sequences","String Reconstruction"],"languages":["en","eng"],"rights":["Copyright 2023 Rebecca Golm"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/2142/120117","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Milenkovic, Olgica"]},{"key":"dc:creator","label":"Author","values":["Golm, Rebecca"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2023-05","2023-05-01"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical & Computer Engr"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Gapped Subsequences","K-deck","Morse-thue Sequences","String Reconstruction"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en","eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2023 Rebecca Golm"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://hdl.handle.net/2142/120117"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2023-09-01 without embargo terms","The student, Rebecca Golm, accepted the attached license on 2023-04-26 at 16:54.","The student, Rebecca Golm, submitted this Thesis for approval on 2023-04-26 at 16:55.","This Thesis was approved for publication on 2023-05-01 at 17:29.","DSpace SAF Submission Ingestion Package generated from Vireo submission #19200 on 2023-09-01 at 16:55:38","Reconstructing an unknown string from information about its subsequences is known as the string reconstruction problem and has applications in many different contexts such as bioinformatics and computer science. We study the $k$-deck problem, 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 dicuss some properties of the ``padded\"-Morse-Thue sequence. Lastly, we improve the bound on $G_2(k)$ using the approach by Dudik and Schulman."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["The gapped k-deck problem"]}]}],"canonical_facts":{"dc:contributor":["Milenkovic, Olgica"],"dc:creator":["Golm, Rebecca"],"dc:date":["2023-05","2023-05-01"],"dc:description":["Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2023-09-01 without embargo terms","The student, Rebecca Golm, accepted the attached license on 2023-04-26 at 16:54.","The student, Rebecca Golm, submitted this Thesis for approval on 2023-04-26 at 16:55.","This Thesis was approved for publication on 2023-05-01 at 17:29.","DSpace SAF Submission Ingestion Package generated from Vireo submission #19200 on 2023-09-01 at 16:55:38","Reconstructing an unknown string from information about its subsequences is known as the string reconstruction problem and has applications in many different contexts such as bioinformatics and computer science. We study the $k$-deck problem, 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 dicuss some properties of the ``padded\"-Morse-Thue sequence. Lastly, we improve the bound on $G_2(k)$ using the approach by Dudik and Schulman."],"dc:format":["application/pdf"],"dc:identifier":["https://hdl.handle.net/2142/120117"],"dc:language":["en","eng"],"dc:rights":["Copyright 2023 Rebecca Golm"],"dc:subject":["Gapped Subsequences","K-deck","Morse-thue Sequences","String Reconstruction"],"dc:title":["The gapped k-deck problem"],"dc:type":["text"],"thesis:degree_discipline":["Electrical & Computer Engr"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:56Z"}