Tree complexity and a doubly exponential gap between structured and random sequences

DOI10.1006/JCOM.1996.0014MaRDI QIDQ2565197zbMATH OpenOpenAlexFDO

Authors Michael Vielhaber, Harald Niederreiter

Publication date 17 August 1997

Published in Journal of Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jcom.1996.0014

zbMATH Keywords

tree complexity

Mathematics Subject Classification ID

Data encryption (aspects in computer science) (68P25)

Review text

The authors introduce a new complexity measure for binary sequences, the tree complexity. They show that the tree complexity grows asymptotically like \(O(2^{2^h})\) (\(h\) height of the tree) for random sequences and like \(O(1)\) for algebraic sequences.

Recommendations

• scientific article; zbMATH DE number 1740058
• scientific article; zbMATH DE number 503334
• scientific article; zbMATH DE number 1747450
• scientific article; zbMATH DE number 4211347
• Randomness for computable measures and initial segment complexity

Cited in

(1)

• Pattern sets for \(\mathbb{F}_q\)-sequences invariant under the continued fraction operator K (the Berlekamp-Massey algorithm)

This page was built for publication: Tree complexity and a doubly exponential gap between structured and random sequences

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