![](https://csd.cmu.edu/sites/default/files/styles/full_width_focal_point/public/graduate.png.webp?itok=Wsy3nMEH)
Robert Wilber
Thesis Title:
A Comparison of the Black and Black-white Pebble Games
Degree Type:
Ph.D. in Computer Science
Advisor(s):
Merrick Furst
Graduated:
May
1985
Abstract:
The black pebble game is played by placing pebbles on, and removing them from, the vertices of a directed acyclic graph according to rules that model the deterministic evaluation of a straight-line program. The black-white pebble game models nondeterministic evaluations. In both there is a dag with vertix indegrees bounded by 2 for which an optimal programs for which nondeterminism reduces the space required to evaluate the programs by more than any constant factor.