MURAL - Maynooth University Research Archive Library



    Resource-bounded Measure on Probabilistic Classes


    Moser, Philippe (2008) Resource-bounded Measure on Probabilistic Classes. Information Processing Letters, 106 (6). pp. 241-245. ISSN 0020-0190

    [img] Download (171kB)


    Share your research

    Twitter Facebook LinkedIn GooglePlus Email more...



    Add this article to your Mendeley library


    Abstract

    We extend Lutz’s resource-bounded measure to probabilistic classes, and obtain notions of resource-bounded measure on probabilistic complexity classes such as BPE and BPEXP. Unlike former attempts, our resource bounded measure notions satisfy all three basic measure properties, that is every singleton {L} has measure zero, the whole space has measure one, and "enumerable infinite unions" of measure zero sets have measure zero.

    Item Type: Article
    Additional Information: Preprint version of original published article: Moser, Philippe, Resource-bounded measure on probabilistic classes in Information Processing Letters, Volume 106, Issue 6, 15 June 2008, Pages 241-245, http://www.sciencedirect.com/ doi:10.1016/j.ipl.2007.11.019
    Keywords: Resource-bounded Measure; Probabilistic complexity classes; Lutz;
    Academic Unit: Faculty of Science and Engineering > Computer Science
    Item ID: 3501
    Depositing User: Philippe Moser
    Date Deposited: 29 Feb 2012 14:26
    Journal or Publication Title: Information Processing Letters
    Publisher: Elsevier
    Refereed: Yes
    URI:

    Repository Staff Only(login required)

    View Item Item control page

    Downloads

    Downloads per month over past year