Wednesday 18 June 2025
Venue: LIX, École polytechnique
For planning purposes, please register your participation.
Speaker 1: (present) Noam Zeilberger, LIX
Title: Generalized context-free grammars over categories and operads
Abstract:
I will discuss some categorical perspectives on context-free grammars
developed in joint work with Paul-André Melliès. Under this
perspective, a generalized CFG may be represented by a functor from a
free colored operad (aka multicategory) generated by a pointed finite
species into an arbitrary base operad: this encompasses classical CFGs
by taking the base to be a certain operad constructed from a free
monoid, as an instance of a more general construction of an "operad of
spliced arrows" for any category. One benefit of this perspective is
that by taking different base operads we naturally recover some
well-known extensions of the context-free regime, such as so-called
"multiple" context free grammars. I will also briefly discuss some of
our ongoing work on giving categorical content to a more general
notion of formal language, which encompasses "context-free
multilanguages" in the sense of Knuth (1991).
Reference: The categorical contours of the Chomsky-Schützenberger representation theorem, LMCS 21:2, https://doi.org/10.46298/lmcs-21(2:12)2025
Speaker 2: (present) Benjamin Bisping, Technische Universität Berlin, Germany
Title: Deciding All Behavioral Equivalences at Once through Energy Games
Abstract:
Concurrency theory has come up with a spectrum of program equivalences (e.g. bisimilarity, trace equivalence, ready traces), which vary in granularity. My recent approach turns a whole family of equivalence problems into one quantitative problem of how equivalent two models are. The core idea is to generalize the bisimulation game into a multi-dimensional energy game, where the attacker has to tell processes apart using limited resources.
The talk presents the key thoughts of my PhD thesis "Generalized Equivalence Checking of Concurrent Programs", which connects conference publications from CAV'23, EXPRESS/SOS'24 (joint work with David N. Jansen), and CONCUR'25 (to appear, joint work with Caroline Lemke).