BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.bham.ac.uk//v3//EN
BEGIN:VEVENT
CATEGORIES:Theoretical computer science seminar
SUMMARY:Context-free grammars and finite-state automata ov
er categories - Noam Zeilberger (LIX)
DTSTART:20231201T110000Z
DTEND:20231201T115000Z
UID:TALK5353AT
URL:/talk/index/5353
DESCRIPTION:*Zoom details*\n\n* Link: https://bham-ac-uk.zoom.
us/j/81873335084?pwd=T1NaUFg2U1l6d0RLL2RlTzFBam1IU
T09\n* Meeting ID: 818 7333 5084\n* Passcode: 217\
n\n*Abstract*\n\nIn "Functors are Type Refinement
Systems" (Melliès & Z\, 2015)\, we advocated that
when viewing type theory through a categorical len
s\, type systems are best modelled as *functors* r
ather than as categories\, in order to properly ac
count for the distinction between terms\, typing j
udgments\, and typing derivations. This fibrationa
l\nperspective can also be applied to automata and
formal language theory\, and in the talk I will r
eport on insights we've gained in doing so over th
e last few years. From the starting point of mode
lling context-free grammars as certain functors of
multicategories\, we had a breakthrough when tryi
ng to understand the Chomsky-Schützenberger repres
entation theorem\, the classical statement of whic
h says that "any context-free language is a homomo
rphic image of the intersection of a Dyck language
with a regular language". Thinking about the theo
rem made us realize that the notions of context-fr
ee grammar and of non-deterministic finite state a
utomata may be naturally extended to define CFGs a
nd NDFAs over arbitrary categories\, and that the
theorem itself is intimately tied to an (apparentl
y previously unnoticed) adjunction between categor
ies and multicategories that is of independent int
erest.\n\nBased on joint work with Paul-André Mell
iès\, particularly a paper presented at MFPS 2022
(https://hal.science/hal-03702762) and a long vers
ion of that article near completion.
LOCATION:LG23\, Computer Science // Zoom
CONTACT:George Kaye
END:VEVENT
END:VCALENDAR