Higher order interpretation for higher order complexity

descriptionPublicationkeyboard_double_arrow_right Article , Conference object 23 Jan 2018Publisher:EasyChairJournal:EPiC Series in Computing, volume 46, pages 269-251 (issn: 2398-7340,

Copyright policy )

Authors: Hainry, Emmanuel; Péchoux, Romain;

doi: 10.29007/1tkw

Higher order interpretation for higher order complexity

- Summary
- Subjects
- Metrics

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 a` 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.

Related Organizations

View all View all

Keywords

higher-order programs, Basic Feasible Functionals, [INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC], higher-order interpretation

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	0
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average