文章基本信息

标题：Analyzing the Implicit Computational Complexity of object-oriented programs
本地全文：下载
作者：Jean-Yves Marion ; Romain Pechoux
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2008
卷号：2
页码：316-327
DOI：10.4230/LIPIcs.FSTTCS.2008.1763
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Implicit computational complexity; object-oriented programs; sup-interpretation; resource upper bounds