Paper: Linear Types and Non Size-Increasing Polynomial Time Computation (at LICS 1999)

Authors: Martin Hofmann

Abstract

We propose a linear type system with recursion operators for inductive datatypes which ensures that all definable functions are polynomial time computable. The system improves upon previous such systems in that recursive definitions can be arbitrarily nested, in particular no predicativity or modality restrictions are made.

BibTeX

  @InProceedings{Hofmann-LinearTypesandNonSi,
    author = 	 {Martin Hofmann},
    title = 	 {Linear Types and Non Size-Increasing Polynomial Time Computation},
    booktitle =  {Proceedings of the Fourteenth Annual IEEE Symposium on Logic in Computer Science (LICS 1999)},
    year =	 {1999},
    month =	 {July}, 
    pages =      {464--473},
    location =   {Trento, Italy}, 
    publisher =	 {IEEE Computer Society Press}
  }