A problem of reconstructing words from their subwords involves determining the minimum amount of information needed, such as multisets of scattered subwords of a specific length or the frequency of scattered subwords from a given set, in order to uniquely identify a word. In this paper we show that a cyclic word on a binary alphabet can be reconstructed by its scattered subwords of length $\frac34n+4$, and for each $n$ one can find two cyclic words of length $n$ which have the same set of scattered subwords of length $\frac34n-\frac32$.
翻译：从子词重构原词的问题涉及确定所需的最小信息量，例如特定长度的分散子词的多重集或给定集合中分散子词的频率，以唯一识别一个词。本文证明，在二元字母表上的循环词可通过其长度为$\\frac34n+4$的分散子词进行重构，并且对于每个$n$，可以找到两个长度为$n$的循环词，它们具有相同的长度为$\\frac34n-\\frac32$的分散子词集合。
微信扫码咨询专知VIP会员