Time-complexity semantics for feasible affine recursions

Norman Danner, James S. Royer

Research output: Chapter in Book/Entry/PoemConference contribution

1 Scopus citations


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.

Original languageEnglish (US)
Title of host publicationComputation and Logic in the Real World - Third Conference on Computability in Europe, CiE 2007, Proceedings
Number of pages13
StatePublished - 2007
Event3rd Conference on Computability in Europe, CiE 2007 - Siena, Italy
Duration: Jun 18 2007Jun 23 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4497 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other3rd Conference on Computability in Europe, CiE 2007

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Time-complexity semantics for feasible affine recursions'. Together they form a unique fingerprint.

Cite this