On sharing, memoization, and polynomial time

DOI10.1016/j.ic.2018.05.003zbMath1395.68134OpenAlexW2808308120MaRDI QIDQ1640979

Ugo Dal Lago, Martin Avanzini

Publication date: 14 June 2018

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

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

zbMATH Keywords

polynomial timeimplicit computational complexitydata-tiering

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (1)

Implicit computation complexity in higher-order programming languages

Cites Work

• Quasi-interpretations. A way to control resources
• Term rewriting theory for the primitive recursive functions
• A new recursion-theoretic characterization of the polytime functions
• Analysing the implicit complexity of programs.
• On Constructor Rewrite Systems and the Lambda Calculus
• On quasi-interpretations, blind abstractions and implicit complexity
• A new function algebra of EXPTIME functions by safe nested recursion
• Recursion Schemata for NC k
• Automated Complexity Analysis Based on the Dependency Pair Method
• Beta reduction is invariant, indeed
• Essentials of Term Graph Rewriting
• Closing the Gap Between Runtime Complexity and Polytime Computability.
• Derivational Complexity Is an Invariant Cost Model
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On sharing, memoization, and polynomial time