On quasi-interpretations, blind abstractions and implicit complexity

DOI10.1017/S0960129511000685zbMATH Open1288.68078OpenAlexW2625940422MaRDI QIDQ2909730FDOQ2909730

Patrick Baillot, Ugo Dal Lago, Jean-Yves Moyen

Publication date: 6 September 2012

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

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

Recommendations

• Higher-order interpretations and program complexity
• Higher-order interpretations and program complexity
• Quasi-interpretations. A way to control resources
• scientific article; zbMATH DE number 2061700
• scientific article; zbMATH DE number 2182486

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (5)

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Term Rewriting and Applications
• On sharing, memoization, and polynomial time

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

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