Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2008.1763
URN: urn:nbn:de:0030-drops-17638
URL: https://drops.dagstuhl.de/opus/volltexte/2008/1763/
Marion, Jean-Yves ; Pechoux, Romain
Analyzing the Implicit Computational Complexity of object-oriented programs
| pdf-format: |
|
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.
BibTeX - Entry
@InProceedings{marion_et_al:LIPIcs:2008:1763,
author = {Jean-Yves Marion and Romain Pechoux},
title = {{Analyzing the Implicit Computational Complexity of object-oriented programs}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
pages = {316--327},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-08-8},
ISSN = {1868-8969},
year = {2008},
volume = {2},
editor = {Ramesh Hariharan and Madhavan Mukund and V Vinay},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2008/1763},
URN = {urn:nbn:de:0030-drops-17638},
doi = {10.4230/LIPIcs.FSTTCS.2008.1763},
annote = {Keywords: Implicit computational complexity, object-oriented programs, sup-interpretation, resource upper bounds}
}
| Keywords: | Implicit computational complexity, object-oriented programs, sup-interpretation, resource upper bounds | |
| Seminar: | IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science | |
| Issue date: | 2008 | |
| Date of publication: | 05.12.2008 |
