A tool for calculating exponential run-time properties

Please use this identifier to cite or link to this item: https://doi.org/10.1109/SYNASC.2007.15

Title:	A tool for calculating exponential run-time properties
Authors:	Anderson, H. Khoo, S.-C. Liu, Y.
Issue Date:	2007
Citation:	Anderson, H., Khoo, S.-C., Liu, Y. (2007). A tool for calculating exponential run-time properties. Proceedings - 9th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2007 : 25-32. ScholarBank@NUS Repository. https://doi.org/10.1109/SYNASC.2007.15
Abstract:	Affine size-change analysis has been used for calculating precise polynomial bounds on the run times, and stack depths of affine size-change terminating programs. Such polynomial costs may be discovered by a characterization as a problem in quantifier elimination. In this paper we extend this work to cover a class of exponential cost programs. The tool described allows the calculation of run-time and stack-depth costs for some classes of exponential-cost programs, again by using quantifier elimination. The technique is automated, and uses the reduce computer algebra system. © 2008 IEEE.
Source Title:	Proceedings - 9th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2007
URI:	http://scholarbank.nus.edu.sg/handle/10635/41449
ISBN:	0769530788
DOI:	10.1109/SYNASC.2007.15
Appears in Collections:	Staff Publications

There are no files associated with this item.

Check