On sharing, memoization, and polynomial time

DOI10.1016/J.IC.2018.05.003zbMATH Open1395.68134OpenAlexW2808308120MaRDI QIDQ1640979FDOQ1640979

Authors: Martin Avanzini, Ugo Dal Lago 

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

Recommendations

• On sharing, memoization, and polynomial time
• Efficient memo-table management strategies
• Higher type recursion, ramification and polynomial time
• Weak optimality, and the meaning of sharing
• Polynomial Time in the Parametric Lambda Calculus.

zbMATH Keywords

implicit computational complexitypolynomial timedata-tiering

Mathematics Subject Classification ID

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

Cites Work

• A new recursion-theoretic characterization of the polytime functions
• On constructor rewrite systems and the lambda calculus
• Automated Complexity Analysis Based on the Dependency Pair Method
• Title not available (Why is that?)
• Closing the gap between runtime complexity and polytime computability
• Quasi-interpretations. A way to control resources
• Derivational complexity is an invariant cost model
• Title not available (Why is that?)
• Analysing the implicit complexity of programs.
• Term rewriting theory for the primitive recursive functions
• Beta reduction is invariant, indeed
• Title not available (Why is that?)
• On sharing, memoization, and polynomial time
• On quasi-interpretations, blind abstractions and implicit complexity
• A new function algebra of EXPTIME functions by safe nested recursion
• Recursion Schemata for NC k
• Title not available (Why is that?)
• Essentials of term graph rewriting
• On the invariance of the unitary cost model for head reduction

Cited In (4)

• Implicit computation complexity in higher-order programming languages
• The ramifications of sharing in data structures
• Partial memoization for obtaining linear time behavior of a 2DPDA
• On sharing, memoization, and polynomial time

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

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