Spans of preference functions for de Bruijn sequences

DOI10.1016/J.DAM.2011.11.024MaRDI QIDQ423901zbMATH OpenOpenAlexFDO

Authors Abbas M. Alhakim

Publication date 30 May 2012

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1012.1796

zbMATH Keywords

de Bruijn sequencelinear complexityford sequenceprefer-one algorithmpreference function

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15)

Abstract: 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.

Recommendations

• A simple combinatorial algorithm for de Bruijn sequences
• A generalized recursive construction for de Bruijn sequences
• De Bruijn sequences revisited
• Clues to the hidden nature of de Bruijn sequences
• Revisiting the prefer-same and prefer-opposite de Bruijn sequence constructions

Cites work

• scientific article; zbMATH DE number 3422259 (Why is no real title available?)
• scientific article; zbMATH DE number 3095523 (Why is no real title available?)
• A Survey of Full Length Nonlinear Shift Register Cycle Algorithms
• A problem in arrangements
• A simple combinatorial algorithm for de Bruijn sequences
• On the complexities of de-Bruijn sequences

Cited in

(12)

• Constructing de Bruijn sequences by concatenating smaller universal cycles
• On the quadratic spans of DeBruijn sequences
• Revisiting the prefer-same and prefer-opposite de Bruijn sequence constructions
• On prefer-one sequences
• An efficient shift rule for the prefer-max de Bruijn sequence
• Linear spans of modified de Bruijn sequences
• A simple shift rule for \(k\)-ary de Bruijn sequences
• A relation between sequences generated by Golomb's preference algorithm
• Mapping prefer-opposite to prefer-one de Bruijn sequences
• Designing preference functions for de Bruijn sequences with forbidden words
• A framework for constructing de Bruijn sequences via simple successor rules
• On greedy algorithms for binary de Bruijn sequences

This page was built for publication: Spans of preference functions for de Bruijn sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q423901)