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

Summary: 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,\dots,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.