On characterizations of the basic feasible functionals, Part I

Robert J. Irwin, James S. Royer, Bruce M. Kapron

Research output: Contribution to journalArticle

27 Scopus citations

Abstract

We introduce a typed programming formalism, type-2 inflationary tiered loop programs or ITLP2, that characterizes the type-2 basic feasible functionals. 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 of the type-2 basic feasible functionals.

Original languageEnglish (US)
Pages (from-to)117-153
Number of pages37
JournalJournal of Functional Programming
Volume11
Issue number1
DOIs
StatePublished - Jan 1 2001

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'On characterizations of the basic feasible functionals, Part I'. Together they form a unique fingerprint.

  • Cite this