Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > SLOW GROWING FUNCTION:
Reports tagged with Slow growing function:
TR11-014 | 3rd February 2011
Antoine Taveneaux

Towards an axiomatic system for Kolmogorov complexity

Revisions: 1

In \cite{shenpapier82}, it is shown that four basic functional properties are enough to characterize plain Kolmogorov complexity, hence obtaining an axiomatic characterization of this notion. In this paper, we try to extend this work, both by looking at alternative axiomatic systems for plain complexity and by considering potential axiomatic systems ... more >>>




ISSN 1433-8092 | Imprint