Transitive Closure Algorithms for Causal Directed Graphs

A causal directed graph (CDG) is a finite directed graph with and-gates and or-nodes, in which nodes indicate true or false conditions and where arcs indicate causality. The set of all nodes implied true by a set of conditions (nodes declared true) is called the transitive closure of that set. Theorems 3-5 evaluate the number of distinct transitive closures for common CDGs. We present linear-space, linear-time algorithms for solving three transitive closure problems on CDG’s:

1. determine if a particular node is implied by a set of conditions,
2. Find the transitive closure of a set of conditions,
3. determine the minimal set of initial conditions for a given transitive closure of an acyclic CDG.

Implicit in Problem 3 is that every transitive closure of an acyclic CDG is generated by a unique minimal set of initial conditions. This is proved in Theorem 6.