Please use this identifier to cite or link to this item: https://doi.org/10.1145/1111542.1111563
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.date.accessioned2013-07-04T08:02:23Z
dc.date.available2013-07-04T08:02:23Z
dc.date.issued2006
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="https://doi.org/10.1145/1111542.1111563" target="_blank">https://doi.org/10.1145/1111542.1111563</a>
dc.identifier.isbn1595931961
dc.identifier.urihttp://scholarbank.nus.edu.sg/handle/10635/40353
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.description.urihttp://libproxy1.nus.edu.sg/login?url=http://dx.doi.org/10.1145/1111542.1111563
dc.sourceScopus
dc.subjectEfficient time complexity
dc.subjectProgram transformation
dc.subjectRecurrences with one or multiple parameters
dc.typeConference Paper
dc.contributor.departmentCOMPUTER SCIENCE
dc.description.doi10.1145/1111542.1111563
dc.description.sourcetitleProceedings of the ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation
dc.description.page121-129
dc.identifier.isiutNOT_IN_WOS
Appears in Collections:Staff Publications

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

SCOPUSTM   
Citations

4
checked on Jun 9, 2019

Page view(s)

83
checked on May 23, 2019

Google ScholarTM

Check

Altmetric


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