No label defined (Q3140634)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 440477
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 440477

      Statements

      0 references
      0 references
      0 references
      2 December 1993
      0 references
      fragments of bounded arithmetic
      0 references
      definable functions
      0 references
      provably total functions
      0 references
      witnessing theorems
      0 references
      conservation results
      0 references
      This paper investigates the provably total functions of fragments of first- and second-order bounded arithmetic. The (strongly) \(\Sigma_ i^ b\)-definable functions of \(S_ 3^{i-1}\) and \(R_ 3^ i\) are precisely the (strong) \(FP_ 3^{\Sigma^ p_{i-1}} [\text{wit},\log^{O(1)}]\) functions. The \(\Sigma_ i^{1,b}\)- definable functions of \(V_ 2^{i-1}\) and \(U_ 2^ I\) are the \(\text{EXPTIME}^{\Sigma^{1,p}_{i-1}} [\text{wit,poly}]\) functions, and the \(\Sigma_ i^{1,b}\)-definable functions of \(V_ 2^ i\) are the \(\text{EXPTIME}^{\Sigma_ i^{1,p}}\)-functions. The authors give witnessing theorems for these theories and prove conservation results for \(R_ 3^ i\) over \(S_ 3^{i-1}\) and for \(U_ 2^ i\) over \(V_ 2^{i-1}\). For the entire collection see [Zbl 0777.00008].
      0 references

      Identifiers