Weak Sequential Composition in Process Algebras

Arend Rensink; Heike Wehrheim

doi:10.1007/BFb0015012

Weak Sequential Composition in Process Algebras

Arend Rensink, Heike Wehrheim

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

16 Citations (Scopus)

59 Downloads (Pure)

Abstract

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 language	English
Title of host publication	CONCUR '94: Concurrency Theory
Subtitle of host publication	5th International Conference, Uppsala, Sweden, August 22–25, 1994, Proceedings
Editors	Bengt Jonsson, Joachim Parrow
Place of Publication	Berlin
Publisher	Springer
Pages	226-241
Number of pages	16
ISBN (Electronic)	978-3-540-48654-1
ISBN (Print)	978-3-540-58329-5
DOIs	https://doi.org/10.1007/BFb0015012
Publication status	Published - 1994
Event	5th International Conference on Concurrency Theory, CONCUR 1994 - Uppsala, Sweden Duration: 22 Aug 1994 → 25 Aug 1994 Conference number: 5

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	836
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	5th International Conference on Concurrency Theory, CONCUR 1994
Abbreviated title	CONCUR
Country/Territory	Sweden
City	Uppsala
Period	22/08/94 → 25/08/94

Access to Document

10.1007/BFb0015012

Rensink1994weakAccepted author version, 253 KB

Cite this

@inproceedings{6dcb53bd07e84bd090c736313fa31f48,

title = "Weak Sequential Composition in Process Algebras",

abstract = "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.",

author = "Arend Rensink and Heike Wehrheim",

year = "1994",

doi = "10.1007/BFb0015012",

language = "English",

isbn = "978-3-540-58329-5",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "226--241",

editor = "Bengt Jonsson and Joachim Parrow",

booktitle = "CONCUR '94: Concurrency Theory",

address = "Netherlands",

note = "5th International Conference on Concurrency Theory, CONCUR 1994, CONCUR ; Conference date: 22-08-1994 Through 25-08-1994",

}

Rensink, A & Wehrheim, H 1994, Weak Sequential Composition in Process Algebras. in B Jonsson & J Parrow (eds), CONCUR '94: Concurrency Theory: 5th International Conference, Uppsala, Sweden, August 22–25, 1994, Proceedings. Lecture Notes in Computer Science, vol. 836, Springer, Berlin, pp. 226-241, 5th International Conference on Concurrency Theory, CONCUR 1994, Uppsala, Sweden, 22/08/94. https://doi.org/10.1007/BFb0015012

Weak Sequential Composition in Process Algebras. / Rensink, Arend; Wehrheim, Heike.

CONCUR '94: Concurrency Theory: 5th International Conference, Uppsala, Sweden, August 22–25, 1994, Proceedings. ed. / Bengt Jonsson; Joachim Parrow. Berlin : Springer, 1994. p. 226-241 (Lecture Notes in Computer Science; Vol. 836).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Weak Sequential Composition in Process Algebras

AU - Rensink, Arend

AU - Wehrheim, Heike

N1 - Conference code: 5

PY - 1994

Y1 - 1994

N2 - 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.

AB - 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.

U2 - 10.1007/BFb0015012

DO - 10.1007/BFb0015012

M3 - Conference contribution

SN - 978-3-540-58329-5

T3 - Lecture Notes in Computer Science

SP - 226

EP - 241

BT - CONCUR '94: Concurrency Theory

A2 - Jonsson, Bengt

A2 - Parrow, Joachim

PB - Springer

CY - Berlin

T2 - 5th International Conference on Concurrency Theory, CONCUR 1994

Y2 - 22 August 1994 through 25 August 1994

ER -

Weak Sequential Composition in Process Algebras

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this