Home Work Exercise -- Week 2 on CCS


Note. Please explain what is going on, what are the processes (capable
of) doing, what are you thinking. Point c) is just optional (hence you
do it only if you wish).


(a) State what it means for a binary relation between CCS processes to
be a strong bisimulation. Define the strong bisimulation equivalence
between CCS processes.




(b) Consider the CCS processes 

    P =def a.(tau.b.c.0 + tau.c.b.0) 

    Q =def a.tau .(b.c.0 + c.b.0) 

    R =def (a.d.b.0 | 'd.c.0)\d

Determine whether the following statements about bisimilar processes
are true or false. If true, give a strong bisimulation relation
containing the processes. If false, prove that no such strong
bisimulation relation exists.

	     i.  P ~ R 
	     ii. Q ~ R 




(c) (Optional&Tricky) Let R =def a.a.(b.c.0 + c.b.0). Prove that R ~ P | Q
implies P ~ 0 or Q ~ 0, for arbitrary processes P and Q.