Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [19 references]  Display  Hide  Download

https://hal.inria.fr/inria-00332550
Contributor : Romain Péchoux Connect in order to contact the contributor
Submitted on : Tuesday, October 21, 2008 - 11:01:05 AM
Last modification on : Saturday, June 25, 2022 - 7:45:41 PM
Long-term archiving on: : Monday, June 7, 2010 - 7:05:50 PM

File

paper28.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : inria-00332550, version 1

Collections

Citation

Jean-yves Marion, Romain Péchoux. Analyzing the Implicit Computational Complexity of object-oriented programs. Annual Conference on Foundations of Software Technology and Theoretical Computer Science - FSTTCS 2008, IARCS, the Indian Association for Research in Computing Science, Dec 2008, Bangalore, India. ⟨inria-00332550⟩

Share

Metrics

Record views

118

Files downloads

92