Noam Zeilberger (École Polytechnique), Parsing as a lifting problem and the Chomsky-Schützenberger representation theorem
Programme
- 15 juin 2023, 10:30 - 12:00
Résumé
The classical statement of the Chomsky-Schützenberger representation theorem says that any context-free language may be represented as the homomorphic image of the intersection of a Dyck language of balanced parentheses with a regular language. In the talk I will discuss a fibrational perspective on context-free grammars and finite-state automata that grew out of a long-running project with Paul-André Melliès on type refinement systems, but with a surprising twist that only emerged when we considered the C-S theorem. It turns out that underlying that theorem is a basic adjunction between categories and colored operads (= multicategories), where the right adjoint $W : Cat \to Oper$ builds a "spliced arrow operad" out of any category, and the left adjoint $C : Oper \to \Cat$ sends any operad to a "contour category" whose arrows have a geometric interpretation as oriented contours of operations.
Based on joint work with Paul-André Melliès that appeared at MFPS 2022 https://hal.science/hal-03702762, as well as a long version of that article in preparation.