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:Graphical Conjunctive Queries - Pawel Sobocinski\,
University of Southampton
DTSTART;TZID=Europe/London:20180727T140000
DTEND;TZID=Europe/London:20180727T150000
UID:TALK103186AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/103186
DESCRIPTION:String diagrams are an intuitive and powerful nota
tion with several different applications in comput
er science and related disciplines. In order to ar
rive at an implementation of diagrammatic reasonin
g\, one needs a suitable data structure. In a LiCS
'16 paper with Bonchi\, Gadducci\, Kissinger and Z
anasi\, we identified this as hypergraphs-with-int
erfaces\, or---categorically speaking---discrete c
ospans of hypergraphs. This combinatorial presenta
tion has the core of diagrammatic reasoning (i.e.
the laws of symmetric monoidal categories) built i
n\, and is therefore useful especially for rewriti
ng\, which reduces to a standard form of graph rew
riting. In general\, connections between categoric
al structures and combinatorial structures are oft
en extremely useful.\n\nIn this talk I will argue
that there is one important actor missing from the
above story: logic. In recent work (arXiv:1804.07
626) with Bonchi and Seeber\, we identified a deep
connection with a foundational logical calculus f
rom database theory\, the Calculus of Conjunctive
Queries. Moreover\, we showed that the algebraic t
heory of cartesian bicategories (Carboni and Walte
rs) captures the notion of query inclusion. A clas
sical result by Chandra and Merlin states that que
ry inclusion is decidable: we derive this decidabi
lity result through a deep triangular relationship
between categorical structure (cartesian bicatego
ries)\, logic (conjunctive queries) and combinator
ics (hypergraphs-with-interfaces).
LOCATION:FW26
CONTACT:Victor Gomes
END:VEVENT
END:VCALENDAR