Generalizing the Classic Greedy and Necklace Constructions of de Bruijn Sequences and Universal Cycles

摘要

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 $d0$, strings with at most $d$ cyclic decrements for a fixed $d0$, 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.