Please use this identifier to cite or link to this item:
|Title:||Program transformation by solving recurrences||Authors:||Luca, B.
|Keywords:||Efficient time complexity
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. 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.
checked on Jun 16, 2019
checked on May 23, 2019
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.