Pebble games for studying storage sharing

Pebble games are played on a directed acyclic graph (dag). Placing a pebble on a vertex may be thought of as entering the value of the subexpression represented by the vertex into accessible storage. In some applications, there are types associated with vertices e.g. some vertices may represent functions, others may represent function values. We are interested in determining if vertices of the same type can share storage. The problem considered is as follows. We are given a labelled dag to be pebbled. A pebble may be placed on a vertex if all sons of the vertex have pebbles-in fact it is legal to move a pebble from a son to a father. Pebbles may be picked up at any time. The objective is to pebble each vertex exactly once. We will be interested in 'one pebblings of l vertices' in which there is at most one pebble on vertices with label l, at all times; and 'stack pebblings of l vertices' in which the pebbled vertices with label l are along a path, at all times. Results about the existence of such pebblings are presented. The results have applications to testing serializability of database updates, and potential applications to semantics directed compiler generation.