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

On series-parallel pomset languages: Rationality, context-freeness and automata

Kappe, T; Brunet, P; Luttik, B; Silva, A; Zanasi, F; (2019) On series-parallel pomset languages: Rationality, context-freeness and automata. Journal of Logical and Algebraic Methods in Programming , 103 pp. 130-153. 10.1016/j.jlamp.2018.12.001. Green open access

[thumbnail of Kappé_main.pdf]
Preview
Text
Kappé_main.pdf - Accepted Version

Download (464kB) | Preview

Abstract

Concurrent Kleene Algebra (CKA) is a formalism to study concurrent programs. Like previous Kleene Algebra extensions, developing a correspondence between denotational and operational perspectives is important, both for foundations and for applications. This paper takes an important step towards such a correspondence, by precisely relating bi-Kleene Algebra (BKA), a fragment of CKA, to a novel type of automata called pomset automata (PAs). We show that PAs can implement the BKA semantics of series-parallel rational expressions, and that a class of PAs can be translated back to these expressions. We also characterise the behaviour of general PAs in terms of context-free pomset grammars; consequently, universality, equivalence and series-parallel rationality of general PAs are undecidable.

Type: Article
Title: On series-parallel pomset languages: Rationality, context-freeness and automata
Open access status: An open access version is available from UCL Discovery
DOI: 10.1016/j.jlamp.2018.12.001
Publisher version: https://doi.org/10.1016/j.jlamp.2018.12.001
Language: English
Additional information: This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions.
Keywords: Concurrency, Series-Rational Expressions, Kleene Algebra, Pomsets, Pomset Automata, Brzozowski derivatives, Kleene theorem
UCL classification: UCL
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
URI: https://discovery.ucl.ac.uk/id/eprint/10063259
Downloads since deposit
75Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item