𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Elementary explicit types and polynomial time operations

✍ Scribed by Daria Spescha; Thomas Strahm

Publisher
John Wiley and Sons
Year
2009
Tongue
English
Weight
153 KB
Volume
55
Category
Article
ISSN
0044-3050

No coin nor oath required. For personal study only.

✦ Synopsis

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 computable in polynomial time. The systems considered are natural extensions of the first‐order applicative theories introduced in Strahm [19, 20] (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)

📜 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.