Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/43152
Title: Calculating polynomial runtime properties
Authors: Anderson, H. 
Khoo, S.-C. 
Andrei, S. 
Luca, B.
Issue Date: 2005
Source: Anderson, H.,Khoo, S.-C.,Andrei, S.,Luca, B. (2005). Calculating polynomial runtime properties. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 3780 LNCS : 230-246. ScholarBank@NUS Repository.
Abstract: Affine size-change analysis has been used for termination analysis of eager functional programming languages. The same style of analysis is also capable of compactly recording and calculating other properties of programs, including their runtime, maximum stack depth, and (relative) path time costs. In this paper we show how precise (not just big-script O sign) polynomial bounds on such costs may be calculated on programs, by a characterization as a problem in quantifier elimination. The technique is decidable, and complete for a class of size-change terminating programs with limited-degree polynomial costs. An extension to the technique allows the calculation of some classes of exponential-cost programs. We demonstrate the new technique by recording the calculation in numbers-of-function (or procedure) calls for a simple functional definition language, but it can also be applied to imperative languages. The technique is automated within the reduce computer algebra system. © Springer-Verlag Berlin Heidelberg 2005.
Source Title: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
URI: http://scholarbank.nus.edu.sg/handle/10635/43152
ISBN: 3540297359
ISSN: 03029743
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

64
checked on Dec 9, 2017

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.