Exact Constructive and Computable Dimensions

ResearchSpace/Manakin Repository

Show simple item record

dc.contributor.author Staiger, L en
dc.date.accessioned 2017-02-07T03:37:18Z en
dc.date.available 2017-02-07T03:37:18Z en
dc.date.issued 2016 en
dc.identifier.citation CDMTCS Research Reports CDMTCS-502 (2016) en
dc.identifier.issn 1178-3540 en
dc.identifier.uri http://hdl.handle.net/2292/31759 en
dc.description.abstract In this paper we derive several results which generalise the constructive dimension of (sets of) infinite strings to the case of exact dimension. We start with proving a martingale characterisation of exact Hausdorff dimension. Then using semi-computable super-martingales we introduce the notion of exact constructive dimension of (sets of) infinite strings. This allows us to derive several bounds on the complexity functions of infinite strings, that is, functions assigning to every finite prefix its Kolmogorov complexity. In particular, it is shown that the exactHausdorff dimension of a set of infinite strings lower bounds the maximumcomplexity function of strings in this set. Furthermore,we showa result bounding the exact Hausdorff dimension of a set of strings having a certain computable complexity function as upper bound. en
dc.publisher Department of Computer Science, The University of Auckland, New Zealand en
dc.relation.ispartofseries CDMTCS Research Report Series en
dc.rights Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher. en
dc.rights.uri https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm en
dc.source.uri https://www.cs.auckland.ac.nz/research/groups/CDMTCS/researchreports/index.php en
dc.title Exact Constructive and Computable Dimensions en
dc.type Technical Report en
dc.subject.marsden Fields of Research en
dc.rights.holder The author(s) en
dc.rights.accessrights http://purl.org/eprint/accessRights/OpenAccess en

Full text options

This item appears in the following Collection(s)

Show simple item record


Search ResearchSpace

Advanced Search