Corrigendum to "On the theorem of Fredricksen and Maiorana about de Bruijn sequences" [Adv. in Appl. Math. 33 (2) (2004) 413-415]

Eduardo Moreno, Dominique Perrin

Research output: Contribution to journalComment/debate

2 Scopus citations

Abstract

Fredricksen and Maiorana (1978) [2] prove that the concatenation of Lyndon words of length dividing n in lexicographic order produces a de Bruijn sequence of span n, and they state that this word is lexicographically minimal among all de Bruijn sequences of span n. An alternative proof was presented in Moreno (2004) [4]. The purpose of this corrigendum is twofold. We give a complete proof, clarifying some ambiguities of the previous proof. Additionally, we include a proof of the minimality of the de Bruijn sequence obtained in this way.

Original languageEnglish
Pages (from-to)184-187
Number of pages4
JournalAdvances in Applied Mathematics
Volume62
DOIs
StatePublished - 1 Jan 2015

Keywords

  • De Bruijn sequence
  • Lyndon words
  • Necklaces

Fingerprint

Dive into the research topics of 'Corrigendum to "On the theorem of Fredricksen and Maiorana about de Bruijn sequences" [Adv. in Appl. Math. 33 (2) (2004) 413-415]'. Together they form a unique fingerprint.

Cite this