Elementary explicit types and polynomial time operations

DOI10.1002/MALQ.200810004MaRDI QIDQ3632522zbMATH OpenOpenAlexFDO

Authors 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

applicative theoriescomputability on the set of binary wordsconservativenessfeasible operationsFeferman's explicit mathematicsnamingproof theory

Mathematics Subject Classification ID

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

Recommendations

• Polynomial time operations in explicit mathematics
• A feasible theory of truth over combinatory algebra
• Feasible Operations and Applicative Theories Based on λη
• scientific article; zbMATH DE number 1163982
• Characterising polynomial time computable functions using theories with weak set existence principles
• scientific article; zbMATH DE number 4139739
• A foundational delineation of poly-time
• scientific article; zbMATH DE number 2110623
• Intuitionistic formal theories with realizability in subrecursive classes
• Polytime, combinatory logic and positive safe induction

Cites work

• A new Characterization of Type-2 Feasibility
• A proof-theoretic characterization of the basic feasible functionals
• Constructivism in mathematics. An introduction. Volume I
• Functional interpretations of feasibly constructive arithmetic
• scientific article; zbMATH DE number 3900744 (Why is no real title available?)
• scientific article; zbMATH DE number 3687373 (Why is no real title available?)
• scientific article; zbMATH DE number 176200 (Why is no real title available?)
• scientific article; zbMATH DE number 3556031 (Why is no real title available?)
• scientific article; zbMATH DE number 2222014 (Why is no real title available?)
• Polynomial time operations in explicit mathematics
• Polytime, combinatory logic and positive safe induction
• Theories with self-application and computational complexity.

Cited in

(9)

• A feasible theory of truth over combinatory algebra
• Weak theories of operations and types
• Realisability in weak systems of explicit mathematics
• Characterizing Polynomial and Exponential Complexity Classes in Elementary Lambda-Calculus
• scientific article; zbMATH DE number 4148067 (Why is no real title available?)
• Polynomial time operations in explicit mathematics
• Feasible Operations and Applicative Theories Based on λη
• Admissible closures of polynomial time computable arithmetic
• The provably terminating operations of the subsystem PETJ of explicit mathematics

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3632522)