[HTML][HTML] Lyndon words and Fibonacci numbers

K Saari - Journal of Combinatorial Theory, Series A, 2014 - Elsevier
Journal of Combinatorial Theory, Series A, 2014Elsevier
It is a fundamental property of non-letter Lyndon words that they can be expressed as a
concatenation of two shorter Lyndon words. This leads to a naive lower bound⌈ log 2 (n)⌉+
1 for the number of distinct Lyndon factors that a Lyndon word of length n must have, but this
bound is not optimal. In this paper we show that a much more accurate lower bound is⌈ log
ϕ (n)⌉+ 1, where ϕ denotes the golden ratio (1+ 5)/2. We show that this bound is optimal in
that it is attained by the Fibonacci Lyndon words. We then introduce a mapping L x that …
It is a fundamental property of non-letter Lyndon words that they can be expressed as a concatenation of two shorter Lyndon words. This leads to a naive lower bound⌈ log 2 (n)⌉+ 1 for the number of distinct Lyndon factors that a Lyndon word of length n must have, but this bound is not optimal. In this paper we show that a much more accurate lower bound is⌈ log ϕ (n)⌉+ 1, where ϕ denotes the golden ratio (1+ 5)/2. We show that this bound is optimal in that it is attained by the Fibonacci Lyndon words. We then introduce a mapping L x that counts the number of Lyndon factors of length at most n in an infinite word x. We show that a recurrent infinite word x is aperiodic if and only if L x⩾ L f, where f is the Fibonacci infinite word, with equality if and only if x is in the shift orbit closure of f.
Elsevier
以上显示的是最相近的搜索结果。 查看全部搜索结果