Causal invariance is the property of a multiway system whose causal graphs, starting from a given initial
condition, are all isomorphic as acyclic
digraphs. Each causal graph is then also called
causally invariant. Thus, different update histories have the same causal structure
up to graph isomorphism. This condition does
not require the same events or the same final states. In general, neither causal
invariance nor confluence implies the other with this
definition (Piskunov 2020). For example, the rules 
and 
, with no further rules, give two evolutions from 
, each with a one-vertex causal graph. These causal
graphs are isomorphic, but the distinct
terminal states 
and 
cannot reach a common state, so the reduction system
is not confluent. The figures above illustrate two
nontrivial substitution systems that exhibit
the same causal graphs independent of the order in
which the rules are applied (Wolfram 2002, pp. 500-501).
Overlapping rule hypotheses can lead to inequivalent causal graphs, but overlap alone does not preclude causal invariance. One simple search
strategy is to use rules whose hypotheses can never overlap except trivially. Overlaps
may also be compatible when their competing updates resolve. An overlap can involve
one or two strings. For example, 
does not have any overlaps. However, 
can overlap as 
, and the set of strings 
can overlap as 
.
A mobile automaton simulated by a string rewriting system is an example of a causally invariant network in which rule hypotheses overlap, as long as the initial condition contains only a single active cell.
