论文标题
基于组的完美序列覆盖阵列的结构
A group-based structure for perfect sequence covering arrays
论文作者
论文摘要
$（n，k）$ - 完美的序列覆盖具有多重$λ$的阵列，表示为psca $（n，k，λ）$，是一个多序列，其元素是序列$ $（1,2，\ dots，n）$的元素，并且共同包含每个订单的长度$ k $ k $ secepence $ k $ secepence $λ$λ$ times。主要目的是确定每对$（n，k）$的最小值$λ$，表示为$ g（n，k）$，其中psca $（n，k，λ）$存在；更一般而言，存在PSCA $（N，K，λ）$的完整值$λ$。 Yuster最近确定了$ g（n，k）$大于1的第一个已知价值，即$ g（5,3）= 2 $，并建议找到其他此类价值将具有挑战性。我们表明，使用Mathon引起的旧算法启发的递归搜索方法，$ g（6,3）= g（7,3）= 2 $。然后，我们将基于小组的结构限制在覆盖数组的完美序列上，将其限制为对称组的规定非平凡子组的独特摇摆的结合。这使我们能够确定$ g（7,4）= 2 $和$ g（7,5）\ in \ {2,3,4 \} $和$ g（8,3）\ in \ {2,3 \} $和$ g（9,3）\ in \ in \ in \ {2,3,4 \} $。我们还表明，对于每个$（n，k）\ in \ {（5,3），（6,3），（7,3），（7,4），（7,4）\} $，存在PSCA $（N，K，λ）$时，仅当$λ\ ge 2 $;当时存在PSCA $（8,3，λ）$的情况，并且仅当$λ\ ge g（8,3）$时。
An $(n,k)$-perfect sequence covering array with multiplicity $λ$, denoted PSCA$(n,k,λ)$, is a multiset whose elements are permutations of the sequence $(1,2, \dots, n)$ and which collectively contain each ordered length $k$ subsequence exactly $λ$ times. The primary objective is to determine for each pair $(n,k)$ the smallest value of $λ$, denoted $g(n,k)$, for which a PSCA$(n,k,λ)$ exists; and more generally, the complete set of values $λ$ for which a PSCA$(n,k,λ)$ exists. Yuster recently determined the first known value of $g(n,k)$ greater than 1, namely $g(5,3)=2$, and suggested that finding other such values would be challenging. We show that $g(6,3)=g(7,3)=2$, using a recursive search method inspired by an old algorithm due to Mathon. We then impose a group-based structure on a perfect sequence covering array by restricting it to be a union of distinct cosets of a prescribed nontrivial subgroup of the symmetric group $S_n$. This allows us to determine the new results that $g(7,4)=2$ and $g(7,5) \in \{2,3,4\}$ and $g(8,3) \in \{2,3\}$ and $g(9,3) \in \{2,3,4\}$. We also show that, for each $(n,k) \in \{ (5,3), (6,3), (7,3), (7,4) \}$, there exists a PSCA$(n,k,λ)$ if and only if $λ\ge 2$; and that there exists a PSCA$(8,3,λ)$ if and only if $λ\ge g(8,3)$.
