School of Electronic Engineering and Computer Science

Seminar: Pomset languages and concurrent Kleene algebras

13 February 2018

Time: 1:00 - 2:00pm
Venue: QMUL campus, Informatics Teaching Laboratory (ITL), Top floor

Hosted by the Theoretical Computer Science research group

Speaker: Paul Brunet

Host: Nikos Tzevelekos


Concurrent Kleene algebras (CKA) and bi-Kleene algebras support equational reasoning about computing systems with concurrent behaviours. 

Their natural semantics is given by series(-parallel) rational pomset languages, a standard true concurrency semantics, which is often associated with processes of Petri nets.

In the first part of the talk, I will present a recent proof of completeness, showing that two series-rational expressions are equivalent according to the laws of CKA exactly when their pomset semantics are equal.

In a second part, I will use Petri nets to reduce the problem of containment of languages of pomsets to the equivalence of finite state automata. In doing so, we prove decidability as well as provide tight complexity bounds.

Joint work with Damien Pous, Georg Struth, Tobias KappĂ©, Alexandra Silva, and Fabio Zanasi

*Directions, if coming from outside QMUL*

Queen Mary is on Mile End Road, with nearest tube stations being Stepney Green (closest one to the seminars) and Mile End. The seminars are in the Informatics Teaching Laboratory, floor 2:

As the building has card access, it is best to inform us that you will be coming (