CMU-CS-85-156

Computer Science Department
School of Computer Science, Carnegie Mellon University


CMU-CS-85-156

A Comparison of the Black and Black-White Pebble Games

CMU-CS-85-156

Robert Wilber

June 1985 - Thesis

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.

37 pages


Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by reports@cs.cmu.edu