You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.
Tim Hosgood (Jun 27 2022 at 15:42):Noam Zeilberger: Parsing as a lifting problem and the Chomsky-Schützenberger representation theorem
Joint work with Paul-André Melliès.
In “Functors are Type Refinement Systems” [1], we argued for the idea that rather than being modelled merely as categories, type systems should be modelled as functors p : D → T from a category D whose morphisms are typing derivations to a category T whose morphisms are the terms corresponding to the underlying subjects of those derivations. One advantage of this fibrational point of view is that the notion of typing judgment receives a simple mathematical status, as a triple (R,f,S) consisting of two objects R, S in D and a morphism f in T such that p(R)=dom(f) and p(S)=cod(f). The question of finding a typing derivation for a typing judgment (R,f,S) then reduces to the lifting problem of finding a morphism α : R → S such that p(α)=f. We developed this perspective in a series of papers, and believe that it may be usefully applied to a large variety of deductive systems, beyond type systems in the traditional sense. In this work [2], we focus on derivability in context-free grammars, a classic topic in formal language theory with wide applications in computer science.
The talk will begin by explaining how derivations in any context-free grammar G may be naturally encoded by a functor of operads p : Free S → W[Σ] from a freely generated operad into a certain “operad of spliced words”. This motivates the introduction of a more general notion of context-free grammar over any category C, defined as a finite species S equipped with a color denoting the start symbol and a functor of operads p : Free S → W[C] into the operad of spliced arrows in C. We will see that many standard concepts and properties of context-free grammars and languages can be formulated within this framework, thereby admitting simpler analysis, and that parsing may indeed be profitably considered from a fibrational perspective, as a lifting problem along a functor from a freely generated operad.
The second half of the talk will be devoted to a new proof of the Chomsky-Schützenberger Representation Theorem. An important ingredient is the identification of a left adjoint C[−] : Operad → Cat to the operad of spliced arrows functor W[−] : Cat → Operad. This construction builds the contour category C[O] of any operad O, whose arrows have a geometric interpretation as “oriented contours” of operations. A direct consequence of the contour / splicing adjunction is that every finite species equipped with a color induces a universal context-free grammar, generating a language of tree contour words. Finally, we prove a generalization of the Chomsky-Schützenberger Representation Theorem, establishing that any context-free language of arrows over a category C is the functorial image of the intersection of a C-chromatic tree contour language and a regular language.
[1] P.-A. Melliès and N. Zeilberger, Functors are type refinement systems, POPL 2015
[2] P.-A. Melliès and N. Zeilberger, Parsing as a lifting problem and the Chomsky-Schützenberger representation theorem, to appear at MFPS 2022, preliminary version available at hal.archives-ouvertes.fr/hal-03702762
Zoom: https://topos-institute.zoom.us/j/84392523736?pwd=bjdVS09wZXVscjQ0QUhTdGhvZ3pUdz09
YouTube: https://www.youtube.com/watch?v=AX8tpQSi8v8