TY - GEN
T1 - Axiomatizing resource bounds for measure
AU - Gu, Xiaoyang
AU - Lutz, Jack H.
AU - Nandakumar, Satyadev
AU - Royer, James S.
PY - 2011
Y1 - 2011
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 -