Quando duas simulações não são uma bimimulação?

Dado um sistema de transição rotulado $(S,\Lambda,\to)$ , onde $S$ é um conjunto de estados, $\Lambda$ é um conjunto de rótulos e $\to\subseteq S\times\Lambda\times S$ é uma relação ternária. Como sempre, escreva $p \stackrel\alpha\rightarrow q$ para . A transição rotulada indica que o sistema no estado muda de estado para com label , o que significa quep α → q p q α $(p,\alpha,q)\in\to$$p\stackrel\alpha\to q$$p$$q$$\alpha$$\alpha$ é alguma ação observável que causa a mudança de estado.

Agora, uma relação é chamada de simulação iff ∀ ( p , q ) ∈ R ,  se  p α → p ′  então  ∃ q '$R \subseteq S \times S$

$$\forall (p,q)\in R, \text{ if } p \stackrel\alpha\rightarrow p' \text{ then } \exists q', \; q \stackrel\alpha\rightarrow q' \text{ and } (p',q')\in R.$$

Diz- se que um LTS simula outro se existir uma relação de simulação entre eles.

Da mesma forma, uma relação é uma bisimulação se for$R \subseteq S \times S$ se  p α → p ′  então  ∃ q ′$\forall (p,q)\in R,$

$$\begin{array}{l} \text{ if } p \stackrel\alpha\rightarrow p' \text{ then } \exists q', \; q \stackrel\alpha\rightarrow q' \text{ and } (p',q')\in R \text{ and } \\ \text{ if } q \stackrel\alpha\rightarrow q' \text{ then } \exists p', \; p \stackrel\alpha\rightarrow p' \text{ and } (p',q')\in R. \end{array}$$

Diz-se que dois LTSs são bisimilares se existir uma bisimulação entre seus espaços de estado.

Claramente, essas duas noções são bastante relacionadas, mas não são as mesmas.

Em que condições um LTS simula outro e vice-versa, mas que os dois LTSs não são bimilares?

Como um processo CCS vale mais que mil pixels - e é fácil ver o LTS subjacente -, aqui estão dois processos que simulam um ao outro, mas não são bisimilares:

$$P = ab + a$$ $$Q = ab$$

é uma simulação.$\mathcal{R_1}=\{(ab+a, ab), (b, b), (0,b), (0, 0)\}$

é uma simulação.$\mathcal{R_2}=\{(ab, ab+a), (b, b), (0,0)\}$

e Q R 2 P mas P e Q não são bimimilares. Por que não? Porque P a → 0 e o único Q ′ tal que Q a → Q ′ é b ... e 0 não é bisimilar a b .$P\ \mathcal R_1\ Q$$Q\ \mathcal R_2\ P$$P$$Q$$P\stackrel{a}→0$$Q'$$Q\stackrel{a}→Q'$$b$$0$$b$

Por que eles podem simular um ao outro, então? Porque simula Q, pois pode fazer tudo o que Q faz. E Q simula P porque, mesmo que P possa ir em uma etapa a para um programa que não faz nada, Q ainda pode fazer isso em uma etapa, e isso é o suficiente para simular alguma coisa. A principal diferença com a bisimulação é realmente que, como Charles disse, você precisa relacionar os mesmos processos com as duas simulações. (isto é, R de modo que R e R - 1 sejam simulações)$P$$Q$$Q$$Q$$P$$P$$a$$Q$$a$$\mathcal R$$\mathcal R$$\mathcal R^{-1}$

Mesmo se houver uma simulação em cada direção, as simulações podem não se relacionar com os mesmos conjuntos de estados. Às vezes, você tem uma simulação em uma direção e uma simulação R 2 na outra direção, e dois estados p 1 e q que são relacionados por R 1, mas não por R 2, nem por qualquer outra simulação na mesma direção.$R_1$$R_2$$p_1$$q$$R_1$$R_2$

O exemplo canônico são dois sistemas que têm os mesmos traços, mas fazem escolhas diferentes. Considere duas máquinas de bebidas: a primeira (a maligna) pega uma moeda ( c) e decide de maneira não determinística se deve entregar uma xícara de chá ( t). A segunda máquina (a boa) pega uma moeda ( c) e entrega uma xícara de chá ( t).

A boa máquina simula a má máquina: tome . Todas as transições de saída de estados são cobertas, incluindo r (que não possui transição de saída, por isso é trivial). Observe como a máquina boa esquece a diferença entre r e p .$R_1 = \{(s,s'), (p,p'), (q,q'), (r,p')\}$$r$$r$$p$

A máquina do mal simula a máquina do bem: tome . O estado r passa a não ser usado por esta simulação. De fato, não é possível para uma simulação usar r , já que s ' deve mapear para um estado a partir do qual um traço de comprimento 2 é possível; portanto, deve ser s ; p ' tem que mapear para um sucessor de $R_2 = \{(s',s),(p',p),(q',q)\}$$r$$r$$s'$$2$$s$$p'$ Com o rótulo c , então é p ou r , mas esse estado também deve ter um possível rastro do comprimento 1 , portanto deve ser p ; e pelo mesmo raciocínio q ' deve mapear para q , não deixando a possibilidade de mapear qualquer estado para r .$s'$$c$$p$$r$$1$$p$$q'$$q$$r$

Uma simulação em uma direção deve enviar algum lugar. Uma simulação na outra direção deve evitar r . Portanto, não existe uma relação que seja uma simulação em ambas as direções: os sistemas não são bisimilares.$r$$r$

A diferença entre as duas máquinas é que a máquina boa é determinística e (assumindo vivacidade) sempre entrega chá se você inserir uma moeda, enquanto a máquina do mal pode, por capricho, pegar a moeda, mas ficar presa, incapaz de distribuir o chá.

Esse tipo de diferença surge frequentemente no estudo de sistemas concorrentes. A resposta do jmad mostra um processo CCS com este LTS.

Para mais informações sobre bisimulações, recomendo as anotações de Davide Sangiorgi Sobre as origens da bisimulação e coindução . (Este é o exercício 1, p. 29, e as notas usam o mesmo exemplo.)

$LTS_1$$LTS_2$$R$$LTS_2$$LTS_1$$R$$R$

$LTS_1$$LTS_2$$R$$LTS_2$$LTS_1$$R$