On Perfect Sequence Covering Arrays

Abstract

A PSCA$(v,t,\lambda )$ is a multiset of permutations of the $v$-element alphabet $\{0,\dots ,v-1\}$ such that every sequence of $t$ distinct elements of the alphabet appears in the specified order in exactly $\lambda$ of the permutations. For $v\ge t\ge 2$, we define $g(v,t)$ to be the smallest positive integer $\lambda$ such that a PSCA$(v,t,\lambda )$ exists. We show that $g(6,3)=g(7,3)=g(7,4)=2$ and $g(8,3)=3$. Using suitable permutation representations of groups we make improvements to the upper bounds on $g(v,t)$ for many values of $v\le 32$ and $3\le t\le 6$. We also prove a number of restrictions on the distribution of symbols among the columns of a PSCA.