Principles of Programming Seminar

— 5:00pm

Location:
In Person and Virtual - ET - Gates Hillman 8102

Speaker:
NOAM ZEILBERGER, Assistant Professor in Computer Science, Laboratoire d'informatique de l'École Polytechnique
http://noamz.org/

Parsing as a Lifting Problem and the Chomsky-Schützenberger Representation Theorem

I will discuss recent joint work with Paul-André Melliès,[*] where we develop a fibrational perspective on context-free grammars, and a generalization of the classical notion of CFG to define context-free languages of arrows in any category.  Our starting point is the construction of a functor W[-] : Cat -> Operad that builds an "operad of spliced arrows" W[C] from any category C.  We show that many standard concepts about context-free grammars may be reformulated in this framework, thereby admitting simpler analysis, and that context-free languages of arrows satisfy natural generalizations of the usual closure properties.  Our main result is a new proof of (a refinement and generalization of) the Chomsky-Schützenberger Representation Theorem, whose classical formulation states that any context-free language is the homomorphic image of the intersection of a Dyck language with a regular language.  The proof relies on two constructions of more general interest: 1. the pullback of a CFG of arrows along an NDFA, defining a CFG of runs of an automaton, and 2. the "contour category" of an operad, which provides a left adjoint C[-] : Operad -> Cat to the operad of spliced arrows functor. —

I am an assistant professor at LIX and a member of the PARTOUT team within the Proofs and Algorithms pole. Previously, I was a Birmingham Fellow at the University of Birmingham for three years, and a member of the vibrant Theory Group in the School of Computer Science. I moved back to France in 2020 to rejoin my wife, after a few years of tricky navigation between Birmingham and Paris. Before that, I was an itinerant postdoc for around seven years, first in Paris at Laboratoire PPS (now IRIF) with a fellowship of the Fondation Sciences Mathématiques de Paris, then at IMDEA Software in Madrid, then at the Institute for Advanced Study in Princeton during the special year on Univalent Foundations, and then back to Paris at the MSR-Inria Joint Centre and as a member of Team Parsifal. And before all that I was a PhD student at CMU SCS, spending six great years in Pittsburgh, Pennsylvania. [*] Parsing as a lifting problem and the Chomsky-Schützenberger representation theorem. Presented at MFPS 2022. Preliminary version available.

Faculty Host:  Robert Harper In Person and Zoom Participation. See announcement.

Event Website:
https://www.cs.cmu.edu/Groups/pop/seminar.html

For More Information:
ahornick@andrew.cmu.edu