Extending de Bruijn sequences to larger alphabets

A circular de Bruijn sequence of order $n$ in an alphabet of $k$ symbols is a sequence in which each sequence of length $n$ occurs exactly once. In this work we show that for each circular de Bruijn sequence $v$ of order $n$ in an alphabet of $k$ symbols there is another circular de Bruijn sequence $w$ also of order $n$ in an alphabet with one more symbol, that is an alphabet of $k + 1$ symbols, such that $v$ is a subsequence of $w$ and in between any two successive occurrences of the new symbol in $w$ there are at most $n + 2k-2$ consecutive symbols of $v$. We give an algorithm that receives as input such a sequence $v$ and outputs a sequence $w$. We also give a much faster algorithm that receives as input such a sequence $v$ and outputs a sequence $w$, but the new symbol may not be evenly spread out.