ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let T(n,k)\textbf{T}(n,k) denote the set of strings of length nn over the paper's alphabet, and let S⊆T(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 β=b1⋯bn\beta=b_1\cdots b_n belongs to it and α=a1⋯an\alpha=a_1\cdots a_n, one has bm≤amb_m\leq a_m and b1⋯bm−1am⋯anb_1\cdots b_{m-1}a_m\cdots a_n belongs to the set for every 1≤m≤n1\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.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.