On the elementary affine λ-calculus with and without type fixpoints - Université Sorbonne Paris Nord Accéder directement au contenu
Article Dans Une Revue Electronic Proceedings in Theoretical Computer Science Année : 2019

On the elementary affine λ-calculus with and without type fixpoints

Résumé

The elementary affine λ-calculus was introduced as a polyvalent setting for implicit computational complexity, allowing for characterizations of polynomial time and hyperexponential time predicates. But these results rely on type fixpoints (a.k.a. recursive types), and it was unknown whether this feature of the type system was really necessary. We give a positive answer by showing that without type fixpoints, we get a characterization of regular languages instead of polynomial time. The proof uses the semantic evaluation method. We also propose an aesthetic improvement on the characterization of the function classes FP and k-FEXPTIME in the presence of recursive types.
Fichier principal
Vignette du fichier
post-proceedings-dice-fopara.pdf (322.42 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02153709 , version 1 (12-06-2019)

Identifiants

Citer

Lê Thành Dũng Nguyễn. On the elementary affine λ-calculus with and without type fixpoints. Electronic Proceedings in Theoretical Computer Science, 2019, Proceedings Third Joint Workshop on Developments in Implicit Computational complExity and Foundational & Practical Aspects of Resource Analysis (DICE-FOPARA 2019), 298, pp.15-29. ⟨10.4204/EPTCS.298.2⟩. ⟨hal-02153709⟩
47 Consultations
49 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More