Published 2015
| Version v1
Conference paper
On Sharing, Memoization, and Polynomial Time
- Creators
- Avanzini, Martin
- Dal Lago, Ugo
- Others:
- Leopold Franzens Universität Innsbruck - University of Innsbruck
- Foundations of Component-based Ubiquitous Systems (FOCUS) ; Inria Sophia Antipolis - Méditerranée (CRISAM) ; Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Dipartimento di Informatica - Scienza e Ingegneria [Bologna] (DISI) ; Alma Mater Studiorum Università di Bologna [Bologna] (UNIBO)-Alma Mater Studiorum Università di Bologna [Bologna] (UNIBO)
- Alma Mater Studiorum Università di Bologna [Bologna] (UNIBO)
Description
We study how the adoption of an evaluation mechanism with sharing and memoization impacts the class of functions which can be computed in polynomial time. We first show how a natural cost model in which lookup for an already computed result has no cost is indeed invariant. As a corollary, we then prove that the most general notion of ramified recurrence is sound for polynomial time, this way settling an open problem in implicit computational complexity.
Abstract
International audience
Additional details
- URL
- https://hal.inria.fr/hal-01231816
- URN
- urn:oai:HAL:hal-01231816v1
- Origin repository
- UNICA