MURAL - Maynooth University Research Archive Library



    Generic Density and Small Span Theorem


    Moser, Philippe (2008) Generic Density and Small Span Theorem. Information and Computation, 206 (1). pp. 1-14. ISSN 0890-5401

    [thumbnail of PM-Generic-2008.pdf]
    Preview
    Text
    PM-Generic-2008.pdf

    Download (252kB) | Preview

    Abstract

    We refine the genericity concept of Ambos-Spies, by assigning a real number in [0, 1] to every generic set, called its generic density. We construct sets of generic density any E-computable real in [0, 1], and show a relationship between generic density and Lutz resource bounded dimension. We also introduce strong generic density, and show that it is related to packing dimension. We show that all four notions are different. We show that whereas dimension notions depend on the underlying probability measure, generic density does not, which implies that every dimension result proved by generic density arguments, simultaneously holds under any (biased coin based) probability measure. We prove such a result: we improve the small span theorem of Juedes and Lutz, to the packing dimension setting, for k-bounded-truth-table reductions, under any (biased coin) probability measure.
    Item Type: Article
    Additional Information: This is the preprint version of the published article, which is available at DOI: 10.1016/j.ic.2007.10.001
    Keywords: Genericity; Resource-bounded dimension; Small span theorem;
    Academic Unit: Faculty of Science and Engineering > Computer Science
    Item ID: 8243
    Identification Number: 10.1016/j.ic.2007.10.001
    Depositing User: Philippe Moser
    Date Deposited: 25 May 2017 15:31
    Journal or Publication Title: Information and Computation
    Publisher: Elsevier
    Refereed: Yes
    Related URLs:
    URI: https://mural.maynoothuniversity.ie/id/eprint/8243
    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)

    Item control page
    Item control page

    Downloads

    Downloads per month over past year

    Origin of downloads