Necklaces and Lyndon words in colexicographic and binary reflected Gray code order

Joe Sawada; Aaron Williams; Dennis Wong

doi:10.1016/j.jda.2017.10.002

Necklaces and Lyndon words in colexicographic and binary reflected Gray code order

Joe Sawada, Aaron Williams, Dennis Wong

Faculty of Applied Sciences

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

5 Citations (Scopus)

Abstract

We present the first efficient algorithm to list necklaces, Lyndon words, or pseudo-necklaces of length n in colexicographic order. The algorithm has two interesting properties. First, it can be applied to construct a de Bruijn sequence of order n in O(1)-time per bit. Second, it can easily be modified to efficiently list necklaces, Lyndon words, or pseudo-necklaces of length n in binary reflected Gray code order.

Original language	English
Pages (from-to)	25-35
Number of pages	11
Journal	Journal of Discrete Algorithms
Volume	46-47
DOIs	https://doi.org/10.1016/j.jda.2017.10.002
Publication status	Published - Sept 2017

Keywords

De Bruijn sequence
Gray code
Lyndon word
Necklace
Pseudo-necklace

Access to Document

10.1016/j.jda.2017.10.002

Cite this

@article{d3d319504ce741efb41f54ca4fa87f9a,

title = "Necklaces and Lyndon words in colexicographic and binary reflected Gray code order",

abstract = "We present the first efficient algorithm to list necklaces, Lyndon words, or pseudo-necklaces of length n in colexicographic order. The algorithm has two interesting properties. First, it can be applied to construct a de Bruijn sequence of order n in O(1)-time per bit. Second, it can easily be modified to efficiently list necklaces, Lyndon words, or pseudo-necklaces of length n in binary reflected Gray code order.",

keywords = "De Bruijn sequence, Gray code, Lyndon word, Necklace, Pseudo-necklace",

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

note = "Publisher Copyright: {\textcopyright} 2017 Elsevier B.V.",

year = "2017",

month = sep,

doi = "10.1016/j.jda.2017.10.002",

language = "English",

volume = "46-47",

pages = "25--35",

journal = "Journal of Discrete Algorithms",

issn = "1570-8667",

publisher = "Elsevier",

}

TY - JOUR

T1 - Necklaces and Lyndon words in colexicographic and binary reflected Gray code order

AU - Sawada, Joe

AU - Williams, Aaron

AU - Wong, Dennis

PY - 2017/9

Y1 - 2017/9

N2 - We present the first efficient algorithm to list necklaces, Lyndon words, or pseudo-necklaces of length n in colexicographic order. The algorithm has two interesting properties. First, it can be applied to construct a de Bruijn sequence of order n in O(1)-time per bit. Second, it can easily be modified to efficiently list necklaces, Lyndon words, or pseudo-necklaces of length n in binary reflected Gray code order.

AB - We present the first efficient algorithm to list necklaces, Lyndon words, or pseudo-necklaces of length n in colexicographic order. The algorithm has two interesting properties. First, it can be applied to construct a de Bruijn sequence of order n in O(1)-time per bit. Second, it can easily be modified to efficiently list necklaces, Lyndon words, or pseudo-necklaces of length n in binary reflected Gray code order.

KW - De Bruijn sequence

KW - Gray code

KW - Lyndon word

KW - Necklace

KW - Pseudo-necklace

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

U2 - 10.1016/j.jda.2017.10.002

DO - 10.1016/j.jda.2017.10.002

M3 - Article

AN - SCOPUS:85030780666

SN - 1570-8667

VL - 46-47

SP - 25

EP - 35

JO - Journal of Discrete Algorithms

JF - Journal of Discrete Algorithms

ER -

Necklaces and Lyndon words in colexicographic and binary reflected Gray code order

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this