Lics

IEEE Symposium on Logic in Computer Science

LICS Home - LICS Awards - LICS Newsletters - LICS Archive - LICS Organization - Logic-Related Conferences - Links

Fourteenth Annual IEEE Symposium on

Logic in Computer Science (LICS 1999)

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}
  }
   

Last modified: 2017-04-0512:37
Andrzej Murawski