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.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.