Higher order interpretations for higher order complexity

Emmanuel Hainry (1) , Romain Péchoux (1)

1 CARTE - Theoretical adverse computations, and safety

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.

Domaines: Complexité [cs.CC]

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⟩