Functional interpretations of feasibly constructive arithmetic. Abstract

MaRDI QIDQ4035305zbMATH OpenFDO

Authors Alasdair Urquhart, Stephen Cook

Publication date 18 May 1993

zbMATH Keywords

feasible functionalfeasibly constructive proof

Mathematics Subject Classification ID

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

Review text

[For the entire collection see Zbl 0753.00018.] Announcement of the authors' results presented in full detail in their paper with the same title in Ann. Pure Appl. Logic 63, No. 2, 103-200 (1993).

Recommendations

• Functional interpretations of feasibly constructive arithmetic
• Concepts and aims of functional interpretations: Towards a functional interpretation of constructive set theory
• Bounded functional interpretation and feasible analysis
• scientific article; zbMATH DE number 4004179
• Functional interpretation and inductive definitions

Cited in

(7)

• Bounded arithmetic for NC, ALogTIME, L and NL
• Bounded linear logic: A modular approach to polynomial-time computability
• Semantics vs syntax vs computations: Machine models for type-2 polynomial-time bounded functionals
• Elementary realizability
• A parametrised functional interpretation of Heyting arithmetic
• Structural properties for feasibly computable classes of type two
• On two questions about feasibly constructive arithmetic

This page was built for publication: Functional interpretations of feasibly constructive arithmetic. Abstract

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