Time-complexity semantics for feasible affine recursions

Norman Danner, James S. Royer

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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
Pages205-217
Number of pages13
DOIs
StatePublished - Dec 1 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

Other

Other3rd Conference on Computability in Europe, CiE 2007
CountryItaly
CitySiena
Period6/18/076/23/07

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

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

  • Cite this

    Danner, N., & Royer, J. S. (2007). Time-complexity semantics for feasible affine recursions. In Computation and Logic in the Real World - Third Conference on Computability in Europe, CiE 2007, Proceedings (pp. 205-217). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4497 LNCS). https://doi.org/10.1007/978-3-540-73001-9_22