Pebbling with an Auxiliary Pushdown

Authors

Nicholas Pippenger, Harvey Mudd CollegeFollow

Document Type

Article

Department

Mathematics (HMC)

Publication Date

1981

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 [image] (where T denotes time, S denotes space and N denotes the size of the graph), which contrasts with [image] for ordinary pebbling. The significance of this result to various questions concerning relations among complexity classes is discussed.

Rights Information

© 1981 Elsevier Ltd.

Terms of Use & License Information

Terms of Use for work posted in Scholarship@Claremont.

DOI

10.1016/0022-0000(81)90011-8

Recommended Citation

Nicholas Pippenger, Pebbling with an auxiliary pushdown, Journal of Computer and System Sciences, Volume 23, Issue 2, October 1981, Pages 151-165, ISSN 0022-0000, 10.1016/0022-0000(81)90011-8. (http://www.sciencedirect.com/science/article/pii/0022000081900118)