Classifying Rotationally-Closed Languages Having Greedy Universal Cycles

Abstract

Let $\textbf{T}(n,k)$ be the set of strings of length $n$ over the alphabet $\Sigma=\{1,2,\ldots,k\}$. A universal cycle for $\textbf{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 $\textbf{S}\subseteq\textbf{T}(n,k)$; we will classify all such subsets that are closed under rotations.