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

研究成果: Article › 同行評審

5 引文斯高帕斯（Scopus）

摘要

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.

原文	English
頁（從 - 到）	25-35
頁數	11
期刊	Journal of Discrete Algorithms
卷	46-47
DOIs	https://doi.org/10.1016/j.jda.2017.10.002
出版狀態	Published - 9月 2017

存取文件

10.1016/j.jda.2017.10.002

其它文件與鏈接

Link to publication in Scopus

引用此

@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 - https://www.scopus.com/pages/publications/85030780666

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

摘要

存取文件

其它文件與鏈接

指紋

引用此