Топ-100
Indietro

ⓘ Bisimulazione. Nel campo dellinformatica teorica la bisimulazione è una relazione binaria tra sistemi a transizione di stati, che associa due sistemi quando si ..




                                     

ⓘ Bisimulazione

Nel campo dellinformatica teorica la bisimulazione è una relazione binaria tra sistemi a transizione di stati, che associa due sistemi quando si comportano nello stesso modo, quando cioè un sistema simula laltro e viceversa.

Intuitivamente due sistemi sono bisimilari se le transizioni di uno possono essere ordinatamente mimate dallaltro, ed è in questo senso che si dice che un osservatore non è in grado di distinguerli.

                                     

1. Definizione formale

Dato un sistema a transizione di stati, una relazione di bisimulazione è una relazione binaria R {\displaystyle R} su S {\displaystyle S} quindi R ∈ S × S {\displaystyle R\in S\times S} tale che sia R {\displaystyle R} -1 and R {\displaystyle R} è una simulazione.

Equivalentemente R {\displaystyle R} è una bisimulazione se per ogni coppia di elementi p, q {\displaystyle p,q} in S {\displaystyle S} con p, q {\displaystyle p,q} in R {\displaystyle R}, per ogni α {\displaystyle \alpha } in Λ {\displaystyle \Lambda }:

per ogni p ′ {\displaystyle p} in S {\displaystyle S},

p → α p ′ {\displaystyle p{\overset {\alpha }{\rightarrow }}p}

implica che esiste un q ′ {\displaystyle q} in S {\displaystyle S} tale che

q → α q ′ {\displaystyle q{\overset {\alpha }{\rightarrow }}q}

con p ′, q ′ ∈ R {\displaystyle p,q\in R} ; e, simmetricamente, per ogni q ′ {\displaystyle q} in S {\displaystyle S}

q → α q ′ {\displaystyle q{\overset {\alpha }{\rightarrow }}q}

implica che esiste un p ′ {\displaystyle p} in S {\displaystyle S} tale che

p → α p ′ {\displaystyle p{\overset {\alpha }{\rightarrow }}p}

e p ′, q ′ ∈ R {\displaystyle p,q\in R}.

Dati due stati p {\displaystyle p} e q {\displaystyle q} in S {\displaystyle S}, p {\displaystyle p} è bisimilare a q {\displaystyle q}, scritto p ∼ q {\displaystyle p\,\sim \,q}, se esiste una bisimulazione R {\displaystyle R} tale che p, q ∈ R {\displaystyle p,q\in R}.