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

Tobias Kappé (Corresponding author), Paul Brunet, Bas Luttik (Corresponding author), Alexandra Silva, Fabio Zanasi

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

11 Citaten (Scopus)

Samenvatting

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.
Originele taal-2Engels
Pagina's (van-tot)130-153
Aantal pagina's24
TijdschriftJournal of Logic and Algebraic Programming
Volume103
DOI's
StatusGepubliceerd - feb. 2019

Citeer dit