Relationship among Complexities of Individual Sequences over Countable Alphabet
Shigeaki Kuzuoka · IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences · 2006
This paper investigates some relations among four com-plexities of sequence over countably infinite alphabet, and shows that two kinds of empirical entropies and the self-entropy regarding a finite state source are asymp-totically equal and lower bounded by the muximun number of phrases in distinct parsing of the sequence. Some connections with source coding theorems are also investigated. Further, we consider the empirical en-tropies with fidelity criterion. 1.