Spans of preference functions for de Bruijn sequences

详细信息	查看全文 | 推荐本文 |

• 作者：Abbas Alhakim ; ^{aa145@aub.edu.lb}
• 关键词：de Bruijn sequence ; Ford sequence ; Preference function ; Prefer-one algorithm ; Linear complexity
• 刊名：Discrete Applied Mathematics
• 出版年：2012
• 期刊代码：46_0166218x
• 类别：cp
• 出版时间：May, 2012
• 卷：160
• 期：7-8
• 页码：992-998
• 文件大小：200 K

摘要

A nonbinary Ford sequence is a de聽Bruijn sequence generated by simple rules that determine the priorities of what symbols are to be tried first, given an initial word of size which is the order of the sequence being generated. This set of rules is generalized by the concept of a preference function of span , which gives the priorities of what symbols to appear after a substring of size is encountered. In this paper, we characterize preference functions that generate full de聽Bruijn sequences. More significantly, we establish that any preference function that generates a de聽Bruijn sequence of order also generates de聽Bruijn sequences of all orders higher than , thus making the Ford sequence no special case. Consequently, we define the preference function complexity of a de聽Bruijn sequence to be the least possible span of a preference function that generates this de聽Bruijn sequence.