A note on the complexity of C-infinity-words

作者：Huang, Yun Bao; Weakley, William D.^*

来源：Theoretical Computer Science, 2010, 411(40-42): 3731-3735.

DOI：10.1016/j.tcs.2010.06.024

• Kolakoski sequence
• C-infinity-word

Let gamma(n) be the number of C-infinity-words of length n. Say that a C-infinity-word w is left doubly extendable (LDE) if both 1w and 2w are C-infinity. We show that for any positive real number phi and positive integer N such that the proportion of 2's is greater than 1/2 - phi in each LDE word of length exceeding N, there are positive constants c(1) and c(2) such that
c(1)n log 3/log((3/2)+phi+(2/N)) < gamma(n) < c(2)n log 3/log((3/2)-phi)
for all positive integers n. With the best value known for phi, and large N, this gives
c(1)n(2.7087) < gamma(n) < c(2)n(2.7102).

• 出版日期2010-9-6
• 单位杭州师范大学