A sequence covering array, denoted by <Emphasis FontCategory="SansSerif">SCA</Emphasis>(N; t, v), is a set of N permutations of <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\{0, \dots , v-1 \}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">{</mo> <mn>0</mn> <mo>,</mo> <mo>⋯</mo> <mo>,</mo> <mi>v</mi> <mo>-</mo> <mn>1</mn> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation> such that each sequence of t distinct elements of <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\{0, \dots , v-1\}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">{</mo> <mn>0</mn> <mo>,</mo> <mo>⋯</mo> <mo>,</mo> <mi>v</mi> <mo>-</mo> <mn>1</mn> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation> is a (not necessarily contiguous) subsequence of at least one permutation. The minimum number of permutations such a sequence covering array can have is t! and it has been conjectured that for <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$t > 4$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>t</mi> <mo>></mo> <mn>4</mn> </mrow> </math></EquationSource> </InlineEquation>, if a sequence covering array with t! permutations exists, then <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$v \in \{t,t+1\}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>v</mi> <mo>∈</mo> <mo stretchy="false">{</mo> <mi>t</mi> <mo>,</mo> <mi>t</mi> <mo>+</mo> <mn>1</mn> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation>. In this paper, we prove that an <Emphasis FontCategory="SansSerif">SCA</Emphasis>(7!; 7, 10) does not exist. We do this by analysing connections between sequence covering arrays and a special kind of covering array called an excess coverage array.

Excess coverage arrays and Levenshtein’s conjecture

期刊论文
出版模式：

开放获取
发表日期：

2025年8月30日

查看全文

Amber E. Gentle,
Daniel Horsley,
Ian M. Wanless

摘要

A sequence covering array, denoted by SCA(N; t, v), is a set of N permutations of $\{0, \dots , v-1 \}$ ${0, \dots, v - 1}$ such that each sequence of t distinct elements of $\{0, \dots , v-1\}$ ${0, \dots, v - 1}$ is a (not necessarily contiguous) subsequence of at least one permutation. The minimum number of permutations such a sequence covering array can have is t! and it has been conjectured that for $t > 4$ $t > 4$ , if a sequence covering array with t! permutations exists, then $v \in \{t,t+1\}$ $v \in {t, t + 1}$ . In this paper, we prove that an SCA(7!; 7, 10) does not exist. We do this by analysing connections between sequence covering arrays and a special kind of covering array called an excess coverage array.