Abstract:
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.
Fulltext:
PDF file (1238 kB)