Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4646952 | Discrete Mathematics | 2015 | 12 Pages |
Abstract
We show that for every n≥1n≥1 and over any finite alphabet, there is a word whose circular factors of length nn 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 nn 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 pp-power of length pnpn over a kk-letter alphabet has length between pknpkn and roughly (p+1k)kn, for all integers p≥1p≥1. An algorithm that generates a word which achieves the upper bound is provided.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Yu Hin Au,