This research investigates a class of pebble games developed by Moschovakis and Aczel, by studying the behavior of these games. There is much current interest in the intersection of logic and complexity theory, and pebble games have been used to because of their expressibility and their intuitive appeal. These games will be applied to two kinds of problems. First, there are some queries that might not be expressed in certain logics, e.g., it is conjectured that the graph distance relation dist(x,y) > dist(u,v) cannot be expressed in the fragment of least fixed point logic (without successor) that admits only finitely many alternations. Second, there are some problems in random graph theory that might best be addressed with pebble game techniques.
