Elementary arithmetic

DOI10.1016/j.apal.2004.10.012zbMath1065.03040OpenAlexW4205910551MaRDI QIDQ1772782

G. E. Ostrin, Stanley S. Wainer

Publication date: 21 April 2005

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.apal.2004.10.012

zbMATH Keywords

cut eliminationcomplexity classesprovably recursive functionssyntactically simple theories

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) Recursive functions and relations, subrecursive hierarchies (03D20)

Related Items

2007 European Summer Meeting of the Association for Symbolic Logic: Logic Colloquium '07, Pointwise Transfinite Induction and a Miniaturized Predicativity, An arithmetic for polynomial-time computation, Inductive definitions over a predicative arithmetic

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new recursion-theoretic characterization of the polytime functions
• Fragments of HA based on \(\Sigma_ 1\)-induction
• Fragments of Heyting arithmetic