Weak Sequential Composition in Process Algebras

Arend Rensink, Heike Wehrheim

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

    16 Citations (Scopus)
    59 Downloads (Pure)


    In this paper we study a special operator for sequential composition, which is defined relative to a dependency relation over the actions of a given system. The idea is that actions which are not dependent (intuitively because they share no common resources) do not have to wait for one another to proceed, even if they are composed sequentially. Such a notion has been studied before in a linear-time setting, but until recently there has been no systematic investigation in the context of process algebras.We give a structural operational semantics for a process algebraic language containing such a sequential composition operator, which shows some interesting interplay with choice. We give a complete axiomatisation of strong bisimilarity and we show consistency of the operational semantics with an event-based denotational semantics developed recently by the second author. The axiom system allows to derive the communication closed layers law, which in the linear time setting has been shown to be a very useful instrument in correctness preserving transformations. We conclude with a couple of examples.
    Original languageEnglish
    Title of host publicationCONCUR '94: Concurrency Theory
    Subtitle of host publication5th International Conference, Uppsala, Sweden, August 22–25, 1994, Proceedings
    EditorsBengt Jonsson, Joachim Parrow
    Place of PublicationBerlin
    Number of pages16
    ISBN (Electronic)978-3-540-48654-1
    ISBN (Print)978-3-540-58329-5
    Publication statusPublished - 1994
    Event5th International Conference on Concurrency Theory, CONCUR 1994 - Uppsala, Sweden
    Duration: 22 Aug 199425 Aug 1994
    Conference number: 5

    Publication series

    NameLecture Notes in Computer Science
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349


    Conference5th International Conference on Concurrency Theory, CONCUR 1994
    Abbreviated titleCONCUR


    Dive into the research topics of 'Weak Sequential Composition in Process Algebras'. Together they form a unique fingerprint.

    Cite this