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
Thomas Eiter; David Sands. LPAR 2017 - International Conferences on Logic for Programming, Artificial Intelligence and Reasoning, May 2017, Maun, Botswana. 46, pp.269-285, 2017, LPAR-21. 21st International Conference on Logic for Programming, Artificial Intelligence and Reasoning. 〈http://easychair.org/smart-program/LPAR-21/LPAR-index.html〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01529170
Contributeur : Romain Péchoux <>
Soumis le : mardi 30 mai 2017 - 23:24:09
Dernière modification le : vendredi 9 février 2018 - 12:56:01
Document(s) archivé(s) le : mercredi 6 septembre 2017 - 14:35:47

Fichier

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

Identifiants

  • HAL Id : hal-01529170, version 2

Citation

Emmanuel Hainry, Romain Péchoux. Higher-order interpretations for higher-order complexity. Thomas Eiter; David Sands. LPAR 2017 - International Conferences on Logic for Programming, Artificial Intelligence and Reasoning, May 2017, Maun, Botswana. 46, pp.269-285, 2017, LPAR-21. 21st International Conference on Logic for Programming, Artificial Intelligence and Reasoning. 〈http://easychair.org/smart-program/LPAR-21/LPAR-index.html〉. 〈hal-01529170v2〉

Partager

Métriques

Consultations de la notice

145

Téléchargements de fichiers

40