On the Nth linear complexity of automatic sequences

DOI10.1016/J.JNT.2017.11.008zbMATH Open1416.11042arXiv1711.10764OpenAlexW2962853512MaRDI QIDQ1747239FDOQ1747239

Authors: László Mérai, Arne Winterhof 

Publication date: 4 May 2018

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

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.

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

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

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)

Cites Work

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

Cited In (15)

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