Higher-order interpretations and program complexity

DOI10.1016/j.ic.2015.12.008zbMath1339.68037OpenAlexW1508002867MaRDI QIDQ276254

Ugo Dal Lago, Patrick Baillot

Publication date: 3 May 2016

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2015.12.008

zbMATH Keywords

term rewriting systemstype systemslambda-calculusimplicit computational complexity

Mathematics Subject Classification ID

Functional programming and lambda calculus (68N18) Grammars and rewriting systems (68Q42) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (6)

Analyzing Innermost Runtime Complexity Through Tuple Interpretations ⋮ Complete and tractable machine-independent characterizations of second-order polytime ⋮ Combining linear logic and size types for implicit complexity ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Realizability models and implicit complexity
• Quasi-interpretations. A way to control resources
• Orderings for term-rewriting systems
• Light types for polynomial time computation in lambda calculus
• A new recursion-theoretic characterization of the polytime functions
• Combinatory reduction systems: Introduction and survey
• Linear types and non-size-increasing polynomial time computation.
• Higher type recursion, ramification and polynomial time
• Safe recursion with higher types and BCK-algebra
• Algorithms with polynomial interpretation termination proof
• A Combination Framework for Complexity
• Analysing the complexity of functional programs: higher-order meets first-order
• Quasi-interpretation Synthesis by Decomposition
• A PolyTime Functional Language from Light Linear Logic
• A Soft Type Assignment System for λ-Calculus
• On Constructor Rewrite Systems and the Lambda-Calculus
• Higher-Order Interpretations and Program Complexity
• Linear Dependent Types and Relative Completeness
• Polynomial Interpretations for Higher-Order Rewriting
• Derivational Complexity Is an Invariant Cost Model
• The Derivational Complexity Induced by the Dependency Pair Method

This page was built for publication: Higher-order interpretations and program complexity