Analyzing the Implicit Computational Complexity of object-oriented programs

Jean-Yves Marion 1 Romain Péchoux 1
1 CARTE - Theoretical adverse computations, and safety
Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Abstract : A sup-interpretation is a tool which provides upper bounds on the size of the values computed by the function symbols of a program. Sup-interpretations have shown their interest to deal with the complexity of first order functional programs. This paper is an attempt to adapt the framework of sup-interpretations to a fragment of object-oriented programs, including loop and while constructs and methods with side effects. We give a criterion, called brotherly criterion, which uses the notion of sup-interpretation to ensure that each brotherly program computes objects whose size is polynomially bounded by the inputs sizes. Moreover we give some heuristics in order to compute the sup-interpretation of a given method.
Type de document :
Communication dans un congrès
R. Hariharan, M. Mukund, V. Vinay. Annual Conference on Foundations of Software Technology and Theoretical Computer Science - FSTTCS 2008, Dec 2008, Bangalore, India. Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 License: Creative Commons-NC-ND, 2008
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00332550
Contributeur : Romain Péchoux <>
Soumis le : mardi 21 octobre 2008 - 11:01:05
Dernière modification le : jeudi 11 janvier 2018 - 06:21:25
Document(s) archivé(s) le : lundi 7 juin 2010 - 19:05:50

Fichier

paper28.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : inria-00332550, version 1

Collections

Citation

Jean-Yves Marion, Romain Péchoux. Analyzing the Implicit Computational Complexity of object-oriented programs. R. Hariharan, M. Mukund, V. Vinay. Annual Conference on Foundations of Software Technology and Theoretical Computer Science - FSTTCS 2008, Dec 2008, Bangalore, India. Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 License: Creative Commons-NC-ND, 2008. 〈inria-00332550〉

Partager

Métriques

Consultations de la notice

234

Téléchargements de fichiers

133