On the theorem of Fredricksen and Maiorana about de Bruijn sequences

Eduardo Moreno

doi:10.1016/j.aam.2003.10.002

On the theorem of Fredricksen and Maiorana about de Bruijn sequences

Eduardo Moreno

Faculty of Engineering and Science

Research output: Contribution to journal › Article › peer-review

8 Scopus citations

Abstract

This work gives an alternative proof for the theorem of Fredricksen and Maiorana [Discrete Math. 23 (1978) 207-210] about constructing a de Bruijn sequence by concatenation of the Lyndon words in lexicographic order. This proof gives the exact position of all the words in the sequence, and allows us to extend this result to the concatenation of any number of the last Lyndon words in increasing order.

Original language	English
Pages (from-to)	413-415
Number of pages	3
Journal	Advances in Applied Mathematics
Volume	33
Issue number	2
DOIs	https://doi.org/10.1016/j.aam.2003.10.002
State	Published - Aug 2004

Keywords

De Bruijn sequence
Lyndon words
Necklaces

Access to Document

10.1016/j.aam.2003.10.002

Cite this

@article{03ef6d77c93a4d59bc5fc7fe0695c956,

title = "On the theorem of Fredricksen and Maiorana about de Bruijn sequences",

abstract = "This work gives an alternative proof for the theorem of Fredricksen and Maiorana [Discrete Math. 23 (1978) 207-210] about constructing a de Bruijn sequence by concatenation of the Lyndon words in lexicographic order. This proof gives the exact position of all the words in the sequence, and allows us to extend this result to the concatenation of any number of the last Lyndon words in increasing order.",

keywords = "De Bruijn sequence, Lyndon words, Necklaces",

author = "Eduardo Moreno",

note = "Funding Information: 1 Partially supported by ECOS C00E03 (French-Chilean Cooperation), Programa Iniciativa Cient{\'i}fica Milenio P01-005, Proyecto MECESUP UCH0009 and CONICYT PhD Fellowship.",

year = "2004",

month = aug,

doi = "10.1016/j.aam.2003.10.002",

language = "English",

volume = "33",

pages = "413--415",

journal = "Advances in Applied Mathematics",

issn = "0196-8858",

publisher = "Academic Press Inc.",

number = "2",

}

TY - JOUR

T1 - On the theorem of Fredricksen and Maiorana about de Bruijn sequences

AU - Moreno, Eduardo

N1 - Funding Information: 1 Partially supported by ECOS C00E03 (French-Chilean Cooperation), Programa Iniciativa Científica Milenio P01-005, Proyecto MECESUP UCH0009 and CONICYT PhD Fellowship.

PY - 2004/8

Y1 - 2004/8

N2 - This work gives an alternative proof for the theorem of Fredricksen and Maiorana [Discrete Math. 23 (1978) 207-210] about constructing a de Bruijn sequence by concatenation of the Lyndon words in lexicographic order. This proof gives the exact position of all the words in the sequence, and allows us to extend this result to the concatenation of any number of the last Lyndon words in increasing order.

AB - This work gives an alternative proof for the theorem of Fredricksen and Maiorana [Discrete Math. 23 (1978) 207-210] about constructing a de Bruijn sequence by concatenation of the Lyndon words in lexicographic order. This proof gives the exact position of all the words in the sequence, and allows us to extend this result to the concatenation of any number of the last Lyndon words in increasing order.

KW - De Bruijn sequence

KW - Lyndon words

KW - Necklaces

UR - http://www.scopus.com/inward/record.url?scp=3342899258&partnerID=8YFLogxK

U2 - 10.1016/j.aam.2003.10.002

DO - 10.1016/j.aam.2003.10.002

M3 - Article

AN - SCOPUS:3342899258

SN - 0196-8858

VL - 33

SP - 413

EP - 415

JO - Advances in Applied Mathematics

JF - Advances in Applied Mathematics

IS - 2

ER -

On the theorem of Fredricksen and Maiorana about de Bruijn sequences

Abstract

Keywords

Access to Document

Fingerprint

Cite this