Covering arrays of strength three from extended permutation vectors

A covering array (text{ CA }(N;t,k,v)) is an (Ntimes k) array such that in every (Ntimes t) subarray each possible t-tuple over a v-set appears as a row of the subarray at least once. The integers t and v are respectively the strength and the order of the covering array. Let v be a prime power and let ({mathbb {F}}_v) denote the finite field with v elements. In this work the original concept of permutation vectors generated by a ((t-1))-tuple over ({mathbb {F}}_v) is extended to vectors generated by a t-tuple over ({mathbb {F}}_v). We call these last vectors extended permutation vectors (EPVs). For every prime power v, a covering perfect hash family (text{ CPHF }(2;v^2-v+3,v^3,3)) is constructed from EPVs given by subintervals of a linear feedback shift register sequence over ({mathbb {F}}_v). When (vin {7,9,11,13,16,17,19,23,25}) the covering array (text{ CA }(2v^3-v;3,v^2-v+3,v)) generated by (text{ CPHF }(2;v^2-v+3,v^3,3)) has less rows than the best-known covering array with strength three, (v^2-v+3) columns, and order v. CPHFs formed by EPVs are also constructed using simulated annealing; in this case the results improve the size of eighteen covering arrays of strength three.