论文标题
从右键单词重建单词
Reconstructing Words from Right-Bounded-Block Words
论文作者
论文摘要
来自分散因素的单词的重建问题要求提供最小的信息，例如给定长度的分散因子的多集或给定集合中分散因子的发生数量，是独特地确定单词的必要条件。我们表明，可以从最多$ \ min（| w | _a，| w | _b）+ 1 $零散因子$ a^{i^{i^{i} b $中重建一个单词$ w \ in \ {a，a，b \}^{*} $。此外，我们将结果概括到表单$ \ {1，\ ldots，q \} $的字母中，显示最多最多$ \ sum^{q-1} _ {i = 1} | w | _i（q-i+1）$零散的因子可以重建$ w $。到目前为止，这两种结果都在已知的上限上有所改善。这里还考虑了重建算法的复杂时间界限。
A reconstruction problem of words from scattered factors asks for the minimal information, like multisets of scattered factors of a given length or the number of occurrences of scattered factors from a given set, necessary to uniquely determine a word. We show that a word $w \in \{a, b\}^{*}$ can be reconstructed from the number of occurrences of at most $\min(|w|_a, |w|_b)+ 1$ scattered factors of the form $a^{i} b$. Moreover, we generalize the result to alphabets of the form $\{1,\ldots,q\}$ by showing that at most $ \sum^{q-1}_{i=1} |w|_i (q-i+1)$ scattered factors suffices to reconstruct $w$. Both results improve on the upper bounds known so far. Complexity time bounds on reconstruction algorithms are also considered here.
