Journal
JOURNAL OF LOGICAL AND ALGEBRAIC METHODS IN PROGRAMMING
Volume 103, Issue -, Pages 130-153Publisher
ELSEVIER SCIENCE INC
DOI: 10.1016/j.jlamp.2018.12.001
Keywords
Concurrency; Series-rational expressions; Kleene algebra; Pomset automata; Brzozowski derivatives; Kleene theorem
Categories
Funding
- ERC Starting Grant ProFoundNet [679127]
- EPSRC [EP/R020604/1]
- EPSRC [EP/R006865/1, EP/R020604/1] Funding Source: UKRI
- European Research Council (ERC) [679127] Funding Source: European Research Council (ERC)
Ask authors/readers for more resources
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. (C) 2018 Elsevier Inc. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available