Automatic complexity of shift register sequences

Bjørn Kjos-Hanssen

doi:10.1016/j.disc.2018.05.015

paper

Automatic complexity of shift register sequences

arXiv:1607.08226 · doi:10.1016/j.disc.2018.05.015

Abstract

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 (lo g^{2} n)$ , where $n$ is the length of $x$ . In contrast, Hyde has shown $A_{N} (y) \leq n /2 + 1$ for all sequences $y$ of length $n$ .

Preliminary version: "Shift registers fool finite automata", Lecture Notes in Computer Science 10388 (2017), 170-181, Workshop on Logic, Language, Information and Computation (WoLLIC) 2017

Cited by in corpus (1)

Normal Sequences with Non-Maximal Automatic Complexity