Jeudi 20 novembre 2025, 14:00 à 15:00

salle de séminaire du département d'informatique

Noam Zeilberger

(LIX, Ecole polytechnique, Paris)

Over recent years, in joint work with Paul-André Melliès, we have developed some fibrational perspectives on context-free grammars and finite-state automata, under which a "generalized context-free grammar" is defined as a functor from a finitely generated free operad into an arbitrary base operad.  The classical case is recovered by taking the base to be a certain operad whose operations are "words with gaps". 

One benefit of this perspective is that it interacts well with an analogous notion of "generalized finite-state automaton", providing conceptual explanations for some of the properties of context-free and regular languages (including the closure of the former under intersection with the latter). Moreover, by taking different base operads, one naturally recovers some well-known extensions of the context-free regime including multiple context-free grammars.