On quasi-interpretations, blind abstractions and implicit complexity

DOI10.1017/S0960129511000685MaRDI QIDQ2909730zbMATH OpenOpenAlexFDO

Authors 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

Mathematics Subject Classification ID

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

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

Cites work

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

Cited in

(8)

• On sharing, memoization, and polynomial time
• Higher-order interpretations and program complexity
• scientific article; zbMATH DE number 1696756 (Why is no real title available?)
• scientific article; zbMATH DE number 2061700 (Why is no real title available?)
• Higher-order interpretations and program complexity
• scientific article; zbMATH DE number 2182486 (Why is no real title available?)
• Term Rewriting and Applications
• A characterization of basic feasible functionals through higher-order rewriting and tuple interpretations

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)