Rissanen, Jorma Complexity of strings in the class of Markov sources. (English) Zbl 0621.94005 IEEE Trans. Inf. Theory 32, 526-532 (1986). 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 Cited in 9 Documents MSC: 94A15 Information theory (general) 94A17 Measures of information, entropy Keywords:Shannon’s self information; entropy; finite-state-machine defined sources; complexity; minimum mean code-length; Markov sources PDFBibTeX XMLCite \textit{J. Rissanen}, IEEE Trans. Inf. Theory 32, 526--532 (1986; Zbl 0621.94005) Full Text: DOI