Graph Representations of Monotonic Boolean Model Pools 241section, we first need to adapt the notion of derivative sign vectors and abstrac-
tions. A first approach could be to consider the difference vectors of a state and
its image under the Boolean functionfto capture the tendencies to increase
or decrease. It turns out, however, that for transferring the results of Sect.2.2
the better choice is to just assign values 1, if the image value underfis 1, and
−1, if the image value is 0. This choice becomes more meaningful when relating
Boolean to corresponding ODE systems as we will discuss later.
To formalize this value assignment, we introduce the function
φf:{ 0 , 1 }n→{− 1 , 1 }n,φf(s) →
(
(−1)^1 −fi(s))
i=1,...,n. (2)
Usingφfwe can now assign a sign vector to every state in the state transition
graph off. Naturally, several states correspond to the same sign vector. To
associate the set of these states to the corresponding sign vector, we consider
the equivalence relation induced byφfon the verticesVasync(f):
s≈t:⇔φf(s)=φf(t).Since two states are in the same equivalence class if and only if their images
underφfare the same we identify the equivalence classes with the states ofφf.
In a next step, we want to obtain abstractions. The trajectories of the Boolean
system are the paths in the asynchronous state transition graph, so we infer
edges between sign vectors (representing sets of nodes of the state transition
graph) from the edges in the state transition graph. For this, we simply consider
the quotient graphGasync(f)
/
φf, which consists of the node set induced by the
above equivalence class, identified with the images ofφf, and an edge between
two equivalence classes if there is at least one edge between two nodes in the
preimages ofφfinGasync(f).
Sincefi(s)=0⇔φf(s)i=−1andfi(s)=1⇔φf(s)i= 1, we see thatfand
φfinduce the same equivalence relation, and thusGasync(f)
/
φf=Gasync(f)/
f.Example 5.We illustrate the notions using the Boolean functionffrom Exam-
ple 1 again. Its ASTGGasync(f) is depicted in Fig. 1. In Fig. 3 the quotient graph
Gasync(f)
/
φfis depicted. Each vertex represents an equivalence class on the ver-
tices ofGasync(f) represented usingφf. The state (− 1 , 1 ,− 1 ,−1) for example
represents the equivalence classφf−^1 (− 1 , 1 ,− 1 ,−1) ={(1, 0 , 1 ,1),(1, 1 , 1 ,1)}.
Looking at the example, we can detect some similarity between the quo-
tient graph and the state transition graph of the monotonic ensemble in
Fig. 3. To understand this similarity better we will derive a Boolean version of
Proposition 1. We obtain a nearly identical statement. One adjustment concerns
negative self-loops, which in the time-discrete other than in the continuous set-
ting potentially instigate oscillation in one component. We need to exclude such
an immediate sign switch in the following statement.
Theorem 1.If there is an edge(s, t)∈Easync(f)for a Boolean function
f:{ 0 , 1 }n→{ 0 , 1 }nthen
(
∀i∈diff(f(s),f(t))∃j∈comm(f(s),f(t)) : φf(t)i·φf(s)j=∂jfi(s)
)
(3)
or(
diff(s, t)∩diff(f(s),f(t)) ={j}and∂jfj(s)=− 1