Вероятностная бисимуляция - Probabilistic bisimulation

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

Дискретная вероятностная переходная система - это тройная

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

куда ${ Displaystyle тау (с, а, т)}$ дает вероятность запуска в состоянии s, выполняя действие а и в конечном итоге в состоянии т. Предполагается, что множество состояний счетно. Нет попытки приписать действиям вероятности. Предполагается, что действия недетерминированно выбираются противником или окружающей средой. Этот тип системы является полностью вероятностным, другой неопределенности нет.

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

Применительно к Цепи Маркова, вероятностная бисимуляция - это то же понятие, что и комковатость.^[2]^[3]Вероятностная бисимуляция естественным образом распространяется на взвешенную бисимуляцию.^[4]

Рекомендации

^ К. Г. Ларсен и А. Скоу и появились в статье Бисимуляция посредством вероятностного тестирования, опубликовано в "Информация и вычисления", том 94, страницы 1-28, 1991 г.
^ Вероятностное невмешательство через слабую вероятностную бисимуляцию Джеффри Смит Труды 16-го семинара по основам компьютерной безопасности IEEE (CSFW’03) 1063-6900 / 03
^ Кемени, Джон Г.; Снелл, Дж. Лори (июль 1976 г.) [1960]. Геринг, Ф. В .; Халмос, П. Р. (ред.). Конечные цепи Маркова (Второе изд.). Нью-Йорк Берлин Гейдельберг Токио: Springer-Verlag. п. 224. ISBN 978-0-387-90192-3.
^ Оливейра, Дж. (2013). «Весовые автоматы как коалгебры в категориях матриц». Int. J. Found. Comput. Наука. 24 (6): 709–728. Дои:10.1142 / S0129054113400145.

[1] К. Г. Ларсен и А. Скоу и появились в статье Бисимуляция посредством вероятностного тестирования, опубликовано в "Информация и вычисления", том 94, страницы 1-28, 1991 г.

[2] Вероятностное невмешательство через слабую вероятностную бисимуляцию Джеффри Смит Труды 16-го семинара по основам компьютерной безопасности IEEE (CSFW’03) 1063-6900 / 03

[3] Кемени, Джон Г.; Снелл, Дж. Лори (июль 1976 г.) [1960]. Геринг, Ф. В .; Халмос, П. Р. (ред.). Конечные цепи Маркова (Второе изд.). Нью-Йорк Берлин Гейдельберг Токио: Springer-Verlag. п. 224. ISBN 978-0-387-90192-3.

[4] Оливейра, Дж. (2013). «Весовые автоматы как коалгебры в категориях матриц». Int. J. Found. Comput. Наука. 24 (6): 709–728. Дои:10.1142 / S0129054113400145.

[1]

[2]

[3]

[4]