Concurrent Kleene Algebra (CKA) is a formalism to study programs that exhibit concurrent behaviour. As with previous extensions of Kleene Algebra, an important tool to develop foundations and potential applications is a one-to- one correspondence between denotational and operational perspectives. This paper takes an important step towards such a correspondence, by precisely relating Bi-Kleene Algebra (BKA), a relaxed version of CKA, to a novel type of automata called pomset automata. We show that pomset automata can faithfully represent the BKA-semantics of series-parallel rational expressions, and that a (structurally restricted) class of pomset automata can be translated back to these expressions. Furthermore, we characterise the behavior of unrestricted automata in terms of context-free pomset grammars, thus yielding strong undecidability results.
@article{kbslz19,
title = "On Series-Parallel Pomset Languages: Rationality, Context-Freeness and Automata",
author = "{Paul Brunet}, {Tobias Kappé}, {Alexandra Silva}, {Bas Luttik}, {Fabio Zanasi}",
year = 2019,
journal = "JLAMP",
doi = "10.1016/j.jlamp.2018.12.001"
}
