Spans of preference functions for de Bruijn sequences

作者：Alhakim Abbas^*

来源：Discrete Applied Mathematics, 2012, 160(7-8): 992-998.

DOI：10.1016/j.dam.2011.11.024

• de Bruijn sequence
• Ford sequence
• Preference function
• Prefer-one algorithm
• Linear complexity

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 n which is the order of the sequence being generated. This set of rules is generalized by the concept of a preference function of span n - 1, which gives the priorities of what symbols to appear after a substring of size n - 1 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 n also generates de Bruijn sequences of all orders higher than n, 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.

• 出版日期2012-5