Automatic complexity of shift register sequences

DOI10.1016/J.DISC.2018.05.015zbMATH Open1422.94024arXiv1607.08226OpenAlexW2806486110WikidataQ129718420 ScholiaQ129718420MaRDI QIDQ724846FDOQ724846

Authors: Bjørn Kjos-Hanssen 

Publication date: 26 July 2018

Published in: Discrete Mathematics (Search for Journal in Brave)

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$.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Shift-register synthesis and BCH decoding
• Title not available (Why is that?)
• Title not available (Why is that?)
• Nondeterministic automatic complexity of overlap-free and almost square-free words
• Coding and Cryptography

Cited In (7)

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