On the Nth linear complexity of automatic sequences

DOI10.1016/J.JNT.2017.11.008MaRDI QIDQ1747239zbMATH OpenOpenAlexFDO

Authors László Mérai, Arne Winterhof

Publication date 4 May 2018

Published in Journal of Number Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1711.10764

zbMATH Keywords

continued fractionautomatic sequencepattern sequencepaper-folding sequenceBaum--Sweet sequencelattice profilelinear complexity, expansion complexityRudin--Shapiro sequenceShapiro sequencesum-of-digits sequence

Mathematics Subject Classification ID

Continued fractions (11A55) Normal numbers, radix expansions, Pisot numbers, Salem numbers, good lattice points, etc. (11K16) Automata sequences (11B85) Number-theoretic algorithms; complexity (11Y16)

Abstract: The $N$th linear complexity of a sequence is a measure of predictability. Any unpredictable sequence must have large $N$th linear complexity. However, in this paper we show that for $q$-automatic sequences over $mathbb{F}_q$ the converse is not true. We prove that any (not ultimately periodic) $q$-automatic sequence over $mathbb{F}_q$ has $N$th 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 $N$th linear complexities. These are non-trivial examples of predictable sequences with $N$th linear complexity of largest possible order of magnitude.

Recommendations

• Automatic complexity of shift register sequences
• Linear complexity and expansion complexity of some number theoretic sequences
• Linear Complexity and Random Sequences
• Complexity of automatic sequences
• Pseudorandom sequences derived from automatic sequences

Cites work

• scientific article; zbMATH DE number 4062985 (Why is no real title available?)
• scientific article; zbMATH DE number 1973372 (Why is no real title available?)
• scientific article; zbMATH DE number 2051216 (Why is no real title available?)
• scientific article; zbMATH DE number 2124952 (Why is no real title available?)
• Automatic Sequences
• Counting functions and expected values for the lattice profile at \(n\)
• Ensembles presque périodiques \(k\)-reconnaissables. (Almost periodic \(k\)-recognizable sets)
• Expansion complexity and linear complexity of sequences over finite fields
• Finite automata and arithmetic
• Lattice structure and linear complexity profile of nonlinear pseudorandom number generators
• Linear complexity and related complexity measures
• Linear complexity profile and correlation measure of interleaved sequences
• Linear complexity profile of binary sequences with small correlation measure
• Modular constructions of pseudorandom binary sequences with composite moduli
• On finite pseudorandom binary sequences. II: The Champernowne, Rudin-Shapiro, and Thue-Morse sequences, a further construction
• On the joint linear complexity profile of explicit inversive multisequences
• On the use of expansion series for stream ciphers
• Progress in Cryptology - INDOCRYPT 2003
• Pseudorandom sequences
• Some Notes on the Two-Prime Generator of Order<tex>$2$</tex>
• Subsequences of automatic sequences and uniform distribution
• Suites algébriques, automates et substitutions

Cited in

(15)

• On the boundary sequence of an automatic sequence
• Perfect linear complexity profile and apwenian sequences
• Shift registers fool finite automata
• Decidability and Enumeration for Automatic Sequences: A Survey
• Automated recurrence analysis for almost-linear expected-runtime bounds
• On the joint subword complexity of automatic sequences
• A characterization of \(p\)-automatic sequences as columns of linear cellular automata
• scientific article; zbMATH DE number 1594296 (Why is no real title available?)
• Linear complexity and expansion complexity of some number theoretic sequences
• Automatic complexity of shift register sequences
• Pseudorandom sequences derived from automatic sequences
• On the \(N\)th maximum order complexity and the expansion complexity of a Rudin-Shapiro-like sequence
• ON INTEGER SEQUENCES GENERATED BY LINEAR MAPS
• Complexity of automatic sequences
• Minimum complexity of automatic non sturmian sequences

This page was built for publication: On the \(N\)th linear complexity of automatic sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1747239)