On Generative Parallel Composition

P.R. d' Argenio, H. Hermanns, Joost P. Katoen

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

    37 Citations (Scopus)
    35 Downloads (Pure)


    A major reason for studying probabilistic processes is to establish a link between a formal model for describing functional system behaviour and a stochastic process. Compositionality is an essential ingredient for specifying systems. Parallel composition in a probabilistic setting is complicated since it gives rise to non-determinism, for instance due to interleaving of independent autonomous activities. This paper presents a detailed study of the resolution of non-determinism in an asynchronous generative setting. Based on the intuition behind the synchronous probabilistic calculus PCCS we formulate two criteria that an asynchronous parallel composition should fulfill. We provide novel probabilistic variants of parallel composition for CCS and CSP and show that these operators satisfy these general criteria, opposed to most existing proposals. Probabilistic bisimulation is shown to be a congruence for these operators and their expansion is addressed. We would like to thank the reviewers for their constructive criticism and for pointing out the relation between BPTSs and the model of Pnueli and Zuck. We also thank Ed Brinksma and Rom Langerak (both of the University of Twente) for fruitful discussions.
    Original languageEnglish
    Title of host publicationPROBMIV'98
    Subtitle of host publicationFirst International Workshop on Probabilistic Methods in Verification
    EditorsChristel Baier, Michael Huth, Marta Kwiatkowska, Mark Ryan
    Place of PublicationAmsterdam
    Number of pages25
    Publication statusPublished - Jun 1999
    Event1st International Workshop on Probabilistic Methods in Verification, PROBMIV 1998 - Indianapolis, United States
    Duration: 19 Jun 199820 Jun 1998
    Conference number: 1

    Publication series

    NameElectronic Notes in Theoretical Computer Science
    ISSN (Print)1571-0661


    Workshop1st International Workshop on Probabilistic Methods in Verification, PROBMIV 1998
    Abbreviated titlePROBMIV
    CountryUnited States



    Fingerprint Dive into the research topics of 'On Generative Parallel Composition'. Together they form a unique fingerprint.

  • Cite this

    d' Argenio, P. R., Hermanns, H., & Katoen, J. P. (1999). On Generative Parallel Composition. In C. Baier, M. Huth, M. Kwiatkowska, & M. Ryan (Eds.), PROBMIV'98: First International Workshop on Probabilistic Methods in Verification (pp. 30-54). (Electronic Notes in Theoretical Computer Science; Vol. 22). Amsterdam: Elsevier. https://doi.org/10.1016/S1571-0661(05)80596-1