A SIMPLE MEASURE OF THE KOLMOGOROV COMPLEXITY

Evgeny Ivanko

2009

Abstract

In this article we propose a simple method to estimate the Kolmogorov complexity of a finite word written over a finite alphabet. Usually it is estimated by the ratio of the length of a word’s archive to the original length of the word. This approach is not satisfactory for the theory of information because it does not give an abstract measure. Moreover Kolmogorov complexity approach is not satisfactory in the practical tasks of the compressibility estimation because it measures the potential compressibility by means of the compression itself. There is another measure of a word’s complexity - subword complexity, which is equal to the number of different subwords in the word. We show the computation difficulties connected with the usage of subword complexity and propose a new simple measure of a word’s complexity, which is practically convenient development of the notion of subword complexity.

Paper Citation

in Harvard Style

Ivanko E. (2009). A SIMPLE MEASURE OF THE KOLMOGOROV COMPLEXITY . In Proceedings of the International Conference on Knowledge Discovery and Information Retrieval - Volume 1: KDIR, (IC3K 2009) ISBN 978-989-674-011-5, pages 5-9. DOI: 10.5220/0002273000050009

in Bibtex Style

@conference{kdir09,
author={Evgeny Ivanko},
title={A SIMPLE MEASURE OF THE KOLMOGOROV COMPLEXITY},
booktitle={Proceedings of the International Conference on Knowledge Discovery and Information Retrieval - Volume 1: KDIR, (IC3K 2009)},
year={2009},
pages={5-9},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0002273000050009},
isbn={978-989-674-011-5},
}

in EndNote Style

TY - CONF
JO - Proceedings of the International Conference on Knowledge Discovery and Information Retrieval - Volume 1: KDIR, (IC3K 2009)
TI - A SIMPLE MEASURE OF THE KOLMOGOROV COMPLEXITY
SN - 978-989-674-011-5
AU - Ivanko E.
PY - 2009
SP - 5
EP - 9
DO - 10.5220/0002273000050009