Generalized de Bruijn words for primitive words and powers (Q2515571)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Generalized de Bruijn words for primitive words and powers
scientific article

    Statements

    Generalized de Bruijn words for primitive words and powers (English)
    0 references
    5 August 2015
    0 references
    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.
    0 references
    0 references
    primitive words
    0 references
    de Bruijn words
    0 references
    de Bruijn graphs
    0 references
    Lyndon words
    0 references
    0 references

    Identifiers