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
Contributor : Romain Péchoux <>
Submitted on : Tuesday, October 21, 2008 - 11:01:05 AM
Last modification on : Tuesday, May 5, 2020 - 5:02:15 PM
Long-term archiving on: : Monday, June 7, 2010 - 7:05:50 PM


Publisher files allowed on an open archive


  • HAL Id : inria-00332550, version 1



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⟩



Record views


Files downloads