On quasi-interpretations, blind abstractions and implicit complexity

DOI10.1017/S0960129511000685zbMath1288.68078OpenAlexW2625940422MaRDI QIDQ2909730

Patrick Baillot, Ugo Dal Lago, Jean-Yves Moyen

Publication date: 6 September 2012

Published in: Mathematical Structures in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1017/s0960129511000685

Mathematics Subject Classification ID

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

Related Items (1)

On sharing, memoization, and polynomial time

Cites Work

• Quasi-interpretations. A way to control resources
• Orderings for term-rewriting systems
• A new recursion-theoretic characterization of the polytime functions
• Light linear logic
• Analysing the implicit complexity of programs.
• Linear types and non-size-increasing polynomial time computation.
• LOGSPACE and PTIME characterized by programming languages
• Algorithms with polynomial interpretation termination proof
• Sup-interpretations, a semantic method for static analysis of program resources
• Resource Analysis by Sup-interpretation
• Quasi-interpretation Synthesis by Decomposition
• Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
• Complexity Analysis by Rewriting

This page was built for publication: On quasi-interpretations, blind abstractions and implicit complexity