Complexity of strings in the class of Markov sources
IEEE Transactions on Information TheoryPublished 1 July 1986
J. Rissanen
Citations194
SJR quartileQ1
SJR score1.46
SNIP1.76
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
Shannon's self-information of a string is generalized to its complexity relative to the class of finite-state-machine (FSM) defined sources by a theorem stating that, asymptotically, the mean complexity provides a tight lower bound for the mean length of all so-called regular codes.
Abstract
Shannon's self-information of a string is generalized to its complexity relative to the class of finite-state-machine (FSM) defined sources. Unlike an earlier generalization, the new one is valid for both short and long strings. The definition is justified in part by a theorem stating that, asymptotically, the mean complexity provides a tight lower bound for the mean length of all so-called regular codes. This also generalizes Shannon's noiseless coding theorem. For a large subclass of FSM sources a simple algorithm is described for computing the complexity.
Keywords
Computer ScienceBiochemistry, Genetics and Molecular Biology
IEEE Transactions on Information TheoryCompression of individual sequences via variable-rate coding
3,452 Citations1978J. Ziv, A. Lempel
The proposed concept of compressibility is shown to play a role analogous to that of entropy in classical information theory where one deals with probabilistic ensembles of sequences rather than with individual sequences.
IEEE Transactions on Information TheoryOn the Complexity of Finite Sequences
2,700 Citations1976A. Lempel, J. Ziv
A new approach to the problem of evaluating the complexity ("randomness") of finite sequences is presented, related to the number of steps in a self-delimiting production process by which a given sequence is presumed to be generated.
International Journal of Computer MathematicsThree approaches to the quantitative definition of information<sup>*</sup>
2,013 Citations1968A. N. Kolmogorov
The Annals of StatisticsA Universal Prior for Integers and Estimation by Minimum Description Length
1,667 Citations1983J. Rissanen
Estimation based upon the principle of minimizing the total number of binary digits required to rewrite the observed data, when each observation is given with some precision is studied.
IEEE Transactions on Information TheoryUniversal codeword sets and representations of the integers
1,156 Citations1975Peter Eliaš
An application is the construction of a uniformly universal sequence of codes for countable memoryless sources, in which the n th code has a ratio of average codeword length to source rate bounded by a function of n for all sources with positive rate.
Information and ControlA formal theory of inductive inference. Part I
1,149 Citations1964Ray J. Solomonoff
Journal of the ACMOn the Length of Programs for Computing Finite Binary Sequences
917 Citations1969Gregory J. Chaitin
An attempt is made to carry out a program for defining the concept of a random or patternless, finite binary sequence, and for subsequently defining arandom or patterned, infinite binary sequence to be a sequence whose initial segments are all random orpatternless finite binary sequences.
Journal of the ACMOn the Length of Programs for Computing Finite Binary Sequences
912 Citations1966Gregory J. Chaitin
An application to the problem of defining a patternless sequence is proposed in terms of the concepts here developed to study the use of Turing machines for calculating finite binary sequences.
IEEE Transactions on Information TheoryUniversal coding, information, prediction, and estimation
903 Citations1984J. Rissanen
A connection between universal codes and the problems of prediction and statistical estimation is established, and a known lower bound for the mean length of universal codes is sharpened and generalized, and optimum universal codes constructed.
IEEE Transactions on Information TheoryA universal data compression system
637 Citations1983J. Rissanen
A universal data compression algorithm is described which is capable of compressing long strings generated by a "finitely generated" source, with a near optimum per symbol length without prior knowledge of the source.
IEEE Transactions on Information TheoryThe performance of universal encoding
542 Citations1981Rafail Krichevsky, V. К. Trofimov
Universal coding theory is surveyed from the viewpoint of the interplay between delay and redundancy and the price for universality turns out to be acceptably small.
IEEE Transactions on Information TheoryUniversal modeling and coding
463 Citations1981J. Rissanen, Glen G. Langdon
A general class of so-called first-in first-out (FIFO) arithmetic codes is described which require no alphabet extension devices and which therefore can be used in conjunction with the best models.
IEEE Transactions on Information TheoryUniversal noiseless coding
372 Citations1973L. Davisson
This paper considers noiseless coding for sources with unknown parameters, primarily in terms of variable-length coding, with performance measured as a function of the coding redundancy relative to the per-letter conditional source entropy given the unknown parameter.
IEEE Transactions on Information TheoryThe prediction error of stationary Gaussian time series of unknown covariance
73 Citations1965L. Davisson
The asymptotic form of the mean square prediction error is found for a stationary Gaussian time series when the prediction is a linear weighting of the immediate past, the weights being "learned" from the data.
IEEE Transactions on Information TheoryEfficient universal noiseless source codes
64 Citations1981L. Davisson, Robert J. McEliece +2 more
Efficient implementable universal source coding techniques are discussed in this paper and several techniques for constructing universal noiseless source codes for memoryless sources are presented and their redundancies are compared with the bounds.
IEEE Transactions on Information TheoryMinimax noiseless universal coding for Markov sources
64 Citations1983L. Davisson
Upper and lower bounds are presented on the minimax redundancy for Markov source noiseless block-to-variable universal coding, where the number of states, block size, and Markov order are arbitrary but finite.
IEEE Transactions on Information TheoryRobust noiseless source coding through a game theoretical approach
18 Citations1983D. Kazakos
It is shown that if the class of probability distributions allowed is convex, then there is a saddle point solution which is determined by the maximum entropy distribution of the convex class.