论文标题
从其组成的一部分重建一个字符串
Reconstruction of a Single String from a Part of its Composition Multiset
论文作者
论文摘要
由在基于聚合物的数据存储中应用的激励，我们研究了从其组成多组的一部分重建字符串的问题。我们全面描述了无法从其所有前缀 - 苏联组成的多组中重建的字符串结构（直至逆转）。利用此描述，我们证明，对于所有$ n \ ge 6 $，存在一串长度$ n $的字符串，这些$ n $无法独特地重建以逆转。此外，对于所有$ n \ ge 6 $，我们明确地构造了由所有长度$ n $ strings组成的集合，这些组合可以独特地重建以逆转。作为产品，我们可以获得可以使用Dyck Strings和Catalan-Bertrand Strings构建任何二进制字符串。 对于任何给定的字符串$ \ bm {s} $，我们提供了一种方法来显式构建具有与$ \ bm {s} $的相同前缀suffix-suffix构图多组的所有字符串的集合，以及该集合大小的公式。作为应用程序，我们构建了最大尺寸的组成代码。此外，我们构建了两类的组成代码，它们可以分别纠正缺失错误和质量减少替换错误的组成代码。 此外，我们提出了两个新问题：当丢失数量恒定数量的底带组成时，从其组成多组中重建一根字符串；当仅赋予其长度为$ r $的长度的基因组成时，重建字符串。对于这些设置中的每一个，我们在某些条件下提供了适当的代码。
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 the structure of the strings that cannot be uniquely reconstructed (up to reversal) from their multiset of all of their prefix-suffix compositions. Leveraging this description, we prove that for all $n\ge 6$, there exists a string of length $n$ that cannot be uniquely reconstructed up to reversal. Moreover, for all $n\ge 6$, we explicitly construct the set consisting of all length $n$ strings that can be uniquely reconstructed up to reversal. As a by product, we obtain that any binary string can be constructed using Dyck strings and Catalan-Bertrand strings. For any given string $\bm{s}$, we provide a method to explicitly construct the set of all strings with the same prefix-suffix composition multiset as $\bm{s}$, as well as a formula for the size of this set. As an application, we construct a composition code of maximal size. Furthermore, we construct two classes of composition codes which can respectively correct composition missing errors and mass reducing substitution errors. In addition, we raise two new problems: reconstructing a string from its composition multiset when at most a constant number of substring compositions are lost; reconstructing a string when only given its compositions of substrings of length at most $r$. For each of these setups, we give suitable codes under some conditions.
