Special cases of de Bruijn Objects and its applications

Rafał Witkowski
Adam Mickiewicz University

PDF

Minisymposium: COMBINATORICS

Content: A $k$-ary De Bruijn sequence $B(n,k)$ of order $n$, is a sequence of a given alphabet $A$ with size $k$ for which every subsequence of length $n$ in $A$ appears as a sequence of consecutive characters exactly once. De Bruijn matrix is an array of symbols from an alphabet $A$ of size $k$ that contains every $m$-by-$n$ matrix exactly once. Our goal is to maximize size of the matrix. We will define rotation resistant De Bruijn matrix as a matrix where $k=4$ and each symbol can be rotated: $1 \rightarrow 2, 2 \rightarrow 3, 3 \rightarrow 4, 4 \rightarrow 1$. We will try to give an answer how big can be such a matrix. We will consider, if there exist upper bound for the size of regular de Bruijn matrix.

Back to all abstracts