Order:
  1.  12
    Generalized Quantifier and a Bounded Arithmetic Theory for LOGCFL.Satoru Kuroda - 2007 - Archive for Mathematical Logic 46 (5-6):489-516.
    We define a theory of two-sort bounded arithmetic whose provably total functions are exactly those in ${\mathcal{F}_{LOGCFL}}$ by way of a generalized quantifier that expresses computations of SAC 1 circuits. The proof depends on Kolokolova’s conditions for the connection between the provable capture in two-sort theories and descriptive complexity.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  2.  10
    On a Theory for AC0 and the Strength of the Induction Scheme.Satoru Kuroda - 1998 - Mathematical Logic Quarterly 44 (3):417-426.
    We define a fragment of Primitive Recursive Arithmetic by replacing the defining axioms for primitive recursive functions by those for functions in some specific complexity class. In this note we consider such theory for AC0. We present a model-theoretical property of this theory, by means of which we are able to characterize its provably total functions. Next we consider the problem of how strong the induction scheme can be in this theory.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark  
  3.  11
    An Independence Result on Weak Second Order Bounded Arithmetic.Satoru Kuroda - 2001 - Mathematical Logic Quarterly 47 (2):183-186.
    We show that length initial submodels of S12 can be extended to a model of weak second order arithmetic. As a corollary we show that the theory of length induction for polynomially bounded second order existential formulae cannot define the function division.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark