Perfect sequence covering arrays

Thesis type
(Thesis) M.Sc.
Date created
2021-08-01
Authors/Contributors
Author: Na, Jingzhou
Abstract
An (n, k)-perfect sequence covering array with multiplicity is a subset of the n! permutations of the sequence (1, 2, · · · , n) whose elements collectively contain each ordered length k subsequence exactly times. The primary objective is to determine, for given n and k, the smallest value of (denoted g(n, k)) for which such a configuration exists. In 2020, Yuster 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 determine that g(6, 3) = g(7, 3) = g(7, 4) = 2 and g(8, 3) 2 {2, 3} by modifying an old search algorithm due to Mathon and van Trung, and by restricting a perfect sequence covering array to be a union of cosets of a prescribed nontrivial subgroup of the symmetric group Sn. This prescribed structure provides a deeper understanding of the existence pattern for perfect sequence covering arrays by combining combinatorial and algebraic viewpoints.
Document
Identifier
etd21570
Copyright statement
Copyright is held by the author.
Permissions
This thesis may be printed or downloaded for non-commercial research and scholarly purposes.
Supervisor or Senior Supervisor
Thesis advisor: Chen, Imin
Language
English
Member of collection
Attachment Size
etd21570.pdf 698.45 KB