A Time-Space Trade-Off

Document Type

Article

Department

Mathematics (HMC)

Publication Date

1978

Abstract

A problem with a demonstrable time-space trade-off is exhibited. The problem is to compile a straight-line program for a certain uninterpreted expression; time is reckoned as the number of instructions in the program,. space as the number of registers referred to. There are programs using linear space and linear time, but any program using less than linear space uses more than linear time.

Rights Information

© 1978 Association for Computing Machinery

Terms of Use & License Information

Terms of Use for work posted in Scholarship@Claremont.

Link to Full Text

Share

COinS