Equivalence of the lexicographic-composition de Bruijn constructions

Let alt(n)alt(n) denote the alternating sequence of 00s and 11s of length nn that ends with 00. Let \d835\d835Ln\d835\d835\mathcal{L}_n be the de Bruijn sequence obtained from the lexicographic-composition construction, and let \d835\d835LCn\d835\d835\mathcal{LC}_n be the de Bruijn sequence returned by applying the de Bruijn successor LCLC to 0alt(n1)0alt(n-1). Equivalence of the lexicographic-composition constructions. The de Bruijn sequences \d835\d835LCn\d835\d835\mathcal{LC}_n and \d835\d835Ln\d835\d835\mathcal{L}_n are the same. This identifies the sequence produced by the successor-based construction with the sequence from the lexicographic-composition construction. The source presents the claim as an observed correspondence, but supplies no resolution beyond the stated assertion.

Sources & referencesView supporting material

Primary source

Evan Sala, Joe Sawada and Abbas Alhakim, “Efficient constructions of the Prefer-same and Prefer-opposite de Bruijn sequences”, arXiv:2010.07960 (2023).

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.