BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Logic and Semantics Seminar (Computer Laboratory)
SUMMARY:Concurrent Kleene Algebras and Pomset Languages -
Georg Struth\, University of Sheffield
DTSTART;TZID=Europe/London:20170526T140000
DTEND;TZID=Europe/London:20170526T150000
UID:TALK71819AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/71819
DESCRIPTION:A concurrent Kleene algebra (CKA) is essentially a
Kleene\nalgebra expanded by an operation and axio
ms for concurrent\ncomposition. Pomsets form a st
andard model of true concurrency\; they\nhave rece
ntly attracted some renewed attention in the area
of weak\nmemory concurrency. In this lecture I ou
tline some connections\nbetween pomset languages a
nd CKA. I characterise the free algebras in\nthe
varieties generated by some sublanguages and prese
nt two\ncompleteness results for classes of pomset
languages that generalise\nthe rational languages
to the realm of concurrency. More precisely I\nsh
ow that the congruence on series-parallel rational
pomset\nexpressions generated by series-parallel
rational pomset language\nidentity is axiomatised
by the axioms of Kleene algebra plus those of\ncom
mutative Kleene algebra. A decision procedure is e
xtracted from\nthis proof. A second\, more intric
ate 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 th
is result (joint work with Michael\nLaurence).
LOCATION:FW26
CONTACT:Dominic Mulligan
END:VEVENT
END:VCALENDAR