Please use this identifier to cite or link to this item:
Title: Program transformation by solving recurrences
Authors: Luca, B.
Andrei, S. 
Anderson, H. 
Khoo, S.-C. 
Keywords: Efficient time complexity
Program transformation
Recurrences with one or multiple parameters
Issue Date: 2006
Citation: Luca, B.,Andrei, S.,Anderson, H.,Khoo, S.-C. (2006). Program transformation by solving recurrences. Proceedings of the ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation : 121-129. ScholarBank@NUS Repository.
Abstract: Recursive programs may require large numbers of procedure calls and stack operations, and many such recursive programs exhibit exponential time complexity, due to the time spent re-calculating already computed sub-problems. As a result, methods which transform a given recursive program to an iterative one have been intensively studied. We propose here a new framework for transforming programs by removing recursion. The framework includes a unified method of deriving low time-complexity programs by solving recurrences extracted from the program sources. Our prototype system, APTSR1, is an initial implementation of the framework, automatically finding simpler "closed form" versions of a class of recursive programs. Though in general the solution of recurrences is easier if the functions have only a single recursion parameter, we show a practical technique for solving those with multiple recursion parameters. Copyright © 2006 ACM.
Source Title: Proceedings of the ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation
ISBN: 1595931961
DOI: 10.1145/1111542.1111563
Appears in Collections:Staff Publications

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

Google ScholarTM



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