Some computable complexity measures for binary sequences
The aim of this paper is to survey classical as well as recently introduced complexity measures for binary sequences from the point of view of stream ciphers. The focus is on complexity measures that are of lower rank in the hierarchy since they are based on simpler types of machines, but which have the advantage that they can be obtained in an algorithmic manner. Complexity measures based on pattern counting, namely the tree complexity and the Lempel-Ziv complexity, are discussed. Some open problems are stated at the end of the paper. For the entire collection see [Zbl 0974.00035].
- Joint linear complexity of multisequences consisting of linear recurring sequences
- The expected value of the joint linear complexity of periodic multisequences
- Counting functions and expected values for the \(k\)-error linear complexity
- On the linear complexity profile of some new explicit inversive pseudorandom numbers
- On the linear complexity profile of explicit nonlinear pseudorandom numbers.
- Rational complexity of binary sequences, F\(\mathbb{Q}\)SRs, and pseudo-ultrametric continued fractions in \(\mathbb{R}\)
- Joint string complexity for Markov sources: small data matters
- Enumeration results on linear complexity profiles and lattice profiles
- Tree complexity and a doubly exponential gap between structured and random sequences
- On the linear complexity profile of nonlinear congruential pseudorandom number generators of higher orders
- The expectation and variance of the joint linear complexity of random periodic multisequences
- Linear complexity of the Naor-Reingold pseudo-random function
- scientific article; zbMATH DE number 5150220 (Why is no real title available?)
- scientific article; zbMATH DE number 4135865 (Why is no real title available?)
- Nonlinear Complexity of Binary Sequences and Connections with Lempel-Ziv Compression
- On Lempel-Ziv Complexity of Sequences
- scientific article; zbMATH DE number 3954821 (Why is no real title available?)
- Ziv-Lempel complexity for periodic sequences and its cryptographic application
- The independence of two randomness properties of sequences over finite fields
- A Unified View on Sequence Complexity Measures as Isometries
- Sequences of binary strings with relation of conditional simplicity
- On average sequence complexity
- Binary sequences. III: Complexity versus homogeneity and symmetry
- On the \(k\)-error linear complexity over \({\mathbb F}_p\) of Legendre and Sidelnikov sequences
- On the linear complexity of Sidel'nikov sequences over nonprime fields
This page was built for publication: Some computable complexity measures for binary sequences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4330647)
