Forbidden-substring conjecture for greedy universal cycles

Let T(n,k)\textbf{T}(n,k) denote the set of strings of length nn over the alphabet of symbols used in the paper. Let γT(m,k)\gamma\in\textbf{T}(m,k) be a string containing a symbol ak2a\leq k-2, and let ST(n,k)\textbf{S}\subseteq\textbf{T}(n,k), for some nmn\geq m, be the set of strings not containing γ\gamma as a cyclic substring. Forbidden-substring conjecture. The greedy algorithm starting from knk^n generates a universal cycle for S\textbf{S}. This would complete the known partial classification of forbidden substrings for which the greedy algorithm generates a universal cycle; the claim concerns the remaining case in which the forbidden string contains a symbol at most k2k-2.

Sources & referencesView supporting material

Primary source

Joseph DiMuro, “Classifying Rotationally-Closed Languages Having Greedy Universal Cycles”, arXiv:1805.11641 (2018).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.