Elementary explicit types and polynomial time operations

DOI10.1002/MALQ.200810004zbMath1171.03036OpenAlexW2009311883MaRDI QIDQ3632522

Daria Spescha, Thomas Strahm

Publication date: 11 June 2009

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

Full work available at URL: https://doi.org/10.1002/malq.200810004

zbMATH Keywords

conservativenessproof theoryapplicative theoriesnamingFeferman's explicit mathematicsfeasible operationscomputability on the set of binary words

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Second- and higher-order arithmetic and fragments (03F35) Metamathematics of constructive systems (03F50)

Related Items (4)

A feasible theory of truth over combinatory algebra ⋮ Admissible closures of polynomial time computable arithmetic ⋮ The provably terminating operations of the subsystem PETJ of explicit mathematics ⋮ Realisability in weak systems of explicit mathematics

Cites Work

• Functional interpretations of feasibly constructive arithmetic
• A proof-theoretic characterization of the basic feasible functionals
• Constructivism in mathematics. An introduction. Volume I
• Polytime, combinatory logic and positive safe induction
• Theories with self-application and computational complexity.
• Polynomial time operations in explicit mathematics
• A new Characterization of Type-2 Feasibility
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Elementary explicit types and polynomial time operations