𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Coordination through De Bruijn sequences

✍ Scribed by Olivier Gossner; Penélope Hernández

Publisher
Elsevier Science
Year
2006
Tongue
English
Weight
163 KB
Volume
34
Category
Article
ISSN
0167-6377

No coin nor oath required. For personal study only.

✦ Synopsis

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 m ln m Cn, with probability close to 1, there exists an automaton of size m that matches the sequence at almost all stages.

📜 SIMILAR VOLUMES

Generation of some de Bruijn sequences
Generation of some de Bruijn sequences
✍ Man-Keung Siu; Po Tong 📂 Article 📅 1980 🏛 Elsevier Science 🌐 English ⚖ 411 KB

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

Weight class distributions of de Bruijn
Weight class distributions of de Bruijn sequences
✍ Gregory L. Mayhew 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 275 KB

Order n de Bruijn sequences are the period 2" binary sequences produced by an n stage feedback shift register. The de Bruijn sequences have good randomness and complexity properties. Theorems are given on the weight class distributions of the generator functions. Data that extend the work of Fredric

Transposing Arrays on Multicomputers Usi
Transposing Arrays on Multicomputers Using de Bruijn Sequences
✍ Paul N. Swarztrauber 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 326 KB

Transposing an N\_N array that is distributed row-or columnwise across P=N processors is a fundamental communication task that requires timeconsuming interprocessor communication. It is the underlying communication task for the fast Fourier transform of long sequences and multidimensional arrays. It