A comparison of two variations of a pebble game on graphs

AbstractThe number of pebbles used in the black [black-white] pebble game corresponds to the storage requirement of the deterministic [non-deterministic] evaluation of a straight line program. Suppose a distinguished vertex of a directed acyclic graph can be pebbled with k pebbles in the black-white pebble game. Then it can be pebbled with k′≤1/2k(k−1)+1 pebbles in the black pebble game