On Sharing, Memoization, and Polynomial Time

Martin Avanzini 1, 2, 3 Ugo Dal Lago 2, 3
2 FOCUS - Foundations of Component-based Ubiquitous Systems
CRISAM - Inria Sophia Antipolis - Méditerranée , DISI - Dipartimento di Informatica - Scienza e Ingegneria [Bologna]
Abstract : 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.
Type de document :
Communication dans un congrès
Proceedings of STACS 2015, 2015, Munich, Germany. LIPIcs, 62, 2015, 〈10.4230/LIPIcs.STACS.2015.62〉
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01231816
Contributeur : Ugo Dal Lago <>
Soumis le : jeudi 3 décembre 2015 - 10:14:42
Dernière modification le : jeudi 11 janvier 2018 - 16:48:55
Document(s) archivé(s) le : vendredi 28 avril 2017 - 18:46:28

Fichier

4.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Martin Avanzini, Ugo Dal Lago. On Sharing, Memoization, and Polynomial Time. Proceedings of STACS 2015, 2015, Munich, Germany. LIPIcs, 62, 2015, 〈10.4230/LIPIcs.STACS.2015.62〉. 〈hal-01231816〉

Partager

Métriques

Consultations de la notice

209

Téléchargements de fichiers

41