On compositionality, efficiency, and applicability of abstraction in probabilistic systems

S. Andova, S. Georgievska

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

4 Citations (Scopus)

Abstract

A branching bisimulation for probabilistic systems that is preserved under parallel composition has been defined recently for the alternating model. We show that besides being compositional, it is decidable in polynomial time and it preserves the properties expressible in probabilistic Computation Tree Logic (pCTL). In the ground-complete axiomatization, only a single axiom is added to the axioms for strong bisimulation. We show that the Concurrent Alternating Bit protocol can be verified using the process algebra and a set of recursive rules.
Original languageEnglish
Title of host publicationSOFSEM 2009 : Theory and Practice of Computer Science (35th Conference, Spindleruv Mlyn, Czech Republic, January 24-30, 2009, Proceedings)
EditorsM. Nielsen, A. Kucera, P.B. Miltersen, C. Palamidessi, P. Tuma, F. Valencia
Place of PublicationBerlin
PublisherSpringer
Pages67-78
ISBN (Print)978-3-540-95890-1
DOIs
Publication statusPublished - 2009

Publication series

NameLecture Notes in Computer Science
Volume5404
ISSN (Print)0302-9743

Fingerprint Dive into the research topics of 'On compositionality, efficiency, and applicability of abstraction in probabilistic systems'. Together they form a unique fingerprint.

Cite this