Skip to Main content Skip to Navigation
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 metadatas

Cited literature [4 references]  Display  Hide  Download

https://hal.inria.fr/hal-01653659
Contributor : Emmanuel Hainry <>
Submitted on : Friday, December 1, 2017 - 5:01:08 PM
Last modification on : Thursday, March 5, 2020 - 11:02:09 AM

File

HP.pdf
Files produced by the author(s)

Identifiers

  • 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⟩

Share

Metrics

Record views

292

Files downloads

90