Weak Bisimulation for Fully Probabilistic Processes

Christel Baier, Holger Hermanns

    Research output: Book/ReportReportProfessional

    100 Downloads (Pure)

    Abstract

    Bisimulations that abstract from internal computation have proven to be useful for verification of compositionally defined transition systems. In the literature of probabilistic extensions of such transition systems, similar bisimulations are rare. In this paper, we introduce weak and branching bisimulation for fully probabilistic systems, transition systems where nondeterministic branching is replaced by probabilistic branching. In contrast to the nondeterministic case, both relations coincide. We give an algorithm to decide weak (and branching) bisimulation with a time complexity cubic in the number of states of the fully probabilistic system. This meets the worst case complexity for deciding branching bisimulation in the nondeterministic case. In addition, the relation is shown to be a congruence with respect to the operators of PLSCCS, a lazy synchronous probabilistic variant of CCS. We illustrate that due to these properties, weak bisimulation provides all the crucial ingredients for mechanised compositional verification of probabilistic transition systems.
    Original languageEnglish
    Place of PublicationEnschede
    PublisherCentre for Telematics and Information Technology (CTIT)
    Number of pages61
    Publication statusPublished - 1999

    Publication series

    NameCTIT technical report series
    PublisherUniversity of Twente, CTIT
    No.99-12
    ISSN (Print)1381-3625

    Cite this