Space-Time Tradeoffs for Linear Recursion.
Sowmitri Swami, John E. Savage:
Space-Time Tradeoffs for Linear Recursion.
POPL 1979: 135-142@inproceedings{DBLP:conf/popl/SavageS79,
author = {Sowmitri Swami and
John E. Savage},
title = {Space-Time Tradeoffs for Linear Recursion},
booktitle = {POPL},
year = {1979},
pages = {135-142},
ee = {db/conf/popl/SavageS79.html},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX
Abstract
A linear recursive procedure is one in which a procedural call can activate at most one other procedural call.
When linear recursion cannot be replaced by iteration, it is usually implemented with a stack of size proportional to the depth of recursion.
In this paper we analyze implementations of linear recursion which permit large reductions in storage space at the expense of a small increase in computation time.
For example, if the depth of recursion is sqrt(n), storage space can be reduced to n at the cost of a constant factor increase in running time.
The problem is treated by abstracting linear recursion into the pebbling of a simple graph and for this abstraction we exhibit the optimal space-time tradeoffs.
Copyright © 1979 by the ACM,
Inc., used by permission. Permission to make
digital or hard copies is granted provided that
copies are not made or distributed for profit or
direct commercial advantage, and that copies show
this notice on the first page or initial screen of
a display along with the full citation.
POPL Proceedings Compendium
CDROM Version: Load the CDROM "POPL, The First Ten Years" and ...
BibTeX
Printed Edition
Conference Record of the Sixth Annual ACM Symposium on Principles of Programming Languages, San Antonio, Texas, January 1979.
ACM 1979 BibTeX
Contents
BibTeX
Copyright © Sat May 16 23:34:35 2009
by Michael Ley (ley@uni-trier.de)
