Pravděpodobnostní bisimulace - Probabilistic bisimulation

v teoretická informatika, pravděpodobnostní bisimulace je rozšířením pojmu bisimulace plně pravděpodobnostní přechodové systémy poprvé popsal KG. Larsen a A. Skou.^[1]

Diskrétní pravděpodobnostní přechodový systém je trojitý

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

kde ${ displaystyle tau (s, a, t)}$ dává pravděpodobnost spuštění ve stavu s, provedení akce A a skončit ve státě t. Množina stavů se předpokládá jako spočetná. Neexistuje žádný pokus o přiřazení pravděpodobností akcím. Předpokládá se, že akce jsou nedeterministicky vybírány protivníkem nebo prostředím. Tento typ systému je plně pravděpodobný, neexistuje žádná jiná neurčitost.

Definice pravděpodobnostní bisimulace v systému S je vztah ekvivalence R na stavovém prostoru St, takový pro každý pár s,t v St se sRt a pro každou akci v zákoně a pro každou třídu ekvivalence C z R ${ displaystyle tau (s, a, C) = tau (t, a, C).}$ O dvou státech se říká, že jsou pravděpodobnostně bisimilární, pokud takové existují R spojovat je.

Při aplikaci na Markovovy řetězy, pravděpodobnostní bisimulace je stejný koncept jako hrudkovatelnost.^[2]^[3]Pravděpodobnostní bisimulace se přirozeně rozšiřuje na váženou bisimulaci.^[4]

Reference

^ K. G. Larsen a A. Skou a objevili se v článku Bisimulace pomocí pravděpodobnostního testování, publikovaná v Information and Computation, sv. 94, strany 1-28, 1991
^ Pravděpodobnostní interference prostřednictvím slabé pravděpodobnostní bisimulace autor Geoffrey Smith Proceedings of the 16th IEEE Computer Security Foundations Workshop (CSFW’03) 1063-6900 / 03
^ Kemeny, John G.; Snell, J. Laurie (červenec 1976) [1960]. Gehring, F. W .; Halmos, P. R. (eds.). Konečné Markovovy řetězy (Druhé vydání.). New York Berlin Heidelberg Tokio: Springer-Verlag. p. 224. ISBN 978-0-387-90192-3.
^ Oliveira, J.N. (2013). „Vážené automaty jako coalgebry v kategoriích matic“. Int. J. Nalezeno. Comput. Sci. 24 (6): 709–728. doi:10.1142 / S0129054113400145.

[1] K. G. Larsen a A. Skou a objevili se v článku Bisimulace pomocí pravděpodobnostního testování, publikovaná v Information and Computation, sv. 94, strany 1-28, 1991

[2] Pravděpodobnostní interference prostřednictvím slabé pravděpodobnostní bisimulace autor Geoffrey Smith Proceedings of the 16th IEEE Computer Security Foundations Workshop (CSFW’03) 1063-6900 / 03

[3] Kemeny, John G.; Snell, J. Laurie (červenec 1976) [1960]. Gehring, F. W .; Halmos, P. R. (eds.). Konečné Markovovy řetězy (Druhé vydání.). New York Berlin Heidelberg Tokio: Springer-Verlag. p. 224. ISBN 978-0-387-90192-3.

[4] Oliveira, J.N. (2013). „Vážené automaty jako coalgebry v kategoriích matic“. Int. J. Nalezeno. Comput. Sci. 24 (6): 709–728. doi:10.1142 / S0129054113400145.

[1]

[2]

[3]

[4]