Bounded theories for polyspace computability

DOI10.4171/PM/1936zbMath1371.03047MaRDI QIDQ2450770

Ricardo Bianconi, Emmanuel Sirimal Silva, Gilda Ferreira

Publication date: 16 May 2014

Published in: Portugaliae Mathematica. Nova Série (Search for Journal in Brave)

zbMATH Keywords

cut eliminationbounded arithmeticconservation resultspolyspace computabilityweak analysis

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Cut-elimination and normal-form theorems (03F05) First-order arithmetic and fragments (03F30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Second- and higher-order arithmetic and fragments (03F35) Proof theory in general (including proof-theoretic semantics) (03F03)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The provably total NP search problems of weak second order bounded arithmetic
• Bounded arithmetic and the polynomial hierarchy
• An interpretation of \(S_2^1\) in \(\Sigma_1^b\)-NIA
• Interpretability in Robinson's Q
• A Conservation Result Concerning Bounded Theories and the Collection Axiom
• Fragments of Bounded Arithmetic and Bounded Query Classes
• Groundwork for weak analysis
• A feasible theory for analysis
• Computer Science Logic
• Improved witnessing and local improvement principles for second-order bounded arithmetic
• Counting as integration in feasible analysis

This page was built for publication: Bounded theories for polyspace computability