Please use this identifier to cite or link to this item:
DC FieldValue
dc.titleProgram transformation by solving recurrences
dc.contributor.authorLuca, B.
dc.contributor.authorAndrei, S.
dc.contributor.authorAnderson, H.
dc.contributor.authorKhoo, S.-C.
dc.identifier.citationLuca, 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. <a href="" target="_blank"></a>
dc.description.abstractRecursive 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.
dc.subjectEfficient time complexity
dc.subjectProgram transformation
dc.subjectRecurrences with one or multiple parameters
dc.typeConference Paper
dc.contributor.departmentCOMPUTER SCIENCE
dc.description.sourcetitleProceedings of the ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation
Appears in Collections:Staff Publications

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


checked on Jun 9, 2019

Page view(s)

checked on May 23, 2019

Google ScholarTM



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