Generalized de Bruijn words for primitive words and powers (Q2515571): Difference between revisions

Let \(\Sigma_k=\{0,1,\ldots,k-1\}\), and let \(\Sigma_k^n\) be the set of words of length \(n\) over \(\Sigma_k\). For every subset \(\mathcal{D}\) of \(\Sigma_k^n\), a (generalized) de Bruijn word for \(\mathcal{D}\) is a word over \(\Sigma_k\) containing as a circular factor every word of \(\mathcal{D}\) exactly once, and no other words of \(\Sigma_k^n\) [\textit{E. Moreno}, Inf. Process. Lett. 96, No. 6, 214--219 (2005; Zbl 1184.68323)]. A famous theorem of \textit{H. Fredricksen} and \textit{J. Maiorana} [Discrete Math. 23, 207--210 (1978; Zbl 0384.05004)] states that concatenating all Lyndon words over \(\Sigma_k\) of length dividing \(n\), in lexicographic order, results in a de Bruijn word for the set \(\Sigma_k^n\). The main result of the paper is the proof of the following statement (attributed by the author to Michael Domaratzki) that is strictly related to the theorem of Fredricksen and Maiorana: {Theorem.} Concatenating all Lyndon words over \(\Sigma_k\) of length exactly \(n\), in lexicographic order, results in a de Bruijn word for the set of primitive words in \(\Sigma_k^n\). The paper also contains a number of interesting results related to the main result, as well as algorithmic considerations about the generation of generalized de Bruijn words.