BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Concurrent Kleene Algebras and Pomset Languages - Georg Struth\, U
 niversity of Sheffield
DTSTART:20170526T130000Z
DTEND:20170526T140000Z
UID:TALK71819@talks.cam.ac.uk
CONTACT:Dominic Mulligan
DESCRIPTION:A concurrent Kleene algebra (CKA) is essentially a Kleene\nalg
 ebra expanded by an operation and axioms for concurrent\ncomposition.  Pom
 sets form a standard model of true concurrency\; they\nhave recently attra
 cted some renewed attention in the area of weak\nmemory concurrency.  In t
 his lecture I outline some connections\nbetween pomset languages and CKA. 
  I characterise the free algebras in\nthe varieties generated by some subl
 anguages and present two\ncompleteness results for classes of pomset langu
 ages that generalise\nthe rational languages to the realm of concurrency. 
 More precisely I\nshow that the congruence on series-parallel rational pom
 set\nexpressions generated by series-parallel rational pomset language\nid
 entity is axiomatised by the axioms of Kleene algebra plus those of\ncommu
 tative Kleene algebra. A decision procedure is extracted from\nthis proof.
   A second\, more intricate completeness result relates\ndown-closed serie
 s-parallel rational pomset languages with the full\nset of CKA axioms.  A 
 decision procedure for the equational theory of\nCKA can be obtained from 
 this result (joint work with Michael\nLaurence).
LOCATION:FW26
END:VEVENT
END:VCALENDAR