A surprisingly simple de Bruijn sequence construction

Joe Sawada; Aaron Williams; Dennis Wong

doi:10.1016/j.disc.2015.08.002

A surprisingly simple de Bruijn sequence construction

Joe Sawada
, Aaron Williams
, Dennis Wong

研究成果: Article › 同行評審

47 引文斯高帕斯（Scopus）

摘要

Pick any length n binary string ^b1^b2⋯^bn and remove the first bit ^b1. If ^b2^b3⋯^bn1 is a necklace, then append the complement of ^b1 to the end of the remaining string; otherwise append ^b1. By repeating this process, eventually all 2ⁿ binary strings will be visited cyclically. This shift rule leads to a new de Bruijn sequence construction that can be generated in O(1)-amortized time per bit.

原文	English
頁（從 - 到）	127-131
頁數	5
期刊	Discrete Mathematics
卷	339
發行號	1
DOIs	https://doi.org/10.1016/j.disc.2015.08.002
出版狀態	Published - 6 1月 2016
對外發佈	是

存取文件

10.1016/j.disc.2015.08.002

其它文件與鏈接

Link to publication in Scopus

引用此

@article{2121d227cb5141648442cf06dc818404,

title = "A surprisingly simple de Bruijn sequence construction",

abstract = "Pick any length n binary string b1b2⋯bn and remove the first bit b1. If b2b3⋯bn1 is a necklace, then append the complement of b1 to the end of the remaining string; otherwise append b1. By repeating this process, eventually all 2n binary strings will be visited cyclically. This shift rule leads to a new de Bruijn sequence construction that can be generated in O(1)-amortized time per bit.",

keywords = "CAT algorithm, De Bruijn sequence, Generate, Necklaces, Shift Gray code, Shift rule, Successor rule, Universal cycle",

author = "Joe Sawada and Aaron Williams and Dennis Wong",

year = "2016",

month = jan,

day = "6",

doi = "10.1016/j.disc.2015.08.002",

language = "English",

volume = "339",

pages = "127--131",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier BV",

number = "1",

}

TY - JOUR

T1 - A surprisingly simple de Bruijn sequence construction

AU - Sawada, Joe

AU - Williams, Aaron

AU - Wong, Dennis

PY - 2016/1/6

Y1 - 2016/1/6

N2 - Pick any length n binary string b1b2⋯bn and remove the first bit b1. If b2b3⋯bn1 is a necklace, then append the complement of b1 to the end of the remaining string; otherwise append b1. By repeating this process, eventually all 2n binary strings will be visited cyclically. This shift rule leads to a new de Bruijn sequence construction that can be generated in O(1)-amortized time per bit.

AB - Pick any length n binary string b1b2⋯bn and remove the first bit b1. If b2b3⋯bn1 is a necklace, then append the complement of b1 to the end of the remaining string; otherwise append b1. By repeating this process, eventually all 2n binary strings will be visited cyclically. This shift rule leads to a new de Bruijn sequence construction that can be generated in O(1)-amortized time per bit.

KW - CAT algorithm

KW - De Bruijn sequence

KW - Generate

KW - Necklaces

KW - Shift Gray code

KW - Shift rule

KW - Successor rule

KW - Universal cycle

UR - https://www.scopus.com/pages/publications/84940399452

U2 - 10.1016/j.disc.2015.08.002

DO - 10.1016/j.disc.2015.08.002

M3 - Article

AN - SCOPUS:84940399452

SN - 0012-365X

VL - 339

SP - 127

EP - 131

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1

ER -

A surprisingly simple de Bruijn sequence construction

摘要

存取文件

其它文件與鏈接

指紋

引用此