Algorithmic complexity and stochastic properties of finite binary sequences

V. V. V'yugin

Research output: Contribution to journalArticlepeer-review

30 Citations (Scopus)

Abstract

This paper is a survey of concepts and results related to simple Kolmogorov complexity, prefix complexity and resource-bounded complexity. We also consider a new type of complexitystatistical complexity closely related to mathematical statistics. Unlike other discoverers of algorithmic complexity, A. N. Kolmogorov's leading motive was developing on its basis a mathematical theory more adequately substantiating applications of probability theory, mathematical statistics and information theory. Kolmogorov wanted to deduce properties of a random object from its complexity characteristics without use of the notion of probability. In the first part of this paper we present several results in this direction. Though the subsequent development of algorithmic complexity and randomness was different, algorithmic complexity has successful applications in a traditional probabilistic framework. In the second part of the paper we consider applications to the estimation of parameters and the definition of Bernoulli sequences. All considerations have finite combinatorial character.

Original languageEnglish
Pages (from-to)315-317
Number of pages3
JournalComputer Journal
Volume42
Issue number4
DOIs
Publication statusPublished - 1999
Externally publishedYes

Fingerprint

Dive into the research topics of 'Algorithmic complexity and stochastic properties of finite binary sequences'. Together they form a unique fingerprint.

Cite this