Suffix-language characterization conjecture for FKM universal cycles

Let T(n,k)\textbf{T}(n,k) denote the set of strings of length nn over the paper's alphabet, and let ST(n,k)\textbf{S}\subseteq\textbf{T}(n,k) be closed under rotations. Given a string αT(n,k)\alpha\in\textbf{T}(n,k), an α\alpha-suffix language is a set of strings such that, whenever β=b1bn\beta=b_1\cdots b_n belongs to it and α=a1an\alpha=a_1\cdots a_n, one has bmamb_m\leq a_m and b1bm1amanb_1\cdots b_{m-1}a_m\cdots a_n belongs to the set for every 1mn1\leq m\leq n. Suffix-language characterization conjecture. The FKM algorithm generates a universal cycle for S\textbf{S} if and only if the set of necklaces in S\textbf{S} is an α\alpha-suffix language, where α\alpha is the lexicographically maximal necklace in S\textbf{S}. 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

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.