TY - GEN

T1 - Axiomatizing resource bounds for measure

AU - Gu, Xiaoyang

AU - Lutz, Jack H.

AU - Nandakumar, Satyadev

AU - Royer, James S.

PY - 2011/9/26

Y1 - 2011/9/26

N2 - Resource-bounded measure is a generalization of classical Lebesgue measure that is useful in computational complexity. The central parameter of resource-bounded measure is the resource bound Δ, which is a class of functions. Most applications of resource-bounded measure use only the "measure-zero/measure-one fragment" of the theory. For this fragment, Δ can be taken to be a class of type-one functions. However, in the full theory of resource-bounded measurability and measure, the resource bound Δ also contains type-two functionals. To date, both the full theory and its zero-one fragment have been developed in terms of a list of example resource bounds. This paper replaces this list-of-examples approach with a careful investigation of the conditions that suffice for a class Δ to be a resource bound.

AB - Resource-bounded measure is a generalization of classical Lebesgue measure that is useful in computational complexity. The central parameter of resource-bounded measure is the resource bound Δ, which is a class of functions. Most applications of resource-bounded measure use only the "measure-zero/measure-one fragment" of the theory. For this fragment, Δ can be taken to be a class of type-one functions. However, in the full theory of resource-bounded measurability and measure, the resource bound Δ also contains type-two functionals. To date, both the full theory and its zero-one fragment have been developed in terms of a list of example resource bounds. This paper replaces this list-of-examples approach with a careful investigation of the conditions that suffice for a class Δ to be a resource bound.

UR - http://www.scopus.com/inward/record.url?scp=80053041226&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=80053041226&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-21875-0_11

DO - 10.1007/978-3-642-21875-0_11

M3 - Conference contribution

AN - SCOPUS:80053041226

SN - 9783642218743

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 102

EP - 111

BT - Models of Computation in Context - 7th Conference on Computability in Europe, CiE 2011, Proceedings

T2 - 7th Conference on Computability in Europe, CiE 2011

Y2 - 27 June 2011 through 2 July 2011

ER -