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

20

Dado um sistema de transição rotulado (S,Λ,) , onde S é um conjunto de estados, Λ é um conjunto de rótulos e →⊆S×Λ×S é uma relação ternária. Como sempre, escreva pα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,α,q)∈→pαqpqαα é 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 ' ,RS×S

(p,q)R, if pαp then q,qαq and (p,q)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 forRS×S se  p α p  então  q ,(p,q)R,

 if pαp then q,qαq and (p,q)R and  if qαq then p,pαp and (p,q)R.

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?

Dave Clarke
fonte

Respostas:

12

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=umab+uma
Q=umab

é uma simulação.R1={(umab+uma,umab),(b,b),(0 0,b),(0 0,0 0)}

é uma simulação.R2={(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 R1 QQ R2 PPQPa0QQaQb0b

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)PQQQPPumaQumaRRR-1

jmad
fonte
10

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.R1R2p1qR1R2

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).

escolha precoce e tardia

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 .R1={(s,s),(p,p),(q,q),(r,p)}rrp

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 sR2={(s,s),(p,p),(q,q)}rrs2sp 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 .scpr1pqqr

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.rr

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.)

Gilles 'SO- parar de ser mau'
fonte
O fato de duas simulações unidirecionais não serem iguais à bisimilaridade sugere para mim que a simulação não é a idéia certa de aproximação na presença de não-determinismo. Existem outras idéias que foram consideradas?
Uday Reddy
2

euTS1euTS2ReuTS2euTS1RR

euTS1euTS2ReuTS2euTS1R

Charles
fonte
Eu acho que o que estou tentando dizer é que, na verdade, é sempre o caso de dois LTSs serem bimilares; portanto, a questão real é se uma relação específica é uma simulação (bi).
Charles