244 R. Schwieger and H. Siebert
This graph, which is due to Proposition 1 the same object asGQDE(Σ), can be
constructed without any consideration of specific functions in the ensemble. Nev-
ertheless, Theorem 1 enables us to extract information on specific state transition
graphs using the quotient graph.
Theorem 2.Letf ∈MB(Σ).Themapφf is a graph homomorphism from
Gasync(f)intoGBooleanQDE (Σ).
Proof. By definition,φfmaps the vertex set{ 0 , 1 }nofGasync(f) into the vertex
set ofGBooleanQDE (Σ). Now, we show thatφf conserves the edges. Let (s, t) ∈
Easync(f) and setv:=φf(s),w:=φf(t).
By definition and as discussed in Sect. 3 ,φf is a graph epimorphism from
Gasync(f)ontoGasync(f)
/
φf. Therefore, we only need to show thatGasync(f)/
φf
is a subgraph ofGBooleanQDE (Σ). But this is clear, since the criterion for an edge in
Gasync(f)
/
φfis according to Theorem 1 just Condition ( 4 ), which in turn defines
the edges inGBooleanQDE (Σ).
We can utilize this theorem to obtain reachability constraints for every Boolean
functionfin the monotonic ensemble since the lack of an edge inGBooleanQDE (Σ)
implies the lack of the corresponding edge in the ASTG off. The following
corollary illustrates this point for trap sets, i.e., sets of states no trajectory can
leave, and no-return sets, i.e., sets of states that no trajectory enters.
Corollary 2.Assume the setT⊆VQDEBooleanis a trap set (or a no-return set) in
GBooleanQDE (Σ). Then for anyf∈MB(Σ)the setφ−f^1 (T)is a trap set (no-return
set) inGasync(f). More generally speaking: IfT 1 ,T 2 ⊆VQDEBooleanand there is no
path betweenT 1 andT 2 inGBooleanQDE (Σ)then for anyf∈MB(Σ)there is no path
fromφ−f^1 (T 1 )toφ−f^1 (T)inGasync(f).
Trap sets are of particular interest in application since they always contain
at least one attractor. However, not every trap set inGBooleanQDE (Σ) gives rise to
atrapsetinGasync(f) since the preimage might be empty. Conversely, since
GBooleanQDE (Σ) can be interpreted as a supergraph of a corresponding ASTG, there
might be trap sets inGasync(f) that cannot be identified inGBooleanQDE (Σ). In
any case, to obtain explicit information on a functionfin the ensemble, we
need to calculate preimages, which in general is a hard problem [ 6 ]. However,
in some situations we can test very cheaply if a preimage is empty or if it is
worth computing it with respect to the long term behavior of the system as we
illustrate with the following statements.
For easier notation, we now identify the nodesGBooleanQDE (Σ) with the elements
in the image of anyf∈MB(Σ) (and thus Boolean states), as previously done
forφf.
Corollary 3.Assume the set{t}⊆VQDEBooleanis a trap set of cardinality 1 in
GBooleanQDE (Σ). Then for anyf∈MB(Σ)the setf−^1 (t)is either empty orf(t)=t.
Iff(t)=tevery trajectory inf−^1 (t)⊆Gasync(f)ends int.