Please use this identifier to cite or link to this item:
|Title:||Calculating polynomial runtime properties||Authors:||Anderson, H.
|Issue Date:||2005||Citation:||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.
checked on Dec 30, 2019
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.