%0 Generic %1 kappe2018seriesparallel %A Kappé, Tobias %A Brunet, Paul %A Luttik, Bas %A Silva, Alexandra %A Zanasi, Fabio %D 2018 %K cs %R 10.1016/j.jlamp.2018.12.001 %T On Series-Parallel Pomset Languages: Rationality, Context-Freeness and Automata %U http://arxiv.org/abs/1812.03058 %X 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, for both foundations and 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, 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 behavior of general PAs in terms of context-free pomset grammars; consequently, universality, equivalence and series-parallel rationality of general PAs are undecidable.

@misc{kappe2018seriesparallel, 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, for both foundations and 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, 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 behavior of general PAs in terms of context-free pomset grammars; consequently, universality, equivalence and series-parallel rationality of general PAs are undecidable.}, added-at = {2018-12-30T17:24:33.000+0100}, author = {Kappé, Tobias and Brunet, Paul and Luttik, Bas and Silva, Alexandra and Zanasi, Fabio}, biburl = {https://www.bibsonomy.org/bibtex/2b3acbf1cb5e6f480981d85f01265cb73/chazu}, description = {[1812.03058] On Series-Parallel Pomset Languages: Rationality, Context-Freeness and Automata}, doi = {10.1016/j.jlamp.2018.12.001}, interhash = {24d9ed79e4927d2d95fc407390fc0bac}, intrahash = {b3acbf1cb5e6f480981d85f01265cb73}, keywords = {cs}, note = {cite arxiv:1812.03058Comment: Accepted manuscript}, timestamp = {2018-12-30T17:24:33.000+0100}, title = {On Series-Parallel Pomset Languages: Rationality, Context-Freeness and Automata}, url = {http://arxiv.org/abs/1812.03058}, year = 2018 }