On characterizations of the basic feasible functionals, Part I

作     者：Irwin, RJ Royer, JS Kapron, BM 

作者机构：Syracuse Univ Dept Elect Engn & Comp Sci Syracuse NY 13244 USA Univ Victoria Dept Comp Sci Victoria BC V8W 3P6 Canada 

出 版 物：《JOURNAL OF FUNCTIONAL PROGRAMMING》 (功能程序设计杂志)

年 卷 期：2001年第11卷第1期

页      面：117-153页

核心收录：

学科分类：08[工学] 0835[工学-软件工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：program control structures Basic language Restaurants and catering FUNCTIONALS 

摘      要：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.