Stretching de Bruijn sequences

We give a one-step construction of de Bruijn sequences of general alphabet size and with order \(n+k\), given a de Bruijn sequence of order n and any integer \(k>1\). This is achieved by using an appropriate class of graph homomorphisms between de Bruijn digraphs whose orders differ by an integer k. The method starts with a lower order de Bruijn cycle, finds its inverse cycles in the higher order digraph, which are then cross-joined into one full cycle. Therefore, this generalizes the Lempel’s binary construction and the Alhakim–Akinwande construction for non-binary alphabets and a wide class of homomorphisms.     

Generation of some de Bruijn sequences

The cycle structure of the “connection” of feedback logics is applied to construct more polynomials which generate de Bruijn sequences.     

On the complexities of de Bruijn sequences

The shortest linear recursion which generates a de Bruijn sequence is defined to be the complexity of the sequence. It is shown that the complexity of a binary de Bruijn sequence of span n is bounded by 2ⁿ ? 1 from above and 2^{n ? 1} + n from below. Results on the distribution of the complexities are also presented.     

A recursive construction of nonbinary de Bruijn sequences

This paper presents a method to find new de Bruijn sequences based on ones of lesser order. This is done by mapping a de Bruijn cycle to several vertex disjoint cycles in a de Bruijn digraph of higher order and then connecting these cycles into one full cycle. We present precise formulae for the locations where those cycles can be rejoined into one full cycle. We obtain an exponentially large class of distinct de Bruijn cycles. This method generalizes the Lempel construction of binary de Bruijn sequences as well as its efficient implementation by Annextein.     

Minimal polynomials of the modified de Bruijn sequences

It is well known that a de Bruijn sequence over has the minimal polynomial (x+1)^d, where 2^n-1+nd2ⁿ-1. We study the minimal polynomials of the modified de Bruijn sequences.     

Minimum Eulerian circuits and minimum de Bruijn sequences

Given a digraph (directed graph) with a labeling on its arcs, we study the problem of finding the Eulerian circuit of lexicographically minimum label. We prove that this problem is NP-complete in general, but if the labelling is locally injective (arcs going out from each vertex have different labels), we prove that it is solvable in linear time by giving an algorithm that constructs this circuit. When this algorithm is applied to a de Bruijn graph, it obtains the de Bruijn sequences with lexicographically minimum label.     

Construction for de Bruijn sequences with large stage

Sequences generated by maximum-period nonlinear feedback shift registers are known as de Bruijn sequences. The problem of generating de Bruijn sequences has received considerable attention. In this paper, we provide a method for generating large state (such as \(n=128\)) de Bruijn sequences.     

Further results on correlation functions of de Bruijn sequences

In this paper we develop some bounds for the correlation functions of sequences with period 2 ⁿ and specific linear complexities. These bounds are also applicable to the correlation functions of de Bruijn sequences with spann and specific linear complexities. It is interesting that a conjecture of Chan, Games and Key's for the case ofn=2 ^m can be proved easily by using the results developed here. Their conjecture asserts that there are no de Bruijn sequences with spann and linear complexity 2 ^n–1+n+1. The comjecture was proved by Games by a different method.Institute of Systems Science, Academic Sinica     

Practical algorithms to rank necklaces,Lyndon words,and de Bruijn sequences

We present practical algorithms for ranking k-ary necklaces and Lyndon words of length n. The algorithms are based on simple counting techniques. By repeatedly applying the ranking algorithms, both necklaces and Lyndon words can be efficiently unranked. Then, explicit details are given to rank and unrank the length n substrings of the lexicographically smallest de Bruijn sequence of order n.     

A note on certain de Bruijn sequences with forbidden subsequences

We consider words over a finite alphabet with certain uniqueness properties (a subsequence of length k does not occur more than once) and distance properties (at least j other symbols separate the occurrence of the same symbol). The maximal length of these words is realised by linear de Bruijn sequences with certain forbidden subsequences. We prove the existence of these maximal sequences.     

Necklaces of beads in k colors and k-ary de Bruijn sequences

This paper constructs a decreasing lexicographic list of necklaces of length n in beads of k colors. This list, somewhat modified, produces a k-ary de Bruijn sequence of length kⁿ.     

A framework for constructing de Bruijn sequences via simple successor rules

We present a simple framework for constructing de Bruijn sequences, and more generally, universal cycles, via successor rules. The framework is based on the often used method of joining disjoint cycles. It generalizes four previously known de Bruijn sequence constructions and is applied to derive three new and simple de Bruijn sequence constructions. Four of the constructions apply the pure cycling register and three apply the complemented cycling register. The correctness of each new construction is easily proved using the new framework. Each of the three new de Bruijn sequence constructions can be generated in $O\left(n\right)$-time per bit using $O\left(n\right)$-space.     

Generalized de Bruijn Cycles

For a set of integers , we define a q-ary -cycle to be an assignment of the symbols 1 through q to the integers modulo q ⁿ so that every word appears on some translate of . This definition generalizes that of de Bruijn cycles, and opens up a multitude of questions. We address the existence of such cycles, discuss reduced cycles (ones in which the all-zeroes string need not appear), and provide general bounds on the shortest sequence which contains all words on some translate of . We also prove a variant on recent results concerning decompositions of complete graphs into cycles and employ it to resolve the case of completely.AMS Subject Classification: 94A55, 05C70.     

Generalized de Bruijn graphs

Oriented graphs in which every pair of vertices can be connected by a unique path of given length (not depending on the choice of the pair of vertices) are studied. These graphs are a natural extension of the well-known de Bruijn graphs and retain their most important properties. Some results on the structure of and methods for constructing such graphs are obtained. Translated fromMatematicheskie Zametki, Vol. 62, No. 4, pp. 540–548, October, 1997. Translated by O. V. Sipacheva     

Coordination through De Bruijn sequences

Let (x_t) be an n-periodic sequence in which the first n elements are drawn i.i.d. according to some rational distribution. We prove there exists a constant C such that whenever mlnm?Cn, with probability close to 1, there exists an automaton of size m that matches the sequence at almost all stages.