scientific article; zbMATH DE number 440477
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].
- On parallel hierarchies and R_k^i
- Determining inference semantics for disjunctive logic programs
- Characterising polynomial time computable functions using theories with weak set existence principles
- scientific article; zbMATH DE number 440487 (Why is no real title available?)
- scientific article; zbMATH DE number 4006252 (Why is no real title available?)
- Provably total functions of intuitionistic bounded arithmetic
- An unexpected separation result in Linearly Bounded Arithmetic
- Provably total functions of Basic Arithmetic
- Omission-based abstraction for answer set programs
- The computational power of bounded arithmetic from the predicative viewpoint
- Witnesses for Answer Sets of Logic Programs
- On parallel hierarchies and R ki
- Mining the surface: witnessing the low complexity theorems of arithmetic
- Contrastive explanations for answer-set programs
- Witnessing flows in arithmetic
- Polynomially bounded recursive realizability
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3140634)