On characterizations of the basic feasible functionals, Part I

Authors
Irwin, RJ Royer, JS Kapron, BM
Citation
Rj. Irwin et al., On characterizations of the basic feasible functionals, Part I, J FUNCT PRO, 11, 2001, pp. 117-153
Citations number
49
Categorie Soggetti
Computer Science & Engineering
Journal title
JOURNAL OF FUNCTIONAL PROGRAMMING
ISSN journal
09567968 → ACNP
Volume
11
Year of publication
2001
Part
1
Pages
117 - 153
Database
ISI
SICI code
0956-7968(200101)11:<117:OCOTBF>2.0.ZU;2-H
Abstract
We introduce a typed programming formalism, type-2 inflationary tiered loop programs or ITLP2, that characterizes the type-2 basic feasible functional s. ITLP2 is based on Bellantoni and Cook's (1992) and Leivant's (1995) type -theoretic characterization of polynomial-time, and turns out to be closely related to Kapron and Cook's (1991; 1996) machine-based characterization o f the type-2 basic feasible functionals.