Probabilistic Bisimulation - Semantics of Probabilistic Processes: An Operational Approach - page 40

† ʘ , by Proposition 3.1 we can decompose ʔ and ʘ as follows.

1. ( ⃒ ) Since ʔ R

ʔ = p i · s i s i R t i ʘ = p i · t i .

i ∈ I i ∈ I

Note that { s i } i ∈ I = ʔ . We define an index set J : ={ i ∈ I | s i ∈ A } . Then

ʔ ( A ) ={ p j } j ∈ J . For each j ∈ J we have s j R t j , i.e. t j ∈ R ( s j ). It follows that

{ t j } j ∈ J ↆ R ( A ). Therefore, we can infer that

ʔ ( A ) = ʔ ( { s j } j ∈ J ) = p j ≤ ʘ ( { t j } j ∈ J ) ≤ ʘ ( R ( A )) .

j ∈ J

( ) In view of Theorem 3.4 it suffices to show that the maximum flow of the

network

⃐

) is 1. According to the maximum flow minimum cut theorem
by Ford and Fulkerson [ 42 ], the maximum flow equals the capacity of a minimal
cut. We show that

N ( ʔ , ʘ , R

is a minimal cut of capacity 1. Clearly this cut has capacity
1. To see the minimality, let C

{ s ↥ }

={

s ↥ } be some minimal cut. The capacity of C is

= {

c ( s , t )

| ∈

C , t ∈

}

c ( C ) s C . If the cut C involves an edge of capacity 1,

i.e. ( s , t ) ∈ R with s ∈ C and t ∈ C , then { s ↥ } is a cut of smaller or equal capacity

since its capacity is 1. Let B = C ∩ S , and thus we can assume that if s ∈ B then

{ t | t ∈ R ( s ) }ↆ C . Hence the capacity of C is c ( C ) = ʔ ( S \ B ) + ʘ ( R ( B )).

Since ʔ ( B ) ≤ ʘ ( R ( B )), we have

c ( C ) ≥ ʔ ( S \ B ) + ʔ ( B ) = ʔ ( S ) = 1 .

Therefore, the capacity of C is greater than or equal to 1, which means that the
minimum cut has capacity 1.
2. When

is a preorder, we can show that the following two conditions are equiv-
alent: (i) ʔ ( A )

R

≤ ʘ ( R ( A )) for all A ↆ S , (ii) ʔ ( A ) ≤ ʘ ( A ) for each R -closed

set A ↆ S . For one direction, suppose (i) holds and A is a R -closed set. Then

R ( A ) ↆ A , and thus ʘ ( R ( A )) ≤ ʘ ( A ). Combining this with (i) we see that

ʔ ( A ) ≤ ʘ ( A ). For the other direction, suppose (ii) holds and pick up any A ↆ S .

Since R is reflexive, we have A ↆ R ( A ), and thus ʔ ( A ) ≤ ʔ ( R ( A )). By the tran-

sitivity of R we know that R ( A )is R -closed. By (ii) we get ʔ ( R ( A )) ≤ ʘ ( R ( A )).

Combining the previous two inequalities, we obtain ʔ ( A ) ≤ ʘ ( R ( A )).

Remark 3.1 to be a preorder,

which is used in showing the equivalence of the two conditions (i) and (ii) in the
above proof. If

Note that in Theorem 3.5 (2) it is important to require R

is not a preorder, the implicatio n fro m (ii) to (i) is i n vali d in general.
For example, let S

R

1 1 1 2

={ s , t } , R ={ ( s , t ) } , ʔ =

2 s

+

2 t and ʘ

=

3 s

+

3 t . There are

only two nonempty R -closed sets: { t } and S . Clearly, we have both ʔ ( { t } ) ≤ ʘ ( { t } )

and ʔ ( S ) ≤ ʘ ( { t } ) . However,

1
2 ≤

ʔ ( { t } ) = 0 = ʘ ( ∅ ) = ʘ ( R ( { t } )) .

Note also that Theorem 3.5 can be generalised to countable state spaces. The
proof is almost the same except that the maximum flow minimum cut theorem for
countable networks [ 43 ] is used. See [ 44 ] for more details.