TY - GEN
T1 - Time-complexity semantics for feasible affine recursions
AU - Danner, Norman
AU - Royer, James S.
PY - 2007
Y1 - 2007
N2 - The authors' ATR programming formalism is a version of call-by-value PCF under a complexity-theoretically motivated type system. ATR programs run in type-2 polynomial-time and all standard type2 basic feasible functionals are ATR-definable (ATR types are confined to levels 0, 1, and 2). A limitation of the original version of ATR is that the only directly expressible recursions are tail-recursions. Here we extend ATR so that a broad range of affine recursions are directly expressible. In particular, the revised ATR can fairly naturally express the classic insertion- and selection-sort algorithms, thus overcoming a sticking point of most prior implicit-complexity-based formalisms. The paper's main work is in extending and simplifying the original time-complexity semantics for ATR to develop a set of tools for extracting and solving the higher-type recurrences arising from feasible affine recursions.
AB - The authors' ATR programming formalism is a version of call-by-value PCF under a complexity-theoretically motivated type system. ATR programs run in type-2 polynomial-time and all standard type2 basic feasible functionals are ATR-definable (ATR types are confined to levels 0, 1, and 2). A limitation of the original version of ATR is that the only directly expressible recursions are tail-recursions. Here we extend ATR so that a broad range of affine recursions are directly expressible. In particular, the revised ATR can fairly naturally express the classic insertion- and selection-sort algorithms, thus overcoming a sticking point of most prior implicit-complexity-based formalisms. The paper's main work is in extending and simplifying the original time-complexity semantics for ATR to develop a set of tools for extracting and solving the higher-type recurrences arising from feasible affine recursions.
UR - http://www.scopus.com/inward/record.url?scp=38149111071&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=38149111071&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-73001-9_22
DO - 10.1007/978-3-540-73001-9_22
M3 - Conference contribution
AN - SCOPUS:38149111071
SN - 9783540730002
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 205
EP - 217
BT - Computation and Logic in the Real World - Third Conference on Computability in Europe, CiE 2007, Proceedings
T2 - 3rd Conference on Computability in Europe, CiE 2007
Y2 - 18 June 2007 through 23 June 2007
ER -