Polytime, combinatory logic and positive safe induction

DOI10.1007/S001530100105zbMath1042.03015OpenAlexW2032152194MaRDI QIDQ1407533

Andrea Cantini

Publication date: 16 September 2003

Published in: Archive for Mathematical Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s001530100105

zbMATH Keywords

combinatory logicrestricted inductionpolytime

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) First-order arithmetic and fragments (03F30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Metamathematics of constructive systems (03F50) Combinatory logic and lambda calculus (03B40)

Related Items (11)

The provably terminating operations of the subsystem PETJ of explicit mathematics ⋮ Theories with self-application and computational complexity. ⋮ Primitive recursive selection functions for existential assertions over abstract algebras ⋮ Pointwise Transfinite Induction and a Miniaturized Predicativity ⋮ A proof-theoretic characterization of the basic feasible functionals ⋮ Tiered Arithmetics ⋮ Elementary explicit types and polynomial time operations ⋮ On the proof theory of type two functionals based on primitive recursive operations ⋮ Realisability in weak systems of explicit mathematics ⋮ Implicit recursion-theoretic characterizations of counting classes ⋮ Applicative theories for logarithmic complexity classes

This page was built for publication: Polytime, combinatory logic and positive safe induction