Switch to: Citations

Add references

You must login to add references.
  1. Structure and definability in general bounded arithmetic theories.Chris Pollett - 1999 - Annals of Pure and Applied Logic 100 (1-3):189-245.
    The bounded arithmetic theories R2i, S2i, and T2i are closely connected with complexity theory. This paper is motivated by the questions: what are the Σi+1b-definable multifunctions of R2i? and when is one theory conservative over another? To answer these questions we consider theories , and where induction is restricted to prenex formulas. We also define which has induction up to the 0 or 1-ary L2-terms in the set τ. We show and and for . We show that the -multifunctions of (...)
    Download  
     
    Export citation  
     
    Bookmark   17 citations  
  • Translating IΔ0 + exp Proofs into Weaker Systems.Chris Pollett - 2000 - Mathematical Logic Quarterly 46 (2):249-256.
    The purpose of this paper is to explore the relationship between IΔ0 + exp and its weaker subtheories. We give a method of translating certain classes of IΔ0 + exp proofs into weaker systems of arithmetic such as Buss' systems S2. We show if IEi ⊢ A with a proof P of expind-rank ≤ n + 1where all or have bounding terms not containing function symbols, then Si2 ⊇ IEi,2 ⊢ An. Here A is not necessarily a bounded formula. For (...)
    Download  
     
    Export citation  
     
    Bookmark   1 citation  
  • Multifunction algebras and the provability of PH↓.Chris Pollett - 2000 - Annals of Pure and Applied Logic 104 (1-3):279-303.
    We introduce multifunction algebras B i τ where τ is a set of 0 or 1-ary terms used to bound recursion lengths. We show that if for all ℓ ∈ τ we have ℓ ∈ O then B i τ = FP Σ i−1 p , those multifunctions computable in polynomial time with at most O )) queries to a Σ i−1 p witness oracle for ℓ ∈ τ and p a polynomial. We use our algebras to obtain independence results (...)
    Download  
     
    Export citation  
     
    Bookmark   12 citations