bisimulación probabilística

En la ciencia de la computación teórica , la bisimulación probabilística es una extensión del concepto de bisimulación para sistemas de transición totalmente probabilísticos descritos por primera vez por KG Larsen y A. Skou . ^{[ 1 ]}

Un sistema de transición probabilístico discreto es un sistema triple

${\displaystyle S=(\operatorname {St} ,\operatorname {Act} ,\tau$ :\operatorname {St} \times \operatorname {Act} \times \operatorname {St} \rightarrow [0,1])}

dónde${\displaystyle \tau (s,a,t)}$Proporciona la probabilidad de comenzar en el estado s , realizar la acción a y terminar en el estado t . Se supone que el conjunto de estados es numerable . No se intenta asignar probabilidades a las acciones. Se asume que las acciones son elegidas de forma no determinista por un adversario o por el entorno. Este tipo de sistema es completamente probabilístico; no existe ninguna otra indeterminación.

La definición de una bisimulación probabilística en un sistema S es una relación de equivalencia R en el espacio de estados St, tal que para cada par s , t en St con sRt y para cada acción a en Act y para cada clase de equivalencia C de R${\displaystyle \tau (s,a,C)=\tau (t,a,C).}$ Se dice que dos estados son probabilísticamente bisimilares si existe alguna R que los relaciona.

Cuando se aplica a cadenas de Markov , la bisimulación probabilística es el mismo concepto que la agrupabilidad . ^{[ 2 ] [ 3 ]} La bisimulación probabilística se extiende naturalmente a la bisimulación ponderada. ^{[ 4 ]}