Spans of preference functions for de Bruijn sequences

DOI10.1016/J.DAM.2011.11.024zbMATH Open1239.05013arXiv1012.1796OpenAlexW2075879870MaRDI QIDQ423901FDOQ423901

Abbas M. Alhakim

Publication date: 30 May 2012

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

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.

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)

Cites Work

• Title not available (Why is that?)
• A problem in arrangements
• Title not available (Why is that?)
• A Survey of Full Length Nonlinear Shift Register Cycle Algorithms
• On the complexities of de-Bruijn sequences
• A Simple Combinatorial Algorithm for de Bruijn Sequences

Cited In (10)

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

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)