Geodesic
De Bruijn sequences: from games to shift-rules to a proof of the Fredricksen-Kessler-Maiorana theorem
Gal Amram ; Amir Rubin ; Yotam Svoray1 ; Gera Weiss
1Ben Gurion University of the Negev
The electronic journal of combinatorics, Tome 32 (2025) no. 3
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

We present a combinatorial game and propose efficiently computable optimal strategies. We then show how these strategies can be translated to efficiently computable shift-rules for the well known prefer-max and prefer-min De Bruijn sequences, in both forward and backward directions. Using these shift-rules, we provide a new proof of the well known theorem by Fredricksen, Kessler, and Maiorana on De Bruijn sequences and Lyndon words.
DOI : 10.37236/13603
Classification : 68R15, 05A05, 91A46, 91A68

Gal Amram    ; Amir Rubin    ; Yotam Svoray  1   ; Gera Weiss 

1 Ben Gurion University of the Negev 
@article{10_37236_13603,
     author = {Gal  Amram and Amir  Rubin and Yotam Svoray and Gera  Weiss},
     title = {De {Bruijn} sequences: from games to shift-rules to a proof of the {Fredricksen-Kessler-Maiorana} theorem},
     journal = {The electronic journal of combinatorics},
     year = {2025},
     volume = {32},
     number = {3},
     doi = {10.37236/13603},
     zbl = {8097639},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/13603/}
}
TY  - JOUR
AU  - Gal  Amram
AU  - Amir  Rubin
AU  - Yotam Svoray
AU  - Gera  Weiss
TI  - De Bruijn sequences: from games to shift-rules to a proof of the Fredricksen-Kessler-Maiorana theorem
JO  - The electronic journal of combinatorics
PY  - 2025
VL  - 32
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.37236/13603/
DO  - 10.37236/13603
ID  - 10_37236_13603
ER  - 
%0 Journal Article
%A Gal  Amram
%A Amir  Rubin
%A Yotam Svoray
%A Gera  Weiss
%T De Bruijn sequences: from games to shift-rules to a proof of the Fredricksen-Kessler-Maiorana theorem
%J The electronic journal of combinatorics
%D 2025
%V 32
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/13603/
%R 10.37236/13603
%F 10_37236_13603
Gal  Amram; Amir  Rubin; Yotam Svoray; Gera  Weiss. De Bruijn sequences: from games to shift-rules to a proof of the Fredricksen-Kessler-Maiorana theorem. The electronic journal of combinatorics, Tome 32 (2025) no. 3. doi: 10.37236/13603

Cité par Sources :