Theory of higher order interpretations and application to Basic Feasible Functions
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 i...
Main Authors: | Emmanuel Hainry, Romain Péchoux |
---|---|
Format: | Article |
Language: | English |
Published: |
Logical Methods in Computer Science e.V.
2020-12-01
|
Series: | Logical Methods in Computer Science |
Subjects: | |
Online Access: | https://lmcs.episciences.org/4237/pdf |
Similar Items
-
A tier-based typed programming language characterizing Feasible Functionals
by: Emmanuel Hainry, et al.
Published: (2022-02-01) -
Higher Order Automatic Differentiation of Higher Order Functions
by: Mathieu Huot, et al.
Published: (2022-03-01) -
Modular coinduction up-to for higher-order languages via first-order transition systems
by: Jean-Marie Madiot, et al.
Published: (2021-09-01) -
On the Termination Problem for Probabilistic Higher-Order Recursive Programs
by: Naoki Kobayashi, et al.
Published: (2020-10-01) -
Efficiently Simulating Higher-Order Arithmetic by a First-Order Theory Modulo
by: Guillaume Burel
Published: (2011-03-01)