Please use this identifier to cite or link to this item: http://repositorio.inesctec.pt/handle/123456789/7054
Title: A Safe Approximation for Kolmogorov Complexity
Authors: Bloem,P
Mota,F
de Rooij,S
Luís Filipe Antunes
Adriaans,P
Issue Date: 2014
Abstract: Kolmogorov complexity (K) is an incomputable function. It can be approximated from above but not to arbitrary given precision and it cannot be approximated from below. By restricting the source of the data to a specific model class, we can construct a computable function (kappa) over bar to approximate K in a probabilistic sense: the probability that the error is greater than kappa decays exponentially with kappa. We apply the same method to the normalized information distance (NID) and discuss conditions that affect the safety of the approximation.
URI: http://repositorio.inesctec.pt/handle/123456789/7054
http://dx.doi.org/10.1007/978-3-319-11662-4_24
metadata.dc.type: conferenceObject
Publication
Appears in Collections:CRACS - Articles in International Conferences

Files in This Item:
File Description SizeFormat 
P-009-YXQ.pdf324.75 kBAdobe PDFThumbnail
View/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.