Computational Methods in Systems Biology

242 R. Schwieger and H. Siebert

Proof. Let (s, t)∈Easync(f). By definition of the asynchronous update diff(s, t)
is either empty, and the statement holds trivially, or contains one element. In
the following letj∈diff(s, t) be this element. Consider the following two cases:

Case 1:j∈commf(s)f(t). Fori∈diff(f(s),f(t)), we can build the following
table by considering all possible values offi(s) and listing in the corresponding
row some inferred values.

fi(s)=0φf(s)i=− 1 fi(t)=1φf(t)i=1 fi(t)−fi(s)=1

fi(s)=1φf(s)i=1 fi(t)=0φf(t)i=− 1 fi(t)−fi(s)=− 1

Sincej∈comm(f(s),f(t)),j∈diff(s, t) and (s, t)∈Easync(f), we obtain:

sj=1fj(s)=0tj=0fj(t)=0φf(s)j=− 1 tj−sj=− 1

sj=0fj(s)=1tj=1fj(t)=1φf(s)j=1 tj−sj=1

Taking the last two columns of these tables, we obtain by substitution

φf(t)i·φf(s)j=

[

fi(t)−fi(s)

]

·

[

tj−sj

]

=

fi(t)−fi(s)

tj−sj

=

fi(s⊕ej)−fi(s)

sj⊕ 1 −sj

=∂jfi(s).

Case 2:j∈difff(s)f(t). Due totj=sj,tj=fj(s)andfj(t)=fj(s) we get:

sj tj fj(s) fj(t) tj−sj fj(t)−fj(s)

0 1 1 0 1 − 1

1 0 0 1 − 1 1

From the last two columns we can deduce that there is a negative self-loop:

∂jfj(s)=

fj(s⊕ej)−fj(s)

sj⊕ 1 −sj

=

fj(t)−fj(s)

tj−sj

=− 1.



Before we continue, we want to emphasize the importance of Theorem 1 with
respect to two aspects. First, if we restrict ourselves to Boolean functions without
self-loops, it gives us a condition for an edge inGasync(f) purely in terms off.
Indeed, we will see later that in principle it is enough to know the image of
f andIGf(·) This means, we can deduce information aboutGasync(f)

/

φf=
Gasync(f)

/

ffromIGf(·) without having full information aboutf. Second, if we
compare Theorem 1 with Proposition 1 , we notice that they are identical, if we