Induction rules in bounded arithmetic
From MaRDI portal
Publication:2309507
Abstract: We study variants of Buss's theories of bounded arithmetic axiomatized by induction schemes disallowing the use of parameters, and closely related induction inference rules. We put particular emphasis on induction schemes, which were so far neglected in the literature. We present inclusions and conservation results between the systems (including a witnessing theorem for and of a new form), results on numbers of instances of the axioms or rules, connections to reflection principles for quantified propositional calculi, and separations between the systems.
Recommendations
Cites work
- scientific article; zbMATH DE number 3912375 (Why is no real title available?)
- scientific article; zbMATH DE number 4039892 (Why is no real title available?)
- scientific article; zbMATH DE number 4075030 (Why is no real title available?)
- scientific article; zbMATH DE number 3557241 (Why is no real title available?)
- scientific article; zbMATH DE number 806747 (Why is no real title available?)
- scientific article; zbMATH DE number 819737 (Why is no real title available?)
- scientific article; zbMATH DE number 1420845 (Why is no real title available?)
- scientific article; zbMATH DE number 227056 (Why is no real title available?)
- An Application of Boolean Complexity to Separation Problems in Bounded Arithmetic
- Approximate counting by hashing in bounded arithmetic
- Bounded arithmetic and the polynomial hierarchy
- Collapsing modular counting in bounded arithmetic and constant depth propositional proofs
- Consequences of the provability of NP ⊆ P/poly
- Diophantine induction
- Existentially Closed Models and Conservation Results in Bounded Arithmetic
- Fragments of Bounded Arithmetic and Bounded Query Classes
- Functions provably total in $I^{-}Σ_{n}$
- Induction rules, reflection principles, and provably recursive functions
- Lifting independence results in bounded arithmetic
- Local induction and provably total computable functions
- Logical foundations of proof complexity
- Notes on polynomially bounded arithmetic
- On parameter free induction schemas
- On theories of bounded arithmetic for \(\mathrm{NC}^1\)
- On Σ1‐definable Functions Provably Total in I ∏
- Parameter free induction and provably total computable functions
- Quantified propositional calculi and fragments of bounded arithmetic
- Relating the bounded arithmetic and polynomial time hierarchies
- Simulating non-prenex cuts in quantified propositional calculus
- The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection
- The provably total search problems of bounded arithmetic
- Witnessing functions in bounded arithmetic and search problems
Cited in
(11)- An induction principle for consequence in arithmetic universes
- Universal Induction and True Universal Arithmetic
- Finite multiplicity theorems for induction and restriction
- scientific article; zbMATH DE number 3880682 (Why is no real title available?)
- Unprovability results for clause set cycles
- Restricted polynomial induction versus ordinary induction
- scientific article; zbMATH DE number 3948262 (Why is no real title available?)
- Restricted polynomial induction versus parameter free ordinary induction
- Induction and Skolemization in saturation theorem proving
- Well-behaved principles alternative to bounded induction
- scientific article; zbMATH DE number 5058824 (Why is no real title available?)
This page was built for publication: Induction rules in bounded arithmetic
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2309507)
