On the classification of deBruijn sequences
type: Item
instance of: scholarly article
title: On the classification of deBruijn sequences
zbMATH Open document ID: 0843.05049
DOI: 10.1016/0012-365X(94)00265-K
author: Erik R. Hauge
author: Johannes Mykkeltveit
published in: Discrete Mathematics
publication date: 1996-03-24T00:00:00Z
review text: A deBruijn sequence of order \(n\) is a binary sequence with period length \(2^n\) which contains all binary \(n\)-tupels. The binary deBruijn graph \(B_n\) is a directed graph with \(2^n\) nodes, each labeled with a unique binary \(n\)-tupel, and an edge from node \(T= (t_0, t_1,\dots, t_{n- 1})\) to node \(U= (u_0, u_1,\dots, u_{n- 1})\) if and only if \((t_1, t_2,\dots, t_{n- 1})= (u_0, u_1,\dots, u_{n- 2})\). The deBruijn sequences of order \(n\) are divided into weight classes. Certain permutations of the edges of \(B_n\) correspond to permutations of deBruijn sequences. In this paper, symmetry groups for the weight classes of the deBruijn sequences are used to subdivide them into smaller equivalence classes. These groups are given for \(n\leq 7\) when the weight is minimal or maximal.
Mathematics Subject Classification ID: 05C25
zbMATH DE Number: 858077
zbMATH Keywords: classification
zbMATH Keywords: deBruijn sequence
zbMATH Keywords: deBruijn graph
reviewed by: Ulrike Baumann
MaRDI profile type: Publication
cites work: A Survey of Full Length Nonlinear Shift Register Cycle Algorithms
cites work: On the cycles and adjacencies in the complementary circulating register
cites work: A proof of Golomb's conjecture for the de Bruijn graph
cites work: Generating and Counting the Double Adjacencies in a Pure Circulating Shift Register
full work available at URL: 0012-365x(94)00265-k
OpenAlex ID: W1991303196
description: scientific article; zbMATH DE number 858077