A simple shift rule for -ary de Bruijn sequences

详细信息    查看全文

• 作者：Joe Sawada^a ; ^{jsawada@uoguelph.ca} ; Aaron Williams^b ; ^{haron@uvic.ca} ; Dennis Wong^c ; ^{cwong@uoguelph.ca}
• 关键词：kk-ary de Bruijn sequence ; De Bruijn sequence ; Universal cycle ; Necklaces ; Shift Gray code ; CAT algorithm ; Generate ; Shift rule ; Successor rule
• 刊名：Discrete Mathematics
• 出版年：2017
• 出版时间：March 2017
• 年：2017
• 卷：340
• 期：3
• 页码：524-531
• 全文大小：446 K
• 卷排序：340

文摘

A kk-ary de Bruijn sequence of order nn is a cyclic sequence of length knkn in which each kk-ary string of length nn appears exactly once as a substring. A shift rule for a de Bruijn sequence of order nn is a function that maps each length nn substring to the next length nn substring in the sequence. We present the first known shift rule for kk-ary de Bruijn sequences that runs in O(1)O(1)-amortized time per symbol using O(n)O(n) space. Our rule generalizes the authors’ recent shift rule for the binary case (A surprisingly simple de Bruijn sequence construction, Discrete Math. 339, 127–131).