
## Is Non-Zero.

We now consider what new mutex relations can be inferred from the introduction of the new actions. It is necessary to check all new actions against all actions in the spike.

This check is done in only one direction - low-indexed actions against high-indexed actions
- so that the test is done only once for each pair. We check for both permanent and temporary mutex relations. The permanent mutex test is done first, because if two actions are permanently mutex it is of no interest to find that they are also temporarily mutex.

Definition 10 provides the logical operation used to confirm that two actions are permanently mutex. Temporary mutex relations are checked for using the logical operation defined in Definition 9.

Definition 10 Two actions a and b are permanently mutex if the result of
(precs_of (a) V adds_of (a)) ^ dels_of (b)) V
(precs_of(b) V adds_of(b)) ^ dels_of(a))

## Is Non-Zero.

We add these mutex relations by setting the appropriate bits in the mutex vectors of each of the new actions. This is done by oring the mutex vector of the first action with the bit mask of the second action, and vice versa. A list of mutex actions is also maintained for use during search of the spike.

A refinement of the action mutex checking done by STAN is the use of a record of actions whose preconditions have lost mutex relations since the last layer of the graph. This record enables STAN to avoid retesting temporary mutex relations between actions when the mutex relations between their preconditions cannot have changed. We use a bit vector called changedActs to record this information. Each fact which loses mutex relations between layers adds its consumers to changedActs. The impact of this refinement on efficiency is discussed in Section 3.

This concludes the construction of the new action rank. The new fact rank has already been partially constructed by the addition to the spike of fact headers for any add list elements, of the new actions, that were not already present. Now it is necessary to determine mutex relations between all pairs of facts in the spike. To do this we must first complete the achievement vectors for all of the fact headers in the new rank. Any non-mutex pairs remain non-mutex, as with actions, so effort is focussed on deciding whether previously mutex facts are still mutex following the addition of the new actions, and whether new facts induce new mutex relations. Two facts are mutex if the only way of achieving both of them involves the use of mutex actions. We therefore consider every new fact with every other fact, in only one direction. The pair f, g is mutex in the new rank if every possible achiever of f is mutex with every possible achiever for g. The test for this exclusion is done using g's achievement vector and the result of logically anding the action mutex vectors for all possible achievers of f. the following definition gives the details:
Definition 11 Two facts, fand g, are mutex if: