A feasible algorithm for typing in Elementary Affine Logic

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

We give a new type inference algorithm for typing lambda-terms in Elementary Affine Logic (EAL), which is motivated by applications to complexity and optimal reduction. Following previous references on this topic, the variant of EAL type system we consider (denoted EAL*) is a variant without sharing and without polymorphism. Our algorithm improves over the ones already known in that it offers a better complexity bound: if a simple type derivation for the term t is given our algorithm performs EAL* type inference in polynomial time.
20 pages

Keywords

Logic in Computer Science

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/32484

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/cs/0412028
 http://arxiv.org/abs/cs/0412028

Collections

arXiv