Skip to Main content Skip to Navigation
New interface
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [4 references]  Display  Hide  Download
Contributor : Emmanuel Hainry Connect in order to contact the contributor
Submitted on : Friday, December 1, 2017 - 5:01:08 PM
Last modification on : Wednesday, February 2, 2022 - 3:52:50 PM


Files produced by the author(s)


  • HAL Id : hal-01653659, version 1



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⟩



Record views


Files downloads