𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Higher type recursion, ramification and polynomial time

✍ Scribed by Stephen J. Bellantoni; Karl-Heinz Niggl; Helmut Schwichtenberg

Publisher
Elsevier Science
Year
2000
Tongue
English
Weight
126 KB
Volume
104
Category
Article
ISSN
0168-0072

No coin nor oath required. For personal study only.

✦ Synopsis

It is shown how to restrict recursion on notation in all ΓΏnite types so as to characterize the polynomial-time computable functions. The restrictions are obtained by using a ramiΓΏed type structure, and by adding linear concepts to the lambda calculus.

πŸ“œ SIMILAR VOLUMES

Safe recursion with higher types and BCK
Safe recursion with higher types and BCK-algebra
✍ Martin Hofmann πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 314 KB

In previous work the author has introduced a lambda calculus SLR with modal and linear types which serves as an extension of Bellantoni-Cook's function algebra BC to higher types. It is a step towards a functional programming language in which all programs run in polynomial time. In this paper we de

Elementary explicit types and polynomial
Elementary explicit types and polynomial time operations
✍ Daria Spescha; Thomas Strahm πŸ“‚ Article πŸ“… 2009 πŸ› John Wiley and Sons 🌐 English βš– 153 KB

## Abstract This paper studies systems of explicit mathematics as introduced by Feferman [9, 11]. In particular, we propose weak explicit type systems with a restricted form of elementary comprehension whose provably terminating operations coincide with the functions on binary words that are comput