Back to Search
Start Over
Reconstruction of a Single String From a Part of Its Composition Multiset
- Source :
- IEEE Transactions on Information Theory; 2024, Vol. 70 Issue: 6 p3922-3940, 19p
- Publication Year :
- 2024
-
Abstract
- Motivated by applications in polymer-based data storage, we study the problem of reconstructing a string from part of its composition multiset. We give a full description of strings that cannot be uniquely reconstructed up to reversal from their multisets of all the prefix-suffix compositions. Leveraging this description, we prove that for all <inline-formula> <tex-math notation="LaTeX">$n \geqslant 6$ </tex-math></inline-formula>, there exists a string of length <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> that cannot be uniquely reconstructed up to reversal. Moreover, for all <inline-formula> <tex-math notation="LaTeX">$n \geqslant 6$ </tex-math></inline-formula>, we explicitly construct the set consisting of all length <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> strings that can be uniquely reconstructed up to reversal. As a byproduct, we obtain that any binary string can be constructed using Dyck strings and Catalan-Bertrand strings. For any given string <inline-formula> <tex-math notation="LaTeX">$ \mathbf {s}$ </tex-math></inline-formula>, we provide a method to explicitly construct the set of all strings with the same prefix-suffix composition multiset as <inline-formula> <tex-math notation="LaTeX">$ \mathbf {s}$ </tex-math></inline-formula>, as well as a formula for the size of this set. Furthermore, we construct two classes of composition codes that can respectively correct composition missing errors and mass-reducing substitution errors. In addition, we raise a new problem: reconstructing a string when only given its compositions of substrings of length at most <inline-formula> <tex-math notation="LaTeX">$r$ </tex-math></inline-formula>. We give suitable codes under some conditions.
Details
- Language :
- English
- ISSN :
- 00189448 and 15579654
- Volume :
- 70
- Issue :
- 6
- Database :
- Supplemental Index
- Journal :
- IEEE Transactions on Information Theory
- Publication Type :
- Periodical
- Accession number :
- ejs66457471
- Full Text :
- https://doi.org/10.1109/TIT.2023.3315784