Links und Funktionen
Sprachumschaltung

Navigationspfad
You are here: Home / Publikationen / Linear Types and Non-Size-Increasing Polynomial Time Computation


Inhaltsbereich

Martin Hofmann (1999)

Linear Types and Non-Size-Increasing Polynomial Time Computation

In: 14th Annual IEEE Symposium on Logic in Computer Science, Trento, Italy, July 2-5, 1999, pp. 464-473, IEEE Computer Society (ISBN: 0-7695-0158-3).

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.

Document Actions


Funktionsleiste