COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

University of Cambridge > Talks.cam > Logic and Semantics Seminar (Computer Laboratory) > Concurrent Kleene Algebras and Pomset Languages

## Concurrent Kleene Algebras and Pomset LanguagesAdd to your list(s) Download to your calendar using vCal - Georg Struth, University of Sheffield
- Friday 26 May 2017, 14:00-15:00
- FW26.
If you have a question about this talk, please contact Dominic Mulligan. A concurrent Kleene algebra (CKA) is essentially a Kleene algebra expanded by an operation and axioms for concurrent composition. Pomsets form a standard model of true concurrency; they have recently attracted some renewed attention in the area of weak memory concurrency. In this lecture I outline some connections between pomset languages and CKA . I characterise the free algebras in the varieties generated by some sublanguages and present two completeness results for classes of pomset languages that generalise the rational languages to the realm of concurrency. More precisely I show that the congruence on series-parallel rational pomset expressions generated by series-parallel rational pomset language identity is axiomatised by the axioms of Kleene algebra plus those of commutative Kleene algebra. A decision procedure is extracted from this proof. A second, more intricate completeness result relates down-closed series-parallel rational pomset languages with the full set of CKA axioms. A decision procedure for the equational theory of CKA can be obtained from this result (joint work with Michael Laurence). This talk is part of the Logic and Semantics Seminar (Computer Laboratory) series. ## This talk is included in these lists:- All Talks (aka the CURE list)
- Cambridge talks
- Computer Laboratory talks
- Computing and Mathematics
- FW26
- Interested Talks
- Logic and Semantics Seminar (Computer Laboratory)
- School of Technology
- Trust & Technology Initiative - interesting events
- bld31
- yk373's list
Note that ex-directory lists are not shown. |
## Other listsCambridge Haematopoiesis Seminars Special DPMMS Colloquium Meeting the Challenge of Healthy Ageing in the 21st Century## Other talksInternational Women's Day Lecture 2018: Press for Progress by Being an Active Bystander Downstream dispersion of bedload tracers The Warsaw Uprising in Polish Popular Culture after 1989 Flow Cytometry |