Forbidden-substring conjecture for greedy universal cycles
Forbidden-substring conjecture for greedy universal cycles
Let denote the set of strings of length over the alphabet of symbols used in the paper. Let be a string containing a symbol , and let , for some , be the set of strings not containing as a cyclic substring. Forbidden-substring conjecture. The greedy algorithm starting from generates a universal cycle for . 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 .
Sources & referencesView supporting material
Primary source
Joseph DiMuro, “Classifying Rotationally-Closed Languages Having Greedy Universal Cycles”, arXiv:1805.11641 (2018).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.