Automatic complexity of shift register sequences

DOI10.1016/J.DISC.2018.05.015MaRDI QIDQ724846zbMATH OpenOpenAlexWikidataFDO

Authors Bjørn Kjos-Hanssen

Publication date 26 July 2018

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

finite automatalinear feedback shift registersautomatic complexity

Mathematics Subject Classification ID

Shift register sequences and sequences over finite alphabets in information and communication theory (94A55)

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)len/2+1$ for all sequences $y$ of length $n$.

Recommendations

• Complexity of automatic sequences
• Complexity of automatic sequences
• Automata calculating the complexity of automatic sequences
• On the \(N\)th linear complexity of automatic sequences
• Minimum complexity of automatic non sturmian sequences
• On the Linear Complexity of Combined Shift Register Sequences
• Reconnaissabilité des substitutions et complexité des suites automatiques
• Publication:4934701
• On the joint subword complexity of automatic sequences
• Enumeration and decidable properties of automatic sequences

Cites work

• scientific article; zbMATH DE number 4023423 (Why is no real title available?)
• scientific article; zbMATH DE number 1747450 (Why is no real title available?)
• scientific article; zbMATH DE number 3422259 (Why is no real title available?)
• Coding and Cryptography
• Nondeterministic automatic complexity of overlap-free and almost square-free words
• Shift-register synthesis and BCH decoding

Cited in

(7)

• On the \(N\)th linear complexity of automatic sequences
• Shift registers fool finite automata
• Conditional automatic complexity and its metrics
• On the joint subword complexity of automatic sequences
• Complexity of automatic sequences
• Automatic complexity of Fibonacci and tribonacci words
• Minimum complexity of automatic non sturmian sequences

This page was built for publication: Automatic complexity of shift register sequences

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