MURAL - Maynooth University Research Archive Library



    On the polynomial depth of various sets of random strings


    Moser, Philippe (2013) On the polynomial depth of various sets of random strings. Theoretical Computer Science, 477. pp. 96-108. ISSN 0304-3975

    [img]
    Preview
    Download (312kB) | Preview


    Share your research

    Twitter Facebook LinkedIn GooglePlus Email more...



    Add this article to your Mendeley library


    Abstract

    We introduce a general framework for defining the depth of an infinite binary sequence with respect to a class of observers. We show that our general framework captures all depth notions introduced in computability/complexity theory so far. We review most such notions, show how they are particular cases of our general depth framework, and review some classical results about the different depth notions. We use our framework to define new notions of polynomial depth (called monotone poly depth), based on a polynomial version of monotone Kolmogorov complexity. We show that monotone poly depth satisfies all desirable properties of depth notions. We give two natural examples of deep sets, by showing that both the set of Levin random strings and the set of Kolmogorov random strings are monotone poly deep.

    Item Type: Article
    Additional Information: This is the preprint version of the published article, which is available at DOI: 10.1016/j.tcs.2012.10.045
    Keywords: Logical depth; Polynomial depth; Kolmogorov complexity; Levin complexity;
    Academic Unit: Faculty of Science and Engineering > Computer Science
    Item ID: 6525
    Identification Number: https://doi.org/10.1016/j.tcs.2012.10.045
    Depositing User: Philippe Moser
    Date Deposited: 04 Nov 2015 14:47
    Journal or Publication Title: Theoretical Computer Science
    Publisher: Elsevier
    Refereed: Yes
    URI:

    Repository Staff Only(login required)

    View Item Item control page

    Downloads

    Downloads per month over past year