Spans of Preference Functions for De Bruijn Sequences

Details Spans of Preference Functions for De Bruijn Sequences Spans of Preference Functions for De Bruijn Sequences

2010-12-08

arxiv.org/abs/1012.1796v1

Mathematics

Combinatorics

10 pages, four tables, first draft

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Spans of Preference Functions for De Bruijn Sequences does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Spans of Preference Functions for De Bruijn Sequences, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Spans of Preference Functions for De Bruijn Sequences will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-558796