Logic in Computer Science (LICS 2000)

Paper: A Syntactical Analysis of Non-Size-Increasing Polynomial Time Computation (at LICS 2000)

Authors: Klaus Aehlig Helmut Schwichtenberg

Abstract

A purely syntactical proof is given that all functions definable in a certain affine linear typed lambda-calculus with iteration in all types are polynomial time computable. The proof also gives explicit polynomial bounds that can easily be calculated.

BibTeX

  @InProceedings{AehligSchwichtenber-ASyntacticalAnalysi,
    author = 	 {Klaus Aehlig and Helmut Schwichtenberg},
    title = 	 {A Syntactical Analysis of Non-Size-Increasing Polynomial Time Computation},
    booktitle =  {Proceedings of the Fifteenth Annual IEEE Symp. on Logic in Computer Science, {LICS} 2000},
    year =	 2000,
    editor =	 {Martin Abadi},
    month =	 {June}, 
    pages =      {84--91},
    location =   {Santa Barbara, CA, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }