The structure of information distribution in an infinite sequence

V. D. Solov'ev

Diskretnaya Matematika, Tome 8 (1996) no. 2, pp. 97-107.

Résumé

We pose the problem to study the structure of distribution of information in infinite sequences. To solve this problem, we suggest an approach based on restoring the whole sequence by its subsequence. To realize this approach, we introduce the needed apparatus, in particular, the notions of rigid and densely packed sequences which characterize the degree of redundancy of information in the sequence. We consider the automaton model and within its context prove the existence of densely packed and rigid sequences and find some their properties, in particular, their relations to the complexity of predicting the next element in a sequence.We demonstrate the possibility to apply the results obtained to the study of the structure of degrees of automaton transformations, and prove that any finite partially ordered set possessing a minimal and maximal elements is isomorphic to the initial segment of the structure of degrees of automaton transformations of sequences over the alphabet $\{0,1\}$. We discuss how these results relate to the coding and information theory.This work was supported by the Russian Foundation for Basic Researches, Grant 93–011–16004.