On the Nth linear complexity of automatic sequences

JOURNAL OF NUMBER THEORY

卷:187

Article

Merai, Laszlo¹  Winterhof, Arne¹ 

[1] Austrian Acad Sci, Johann Radon Inst Computat & Appl Math, Altenbergerstr 69, A-4040 Linz, Austria

关键词: Automatic sequences;    Thue-Morse sequence;    Rudin-Shapiro sequence;    Pattern sequence;    Sum-of-digits sequence;    Baum-Sweet sequence;    Paper folding sequence;    Linear complexity;    Expansion complexity;    Lattice profile;    Continued fractions;   

DOI  :  10.1016/j.jnt.2017.11.008

来源: Elsevier

【 摘 要 】

The Nth linear complexity of a sequence is a measure of predictability. Any unpredictable sequence must have large Nth linear complexity. However, in this paper we show that for q-automatic sequences over F-q the converse is not true. We prove that any (not ultimately periodic) q-automatic sequence over F-q has Nth linear complexity of order of magnitude N. For some famous sequences including the Thue-Morse and Rudin-Shapiro sequence we determine the exact values of their Nth linear complexities. These are non-trivial examples of predictable sequences with Nth linear complexity of largest possible order of magnitude. (C) 2017 Elsevier Inc. All rights reserved.

【 授权许可】

Free