Tech Report CS-92-19

Combine and Conquer

Abstract:

We present a general technique for dynamizing a class of problems whose underlying structure is a computation graph embedded in a tree. We associate values, called {\em attributes}, with the nodes, paths, and subtrees of our trees. Path attributes form a {\em path attribute system}, if they are maintained in constant time under path concatenation. Additionally, attributes form a {\em tree attribute system} if the tree attributes of the tail of a path $\Pi$ are determined in constant time from the path attributes of $\Pi$.

We also introduce a new data structure called a {\em linear attribute grammar}. An {\em attribute grammar} is a tree-based expression where the values a node $\mu$ are calculated from the values at the parent, siblings, and/or the children of $\mu$. A linear attribute grammar, is an attribute grammar where all dependencies are linear.

Our contributions can be summarized as follows. We provide a framework for maintaining attribute systems on trees in a fully dynamic environment. We show that given a semiring ${\cal S}$, a set of linear expressions with binary and unary operators over ${\cal S}^k$ can be dynamically maintained in a fully dynamic environment using linear space and logarithmic time per operation. We show that a linear attribute grammar can be dynamically maintained in a fully dynamic environment using linear space and logarithmic time per operation. Finally, we present many examples of application of our technique to dynamic graph and geometric problems.

(complete text in pdf or gzipped postscript)