Perfect linear complexity profile and apwenian sequences

DOI10.1016/J.FFA.2020.101761zbMATH Open1464.11077arXiv2008.12160OpenAlexW3090185765MaRDI QIDQ1994979FDOQ1994979

Authors: Guo-Niu Han, Jean-Paul Allouche, Harald Niederreiter 

Publication date: 18 February 2021

Published in: Finite Fields and their Applications (Search for Journal in Brave)

Abstract: Sequences with {em perfect linear complexity profile} were defined more than thirty years ago in the study of measures of randomness for binary sequences. More recently {em apwenian sequences}, first with values $pm1$, then with values in $0,1$, were introduced in the study of Hankel determinants of automatic sequences. We explain that these two families of sequences are the same up to indexing, and give consequences and questions that this implies. We hope that this will help gathering two distinct communities of researchers.

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

Recommendations

• scientific article; zbMATH DE number 4062985
• Linear complexity profiles: Hausdorff dimensions for almost perfect profiles and measures for general profiles
• Sequences with almost perfect linear complexity profiles and curves over finite fields
• On the limit of maximal density of sequences with a perfect linear complexity profile
• scientific article; zbMATH DE number 1008452

zbMATH Keywords

automatic sequencesperfect linear complexity profileapwenian sequencescontinued fractions with partial quotients with bounded degreegeneralized Rueppel sequences

Mathematics Subject Classification ID

Shift register sequences and sequences over finite alphabets in information and communication theory (94A55) Continued fractions and generalizations (11J70) Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Automata sequences (11B85) Pseudo-random numbers; Monte Carlo methods (11K45) Metric theory of continued fractions (11K50)

Cites Work

• Folded continued fractions
• Handbook of finite fields
• Automatic Sequences
• Continued fractions of algebraic power series in characteristic 2
• Hankel determinants of the Thue-Morse sequence
• Continued fractions for certain algebraic power series
• Badly approximable power series in characteristic 2
• Diophantine approximation exponents and continued fractions for algebraic power series
• Hyperquadratic continued fractions in odd characteristic with partial quotients of degree one
• Linear Complexity and Random Sequences
• Title not available (Why is that?)
• Linear complexity profile of binary sequences with small correlation measure
• Computer assisted proof for Apwenian sequences
• The Probabilistic Theory of Linear Complexity
• Rational functions with partial quotients of small degree in their continued fraction expansion
• On the \(N\)th linear complexity of automatic sequences
• A note on hyperquadratic continued fractions in characteristic 2 with partial quotients of degree 1
• Sur le développement en fraction continue de la série de Baum et Sweet
• On the use of expansion series for stream ciphers
• Expansion complexity and linear complexity of sequences over finite fields
• ON THE GOWERS NORM OF PSEUDORANDOM BINARY SEQUENCES
• Continued fraction expansions of rational expressions with irreducible denominators in characteristic 2
• Orthogonal sequences of polynomials over arbitrary fields
• Algebraic and badly approximable power series over a finite field
• Quartic power series in $
• Flat power series over a finite field
• Constructions of sequences with almost perfect linear complexity profile from curves over finite fields
• Hyperquadratic power series in \(\mathbb F_3((T^{-1}))\) with partial quotients of degree 1
• On the continued fractions of quadratic surds
• On the automaticity of the Hankel determinants of a family of automatic sequences
• Thue-Morse constant is not badly approximable
• Title not available (Why is that?)
• Counting functions and expected values for the lattice profile at \(n\)
• An infinite product with bounded partial quotients
• Polynomials with odd orthogonal multiplicity
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Rational functions over finite fields having continued fraction expansions with linear partial quotients
• On the largest degree of the partial quotients in continued fraction expansions over the field of formal Laurent series
• Title not available (Why is that?)
• Cellular automata in stream ciphers
• Title not available (Why is that?)
• Continued fractions of Laurent series with partial quotients from a given set
• On the Expansion Complexity of Sequences Over Finite Fields

Cited In (9)

• Maximum order complexity of the sum of digits function in Zeckendorf base and polynomial subsequences
• The Pagoda sequence: a ramble through linear complexity, number walls, D0L sequences, finite state automata, and aperiodic tilings
• Title not available (Why is that?)
• The Thue-Morse continued fractions in characteristic 2 are algebraic
• Criteria for apwenian sequences
• Pseudorandom sequences derived from automatic sequences
• Sequences with almost perfect linear complexity profiles and curves over finite fields
• Computer assisted proof for Apwenian sequences
• On the limit of maximal density of sequences with a perfect linear complexity profile

This page was built for publication: Perfect linear complexity profile and apwenian sequences

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