Suffix-language characterization conjecture for FKM universal cycles
Suffix-language characterization conjecture for FKM universal cycles
Let denote the set of strings of length over the paper's alphabet, and let be closed under rotations. Given a string , an -suffix language is a set of strings such that, whenever belongs to it and , one has and belongs to the set for every . Suffix-language characterization conjecture. The FKM algorithm generates a universal cycle for if and only if the set of necklaces in is an -suffix language, where is the lexicographically maximal necklace in . This proposes a necessary-and-sufficient characterization of the rotation-closed languages for which the FKM algorithm produces a universal cycle.
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.