Generalizing the classic greedy and necklace constructions of de Bruijn sequences and universal cycles

Joe Sawada¹ ; Aaron Williams² ; Dennis Wong³

¹University of Guelph
²Bard College of Simon's Rock
³Northwest Missouri State University

The electronic journal of combinatorics, Tome 23 (2016) no. 1

Résumé

We present a class of languages that have an interesting property: For each language $\mathbf{L}$ in the class, both the classic greedy algorithm and the classic Lyndon word (or necklace) concatenation algorithm provide the lexicographically smallest universal cycle for $\mathbf{L}$. The languages consist of length $n$ strings over $\{1,2,\ldots ,k\}$ that are closed under rotation with their subset of necklaces also being closed under replacing any suffix of length $i$ by $i$ copies of $k$. Examples include all strings (in which case universal cycles are commonly known as de Bruijn sequences), strings that sum to at least $s$, strings with at most $d$ cyclic descents for a fixed $d>0$, strings with at most $d$ cyclic decrements for a fixed $d>0$, and strings avoiding a given period. Our class is also closed under both union and intersection, and our results generalize results of several previous papers.

Détail

DOI : 10.37236/5517

Classification : 05A05, 05A15
Mots-clés : \(k\)-suffix language, de Bruijn sequence, universal cycle, greedy algorithm, FKM algorithm, necklaces, lexicographical ordering