论文标题
$ k $ - 钉问题
The Gapped $k$-Deck Problem
论文作者
论文摘要
$ k $ - 戴克问题涉及找到最小的正整数$ s（k）$，因此至少存在两个共享相同$ k $ - deck的长度$ s（k）$的字符串，即长度$ k $的子序列。我们介绍了$ k $ -deck重建的新问题：对于给定的gap参数$ s $，我们寻求最小的正整数$ g_s（k）$，这样至少存在两个不同的长度$ g_s（k）$的条件，这些条件是基于“ gapped” $ k $ k $ subsequess无法区分的。差距约束要求子序列中的元素至少在原始字符串中与众不同。我们的结果如下。首先，我们展示了如何使用递归的莫尔斯 - 托林施工程序的非平地修改来构建共享相同$ 2 $的$ k $ deck的序列。这建立了$ g_2（k）$上的第一个已知的建设性上限。其次，我们使用杜迪克（Dudik）和舒尔曼（Schulman）的方法进一步改善了这种约束。
The $k$-deck problem is concerned with finding the smallest positive integer $S(k)$ such that there exist at least two strings of length $S(k)$ that share the same $k$-deck, i.e., the multiset of subsequences of length $k$. We introduce the new problem of gapped $k$-deck reconstruction: For a given gap parameter $s$, we seek the smallest positive integer $G_s(k)$ such that there exist at least two distinct strings of length $G_s(k)$ that cannot be distinguished based on a "gapped" set of $k$-subsequences. The gap constraint requires the elements in the subsequences to be at least $s$ positions apart within the original string. Our results are as follows. First, we show how to construct sequences sharing the same $2$-gapped $k$-deck using a nontrivial modification of the recursive Morse-Thue string construction procedure. This establishes the first known constructive upper bound on $G_2(k)$. Second, we further improve this bound using the approach by Dudik and Schulman.
