A Time-Space Trade-Off
Nicholas J. Pippenger · Journal of the ACM · 1978
A problem with a demonstrable Ume-space trade-off Is exhibited The problem is to compile a straight-line program for a certain unmterprted expression; time ~s reckoned as the number of mstrucUons m the program, space as the number of registers referred to There are programs using linear space and linear tune, but any program using less than linear space uses more than linear rune KEY WORDS AND PHRASES time, space, pebble game, straight-line program, register allocauon CR CATEGORIES 5 23, 5 24, 5 25, 5 32