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 metadata

Cited literature [17 references]  Display  Hide  Download

https://hal.inria.fr/hal-01529170
Contributor : Romain Péchoux <>
Submitted on : Tuesday, May 30, 2017 - 11:24:09 PM
Last modification on : Tuesday, December 8, 2020 - 9:51:03 AM
Long-term archiving on: : Wednesday, September 6, 2017 - 2:35:47 PM

File

lpar.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01529170, version 2

Collections

Citation

Emmanuel Hainry, Romain Péchoux. Higher-order interpretations for higher-order complexity. LPAR 2017 - International Conferences on Logic for Programming, Artificial Intelligence and Reasoning, Geoff Sutcliffe, May 2017, Maun, Botswana. pp.269-285. ⟨hal-01529170v2⟩

Share

Metrics

Record views

233

Files downloads

120