Higher-order interpretations and program complexity

DOI10.1016/J.IC.2015.12.008zbMATH Open1339.68037OpenAlexW1508002867MaRDI QIDQ276254FDOQ276254

Authors: Patrick Baillot, Ugo Dal Lago 

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

Recommendations

• Higher-order interpretations and program complexity
• Higher order interpretation for higher order complexity
• On quasi-interpretations, blind abstractions and implicit complexity
• Theory of higher order interpretations and application to basic feasible functions
• scientific article; zbMATH DE number 1696756

zbMATH Keywords

implicit computational complexitylambda-calculusterm rewriting systemstype systems

Mathematics Subject Classification ID

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

Cites Work

• 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
• Title not available (Why is that?)
• Title not available (Why is that?)
• A combination framework for complexity
• Analysing the complexity of functional programs: higher-order meets first-order
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Higher-order interpretations and program complexity
• Title not available (Why is that?)
• Title not available (Why is that?)
• Linear dependent types and relative completeness
• Polynomial interpretations for higher-order rewriting
• Realizability models and implicit complexity
• Quasi-interpretations. A way to control resources
• Derivational complexity is an invariant cost model
• The derivational complexity induced by the dependency pair method
• Orderings for term-rewriting systems

Cited In (18)

• Combining linear logic and size types for implicit complexity
• Interpretation of stream programs: characterizing type 2 polynomial time complexity
• Title not available (Why is that?)
• Higher-order interpretations and program complexity
• Implicit computation complexity in higher-order programming languages
• A tier-based typed programming language characterizing feasible functionals
• Title not available (Why is that?)
• Higher order interpretation for higher order complexity
• Static complexity analysis of higher order programs
• Analyzing the implicit computational complexity of object-oriented programs
• Complete and tractable machine-independent characterizations of second-order polytime
• Title not available (Why is that?)
• On quasi-interpretations, blind abstractions and implicit complexity
• Analysing the complexity of functional programs: higher-order meets first-order
• Theory of higher order interpretations and application to basic feasible functions
• Complexity invariance of real interpretations
• Quasi-interpretation Synthesis by Decomposition
• Analyzing Innermost Runtime Complexity Through Tuple Interpretations

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q276254)