About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Paper
Pebbling with an auxiliary pushdown
Abstract
A pebble game on graphs is introduced which bears the same relationship to the ordinary pebble game as auxiliary pushdown machines bear to ordinary machines. The worst-case time-space trade-off for pebbling with an auxiliary pushdown is shown to be T = N exp e( N S) (where T denotes time, S denotes space and N denotes the size of the graph), which contrasts with T = N exp exp e( N S) for ordinary pebbling. The significance of this result to various questions concerning relations among complexity classes is discussed. © 1981.