Equivalence of the lexicographic-composition de Bruijn constructions

About 6 years old · traced to

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(n−1)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.

References

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.