Reconstruction of multiple strings of constant weight from prefix-suffix compositions

2024/11/06 by Yaoyu Yang, Yang, Yaoyu, Zitan Chen +1
Computer Science · #Algorithms and Data Compression #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Information Theory (cs.IT) #Natural Language Processing Techniques #Speech Recognition and Synthesis

paper · pdf · doi:10.48550/arxiv.2411.03776

openalex publication_date 2024/11/06 · openalex created_date 2024/11/15 · openalex updated_date 2026/07/28

Abstract

Motivated by studies of data retrieval in polymer-based storage systems, we consider the problem of reconstructing a multiset of binary strings that have the same length and the same weight from the compositions of their prefixes and suffixes of every possible length. We provide necessary and sufficient conditions for which unique reconstruction up to reversal of the strings is possible. Additionally, we present two algorithms for reconstructing strings from the compositions of prefixes and suffixes of constant-length constant-weight strings.

Related

• Reconstruction of a Single String from a Part of its Composition Multiset
• Reconstructing Mixtures of Coded Strings from Prefix and Suffix Compositions
• Reconstruction of Sets of Strings from Prefix/Suffix Compositions
• Coding methods for string reconstruction from erroneous prefix-suffix compositions
• Reconstruction and Error-Correction Codes for Polymer-Based Data Storage