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.
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 |
Archive Staff Only
 |
View Item |
