On the Generation of Aperiodic and Periodic Necklaces via T-augmentation

Article type: Research Article

Authors: Gulliver, T. Aaron | Makwakwa, Isaiah | Speidel, Ulrich

Affiliations: Department of Electrical and Computer Engineering, University of Victoria, Victoria, BC, Canada. E-mail: [email protected] | School of Mathematics, University College Dublin, Belfield, Dublin 4, Ireland. E-mail: [email protected] | Department of Computer Science, The University of Auckland, Auckland, New Zealand. E-mail: [email protected]

Abstract: In a recent report, Gulliver and Speidel showed that complete sets of aperiodic and – in some cases periodic – necklaces can be generated for arbitrary lengths as fixed-length subsets of variable-length T-codes. The T-codes to which they applied this observation were specifically T-codes constructed by systematic T-augmentation, that is by T-augmentation sequences in which each T-expansion parameter is 1 (simple T-augmentation) and where the T-codes A_{(p1,p2,…,pi)} at each Taugmentation level i do not contain any codewords shorter than pi (strictly minimal T-augmentation). This present paper generalizes their result to arbitrary T-codes and formalizes their earlier result as a special case of the general result.

Keywords: Necklaces, Lyndon words, cyclic equivalence, T-codes, synchronization

Journal: Fundamenta Informaticae, vol. 83, no. 1-2, pp. 91-107, 2008