Вероятностное бисимуляция

В информатике теоретической вероятностное бисимуляция является расширением концепции бисимуляции полностью вероятностных переходных систем, впервые описанной К.Г. Ларсеном и А. Скоу .

Дискретная вероятностная переходная система представляет собой тройку

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

где $\tau (s,a,t)$ дает вероятность начаться в состоянии s , выполнить действие a и оказаться в состоянии t . Множество состояний предполагается счетным . Здесь не делается попыток приписать действиям вероятность. Предполагается, что действия выбираются недетерминировано противником или окружением. Этот тип системы полностью вероятностный, никакой другой неопределенности нет.

Определение вероятностной бисимуляции в системе S — это отношение эквивалентности R в пространстве состояний St, такое, что для каждой пары s , t в St с sRt и для каждого действия a в Act и для каждого класса эквивалентности C системы R $\tau (s,a,C)=\tau (t,a,C).$ Два состояния называются вероятностно биподобными, если существует некоторый такой R, связывающий их.

Применительно к цепям Маркова вероятностное бисимуляция представляет собой ту же концепцию, что и комкуемость . Вероятностное бисимуляция естественным образом расширяется до взвешенной бисимуляции.