Generalized de Bruijn cycles (Q1889887)

This paper generalizes the notion of the de Bruijn sequences assumed as \(q\)-ary sequences \(s_0,s_1,\dots,s_{q^n+n-2}\) such that the family \(\{(s_i,s_{i+1},\dots,s_{i+n-1}): i\in\{0,1,\dots,q^n-1\}\}\) consists of all \(q\)-ary sequences of length \(n\). For a given subset \(\mathcal I=\{t_1,t_2,\dots,t_n\}\) of \(\{0,1,\dots,q^n-1\}\) the generalization of a de Bruijn sequence is defined as an \(\mathcal I\)-cycle such that the family \(\{(s_{i+t_1},s_{i+t_2},\dots,s_{i+t_n}): i\in\{0,1,\dots,q^n-1\}\}\) consists of all \(q\)-ary sequences of length \(n\) (with the indices reduced modulo \(q^n+n-1\)). The classical de Bruijn sequences are obtained for \(\mathcal I_d=\{d,d+1,\dots,d+n-1\}\) with \(d\in\{0,1,\dots,q^n-1\}\). The existence of the \(\mathcal I\)-cycles is mainly discussed for the case \(\mathcal I=\{0,d,\dots,(n-1)d\}\), for which the case \(| \mathcal I| =2\) has been solved completely. For the other cases the existence of approximate cycles, that is the shortest sequence that contains all \(q\)-ary sequences of length \(n\) according to \(\mathcal I\), is considered. The paper also contains a number of open problems.