Reconstruction of Multiple Strings of Constant Weight from Prefix–Suffix Compositions
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 suffic...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2025-01-01
|
| Series: | Entropy |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1099-4300/27/1/39 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832588563397476352 |
|---|---|
| author | Yaoyu Yang Zitan Chen |
| author_facet | Yaoyu Yang Zitan Chen |
| author_sort | Yaoyu Yang |
| collection | DOAJ |
| description | 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 the 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. |
| format | Article |
| id | doaj-art-8b07a1fe92ef43d08066253c330578a5 |
| institution | Kabale University |
| issn | 1099-4300 |
| language | English |
| publishDate | 2025-01-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Entropy |
| spelling | doaj-art-8b07a1fe92ef43d08066253c330578a52025-01-24T13:31:46ZengMDPI AGEntropy1099-43002025-01-012713910.3390/e27010039Reconstruction of Multiple Strings of Constant Weight from Prefix–Suffix CompositionsYaoyu Yang0Zitan Chen1School of Data Science, The Chinese University of Hong Kong, Shenzhen 518172, ChinaSchool of Science and Engineering, Future Networks of Intelligence Institute, The Chinese University of Hong Kong, Shenzhen 518172, ChinaMotivated 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 the 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.https://www.mdpi.com/1099-4300/27/1/39string reconstructionconstant-weight stringsinteger partitionDNA and polymer-based storageprefix-suffix compositions |
| spellingShingle | Yaoyu Yang Zitan Chen Reconstruction of Multiple Strings of Constant Weight from Prefix–Suffix Compositions Entropy string reconstruction constant-weight strings integer partition DNA and polymer-based storage prefix-suffix compositions |
| title | Reconstruction of Multiple Strings of Constant Weight from Prefix–Suffix Compositions |
| title_full | Reconstruction of Multiple Strings of Constant Weight from Prefix–Suffix Compositions |
| title_fullStr | Reconstruction of Multiple Strings of Constant Weight from Prefix–Suffix Compositions |
| title_full_unstemmed | Reconstruction of Multiple Strings of Constant Weight from Prefix–Suffix Compositions |
| title_short | Reconstruction of Multiple Strings of Constant Weight from Prefix–Suffix Compositions |
| title_sort | reconstruction of multiple strings of constant weight from prefix suffix compositions |
| topic | string reconstruction constant-weight strings integer partition DNA and polymer-based storage prefix-suffix compositions |
| url | https://www.mdpi.com/1099-4300/27/1/39 |
| work_keys_str_mv | AT yaoyuyang reconstructionofmultiplestringsofconstantweightfromprefixsuffixcompositions AT zitanchen reconstructionofmultiplestringsofconstantweightfromprefixsuffixcompositions |