Interpretation methods and their restrictions to polynomials have been deeply used to control the termination and complexity of first-order term rewrite systems. This paper extends interpretation methods to a pure higher order functional language. We develop a theory of higher order functions that is well-suited for the complexity analysis of this programming language. The interpretation domain is a complete lattice and, consequently, we express program interpretation in terms of a least fixpoint. As an application, by bounding interpretations by higher order polynomials, we characterize Basic Feasible Functions at any order.

@article{abs-1801-08350,
  title = {Theory of higher order interpretations and application to Basic Feasible Functions},
  author = {Emmanuel Hainry and Romain Péchoux},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 16, Issue 4},
  year = {2020},
  doi = {10.23638/lmcs-16(4:14)2020}
}