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

    Download (312kB) | Preview

    Share your research

    Twitter Facebook LinkedIn GooglePlus Email more...

    Add this article to your Mendeley library


    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:
    Depositing User: Philippe Moser
    Date Deposited: 04 Nov 2015 14:47
    Journal or Publication Title: Theoretical Computer Science
    Publisher: Elsevier
    Refereed: Yes
    Use Licence: This item is available under a Creative Commons Attribution Non Commercial Share Alike Licence (CC BY-NC-SA). Details of this licence are available here

    Repository Staff Only(login required)

    View Item Item control page


    Downloads per month over past year

    Origin of downloads