Mutexes can develop not only in the same possible world but also between two possible worlds, as described by . Cross-world mutexes are useful to capture negative interactions in belief state distance measures (mentioned in Section 3). The representation of cross-world mutexes requires another generalization for the labelling of mutexes. Same world mutexes require keeping only one label for the mutex to signify all same possible worlds for which the mutex holds. The extended representation keeps a pair of labels, one for each element in the mutex; if in possible world is mutex with in possible world , we denote the mutex as the pair ( ).
We can compute cross-world mutexes between several worlds of elements and . For example, if and , then to check for all cross-world mutexes we need to consider mutexes for the world pairs , and . We can also check for mutexes in the intersection of the element labels , meaning the only cross world pairs we check for mutexes are , and .
We can say that a formula is reachable from our projected belief state , when considering cross-world mutexes, if for every pair of states in , is reachable. For a pair of states and , is reachable if and for every pair of constituents such that and , there are no two literals in either or that are same-world mutex when , and there is not a mutex between literals in and , across the respective worlds and when . There is a mutex between a pair literals and , respectively from and if there is a mutex such that and .
The computation of cross-world mutexes requires changes to some of the mutex formulas, as outlined next. The major change is to check, instead of all the single possible worlds , all pairs of possible worlds and for mutexes.
Action Mutexes: The action mutexes can now hold for actions that are executable in different possible worlds.
Effect Mutexes: The effect mutexes can now hold for effects that occur in different possible worlds.
If in is mutex with in , and induces effect in the possible worlds described by , then there is an induced mutex between in and in (see Figure 12).
Literal Mutexes: The literal mutexes can now hold for literals that are supported in different possible worlds.