Generalized de Bruijn words for primitive words and powers

作者：Au Yu Hin^*

来源：Discrete Mathematics, 2015, 338(12): 2320-2331.

DOI：10.1016/j.disc.2015.05.025

• Primitive words
• de Bruijn words
• de Bruijn graphs
• Lyndon words

We show that for every n >= 1 and over any finite alphabet, there is a word whose circular factors of length n have a one-to-one correspondence with the set of primitive words. In particular, we prove that such a word can be obtained by a greedy algorithm, or by concatenating all Lyndon words of length n in increasing lexicographic order. We also look into connections between de Bruijn graphs of primitive words and Lyndon graphs.
Finally, we also show that the shortest word that contains every p-power of length pn over a k-letter alphabet has length between pk(n) and roughly (p+1/k)k(n), for all integers p >= 1. An algorithm that generates a word which achieves the upper bound is provided.

• 出版日期2015-12-6