patternMinor
Weak bisimulation up-to $\approx$
Viewed 0 times
approxweakbisimulation
Problem
Given this definition of weak bisimilarity:
A configuration relation $\mathcal{R}$ is a weak bisimulation
provided that whenever $P\ \mathcal{R}\ Q$ and $\alpha$ is $\mu$ or $\tau$ action then:
-
$P \to^\alpha P'$ then $Q \Rightarrow^\widehat{\alpha} Q'$ for some $Q'$ s.t. $P'\ \mathcal{R}\ Q'$
-
$Q \to^\alpha Q'$ then $P \Rightarrow^\widehat{\alpha} P'$ for some $P'$ s.t.
$P'\ \mathcal{R}\ Q'$
P and Q are weakly bisimilar, written $P \ \approx \ Q$, if $P \ \mathcal{R} \ Q$
for some configuration relation $\mathcal{R}$.
My questions are:
-
According to Sangiorgi's book, P uses $\tau$ and ends up with $a \approx \tau.a$ and Q has $0$ and ignores the move. I am wondering, how is it that you can ignore the move? I thought that one is forced to do a move...
-
Could you please provide an detailed explanation of why weak bisimilarity up-to $\approx$ is unsound? (You can use the example above but I would appreciate a detailed explanation
Thanks.
A configuration relation $\mathcal{R}$ is a weak bisimulation
provided that whenever $P\ \mathcal{R}\ Q$ and $\alpha$ is $\mu$ or $\tau$ action then:
-
$P \to^\alpha P'$ then $Q \Rightarrow^\widehat{\alpha} Q'$ for some $Q'$ s.t. $P'\ \mathcal{R}\ Q'$
-
$Q \to^\alpha Q'$ then $P \Rightarrow^\widehat{\alpha} P'$ for some $P'$ s.t.
$P'\ \mathcal{R}\ Q'$
P and Q are weakly bisimilar, written $P \ \approx \ Q$, if $P \ \mathcal{R} \ Q$
for some configuration relation $\mathcal{R}$.
My questions are:
- For the relation $\mathcal{R} = \{(\tau.a, 0)\}$, $\mathcal{R} \nsubseteq \approx$ but $\mathcal{R} \subseteq \, \approx \! \mathcal{R} \approx$. Why is $\mathcal{R} \subseteq \, \approx \! \mathcal{R} \approx$?
-
According to Sangiorgi's book, P uses $\tau$ and ends up with $a \approx \tau.a$ and Q has $0$ and ignores the move. I am wondering, how is it that you can ignore the move? I thought that one is forced to do a move...
-
Could you please provide an detailed explanation of why weak bisimilarity up-to $\approx$ is unsound? (You can use the example above but I would appreciate a detailed explanation
Thanks.
Solution
(partial answer)
Actually, the inclusion $\mathcal{R} \subseteq \, \approx \! \mathcal{R} \approx$ holds for any relation $\mathcal{R}$, and not just the one mentioned. Indeed, if we have $P \mathcal{R} Q$, then we also have $P \approx P \mathcal{R} Q \approx Q$, by reflexivity of weak bisimulation.
You have to check that $0\xrightarrow{{\hat\tau}} 0$, which (if I remember correctly) is defined as $0\xrightarrow{{\tau}}^* 0$ which holds since the Kleene's star includes "zero steps".
I seem to remember that the "$\hat\alpha$" move definition made a special case for $\hat\tau$, specifically to allow for zero steps.
- For the relation $\mathcal{R} = \{(\tau.a, 0)\}$, $\mathcal{R} \nsubseteq \approx$ but $\mathcal{R} \subseteq \, \approx \! \mathcal{R} \approx$. Why is $\mathcal{R} \subseteq \, \approx \! \mathcal{R} \approx$?
Actually, the inclusion $\mathcal{R} \subseteq \, \approx \! \mathcal{R} \approx$ holds for any relation $\mathcal{R}$, and not just the one mentioned. Indeed, if we have $P \mathcal{R} Q$, then we also have $P \approx P \mathcal{R} Q \approx Q$, by reflexivity of weak bisimulation.
- According to Sangiorgi's book, P uses $\tau$ and ends up with $a \approx \tau.a$ and Q has $0$ and ignores the move. I am wondering, how is it that you can ignore the move? I thought that one is forced to do a move...
You have to check that $0\xrightarrow{{\hat\tau}} 0$, which (if I remember correctly) is defined as $0\xrightarrow{{\tau}}^* 0$ which holds since the Kleene's star includes "zero steps".
I seem to remember that the "$\hat\alpha$" move definition made a special case for $\hat\tau$, specifically to allow for zero steps.
Context
StackExchange Computer Science Q#87653, answer score: 2
Revisions (0)
No revisions yet.