On Embedding De Bruijn Sequences by Increasing the Alphabet Size

arXiv1906.06157MaRDI QIDQ6320508FDOQ6320508

Authors: Moshe Schwartz, Yotam Svoray, Gera Weiss 

Publication date: 10 June 2019

Abstract: The generalization of De Bruijn sequences to infinite sequences with respect to the order $n$ has been studied iand it was shown that every de Bruijn sequence of order $n$ in at least three symbols can be extended to a de Bruijn sequence of order $n+1$. Every de Bruijn sequence of order $n$ in two symbols can not be extended to order $n+1$, but it can be extended to order $n+2$. A natural question to ask is if this theorem is true with respect to the alphabet. That is, we would like to understand if we can extend a De Bruijn sequence of order $n$ over alphabet $k$ into a into a De Bruijn sequence of order $n$ and alphabet $k+1$. We call a De Bruijn sequence with this property an Onion De Bruijn sequence. In this paper we show that the answer to this question is positive. In fact, we prove that the well known Prefer Max De Bruijn sequence has this property, and in fact every sequence with this property behaves like the Prefer max De Bruijn sequence.

This page was built for publication: On Embedding De Bruijn Sequences by Increasing the Alphabet Size

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6320508)