On characterizations of the basic feasible functionals, Part I

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

Research output: Contribution to journalArticle

26 Scopus citations


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
Issue number1
StatePublished - Jan 2001


ASJC Scopus subject areas

  • Computer Graphics and Computer-Aided Design
  • Software

Cite this