Classifying Rotationally-Closed Languages Having Greedy Universal Cycles

Abstract

Let $\text{T}(n,k)$ be the set of strings of length $n$ over the alphabet $\Sigma =\{1,2,\dots ,k\}$. A universal cycle for $\text{T}(n,k)$ can be constructed using a greedy algorithm: start with the string $k^n$, and continually append the least symbol possible without repeating a substring of length $n$. This construction also creates universal cycles for some subsets $\text{S}\subseteq \text{T}(n,k)$; we will classify all such subsets that are closed under rotations.