LIPIcs.FSTTCS.2008.1763.pdf
- Filesize: 429 kB
- 12 pages
Document
Analyzing the Implicit Computational Complexity of object-oriented programs
Authors
-
Part of:
Volume:
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2008)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS) - License:
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
- Publication Date: 2008-12-05
Cite AsGet BibTex
Jean-Yves Marion and Romain Pechoux. Analyzing the Implicit Computational Complexity of object-oriented programs. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 2, pp. 316-327, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)
https://doi.org/10.4230/LIPIcs.FSTTCS.2008.1763
https://doi.org/10.4230/LIPIcs.FSTTCS.2008.1763
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.
Keywords
- Implicit computational complexity
- object-oriented programs
- sup-interpretation
- resource upper bounds
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads