UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

Brzozowski Goes Concurrent-A Kleene Theorem for Pomset Languages

Kappe, T; Brunet, P; Luttik, B; Silva, A; Zanasi, F; (2017) Brzozowski Goes Concurrent-A Kleene Theorem for Pomset Languages. In: Meyer, R and Nestmann;, U, (eds.) Proceedings of the CONCUR 2017 : 28th International Conference on Concurrency Theory. (pp. 25:1-25:16). Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik: Dagstuhl, Germany. Green open access

[img]
Preview
Text
Kappe_main.pdf - Published version

Download (534kB) | Preview

Abstract

Concurrent Kleene Algebra (CKA) is a mathematical formalism to study programs that exhibit concurrent behaviour. As with previous extensions of Kleene Algebra, characterizing the free model is crucial in order to develop the foundations of the theory and potential applications. For CKA, this has been an open question for a few years and this paper makes an important step towards an answer. We present a new automaton model and a Kleene-like theorem that relates a relaxed version of CKA to series-parallel pomset languages, which are a natural candidate for the free model. There are two substantial differences with previous work: from expressions to automata, we use Brzozowski derivatives, which enable a direct construction of the automaton; from automata to expressions, we provide a syntactic characterization of the automata that denote valid CKA behaviours.

Type: Proceedings paper
Title: Brzozowski Goes Concurrent-A Kleene Theorem for Pomset Languages
Event: CONCUR 2017 : 28th International Conference on Concurrency Theory
Open access status: An open access version is available from UCL Discovery
DOI: 10.4230/LIPIcs.CONCUR.2017.25
Publisher version: http://doi.org/10.4230/LIPIcs.CONCUR.2017.25
Language: English
Additional information: Copyright © Tobias Kappé, Paul Brunet, Bas Luttik, Alexandra Silva and Fabio Zanasi; licensed under Creative Commons License CC-BY 28th International Conference on Concurrency Theory (CONCUR 2017).
Keywords: Kleene theorem, Series-rational expressions, Automata, Brzozowski derivatives, Concurrency, Pomsets
UCL classification: UCL > Provost and Vice Provost Offices
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Engineering Science Faculty Office
URI: https://discovery.ucl.ac.uk/id/eprint/1561446
Downloads since deposit
17Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item