✦ LIBER ✦
Tree Complexity and a Doubly Exponential Gap between Structured and Random Sequences
✍ Scribed by Harald Niederreiter; Michael Vielhaber
- Publisher
- Elsevier Science
- Year
- 1996
- Tongue
- English
- Weight
- 215 KB
- Volume
- 12
- Category
- Article
- ISSN
- 0885-064X
No coin nor oath required. For personal study only.
✦ Synopsis
This paper introduces a new complexity measure for binary sequences, the tree complexity. The tree complexity of a sequence grows asymptotically like O(2 2 h ) (h the height of the tree) for random sequences. Functions in F 2 [[x]] can be identified with their coefficient sequence. Under this aspect we will show that the tree complexity is O(1) for all algebraic sequences in F ȍ 2 . This doubly exponential gap may serve as an indicator of ''simply'' structured sequences and furthermore it defines certain classes within the vast set of transcendental sequences.