JetBrains Research unites scientists working in challenging new disciplines

Event Structures and True Concurrency Semantics for CCS

Traditional approach to model concurrency is operational interleaving semantics. In this approach the semantics of parallel processes is defined as an interleaving of their atomic actions. Interleaving semantics present an intuitive and straightforward way to model concurrency. Unfortunately, the reasoning in terms of interleavings is hard for both humans and computers. Besides that, interleaving semantics are not compositional. They cannot be used to define the meaning of the program in terms of its sub-programs.

True concurrency semantics propose an alternative solution. In this framework it is possible to explicitly define the causality relations between atomic actions and avoid the reasoning in terms of all possible interleavings.

In this talk we will consider event structures — one of the classic domains in the theory of true concurrency. We will show how event structures can be used to define denotational (compositional) semantics on the example of Calculus of Communicating Systems (CCS).

Speaker: Evgenii Moiseenko

References:

Winskel G. Event structure semantics for CCS and related languages //International Colloquium on Automata, Languages, and Programming. – Springer, Berlin, Heidelberg, 1982. – С. 561-576.

Winskel G. Event structures //Advanced Course on Petri Nets. – Springer, Berlin, Heidelberg, 1986. – С. 325-392.

The seminar will be held in google meet on Monday, December 14, at 17:30 (google meet room: https://meet.google.com/myu-dhmz-gvu)