Please use this identifier to cite or link to this item: https://doi.org/10.1145/1111542.1111563
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
Source: 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. https://doi.org/10.1145/1111542.1111563
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
URI: http://scholarbank.nus.edu.sg/handle/10635/40353
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.

SCOPUSTM   
Citations

4
checked on Dec 5, 2017

Page view(s)

58
checked on Dec 9, 2017

Google ScholarTM

Check

Altmetric


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