Higher order interpretations for higher order complexity

Emmanuel Hainry 1 Romain Péchoux 1
1 CARTE - Theoretical adverse computations, and safety
Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Abstract : We design an interpretation-based theory of higher order functions that is well-suited for the complexity analysis of a standard higher order functional language à la ML. We manage to express the interpretation of a given program in terms of a least fixpoint and we show that when restricted to functions bounded by higher order polynomials, they characterize exactly classes of tractable functions known as Basic Feasible Functions at any order.
Type de document :
Communication dans un congrès
8th Workshop on Developments in Implicit Computational complExity and 5th Workshop on Foundational and Practical Aspects of Resource Analysis, Apr 2017, Uppsala, Sweden
Liste complète des métadonnées

Littérature citée [4 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01653659
Contributeur : Emmanuel Hainry <>
Soumis le : vendredi 1 décembre 2017 - 17:01:08
Dernière modification le : jeudi 11 janvier 2018 - 06:21:25

Fichier

HP.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01653659, version 1

Collections

Citation

Emmanuel Hainry, Romain Péchoux. Higher order interpretations for higher order complexity. 8th Workshop on Developments in Implicit Computational complExity and 5th Workshop on Foundational and Practical Aspects of Resource Analysis, Apr 2017, Uppsala, Sweden. 〈hal-01653659〉

Partager

Métriques

Consultations de la notice

85

Téléchargements de fichiers

8