科研之友
微信
新浪微博
Facebook
分享链接
摘要
Let x be an m-sequence, a maximal length sequence produced by a linear feedback shift register. We show that x has maximal subword complexity function in the sense of Allouche and Shallit. We show that this implies that the nondeterministic automatic complexity A(N)(x) is close to maximal: n/2 - A(N)(x) = O(log(2)n), where n is the length of x. In contrast, Hyde has shown A(N)(y) <= n/2 + 1 for all sequences y of length n.
- 出版日期2018-9
