×

Complexity of strings in the class of Markov sources. (English) Zbl 0621.94005

The author defines a different notion of complexity in a nonasymptotic way, and proves, for the important class of finite-state-machine (FSM) defined sources, that it represents, assymptotically the minimum mean code-length for all sources with the exception of a set of mesure zero. For a useful subclass of FSM, which include the Markov sources, he describes a fairly simple algorithm for computing, approximately, its complexity.
Reviewer: F.Pessoa

MSC:

94A15 Information theory (general)
94A17 Measures of information, entropy
PDFBibTeX XMLCite
Full Text: DOI