๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Safe recursion with higher types and BCK-algebra

โœ Scribed by Martin Hofmann

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

No coin nor oath required. For personal study only.

โœฆ Synopsis

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 develop a semantics of SLR using BCK-algebras consisting of certain polynomial-time algorithms. It will follow from this semantics that safe recursion with arbitrary result type built up from N and ( as well as recursion over trees and other data structures remains within polynomial time. In its original formulation SLR supported only natural numbers and recursion on notation with รฟrst-order functional result type.

๐Ÿ“œ SIMILAR VOLUMES

Higher type recursion, ramification and
Higher type recursion, ramification and polynomial time
โœ Stephen J. Bellantoni; Karl-Heinz Niggl; Helmut Schwichtenberg ๐Ÿ“‚ Article ๐Ÿ“… 2000 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 126 KB

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.