Paul-André Melliès ; Noam Zeilberger - Parsing as a lifting problem and the Chomsky-Schützenberger representation theorem

entics:10508 - Electronic Notes in Theoretical Informatics and Computer Science, February 22, 2023, Volume 1 - Proceedings of MFPS XXXVIII - https://doi.org/10.46298/entics.10508
Parsing as a lifting problem and the Chomsky-Schützenberger representation theoremArticle

Authors: Paul-André Melliès ORCID; Noam Zeilberger

    We begin by explaining how any context-free grammar encodes a functor of operads from a freely generated operad into a certain "operad of spliced words". This motivates a more general notion of CFG 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] \to W[C]$ into the operad of spliced arrows in $C$. We show that many standard properties of CFGs can be formulated within this framework, and that usual closure properties of CF languages generalize to CF languages of arrows. We also discuss a dual fibrational perspective on the functor $p$ via the notion of "displayed" operad, corresponding to a lax functor of operads $W[C] \to Span(Set)$. We then turn to the Chomsky-Schützenberger Representation Theorem. We describe how a non-deterministic finite state automaton can be seen as a category $Q$ equipped with a pair of objects denoting initial and accepting states and a functor of categories $Q \to C$ satisfying the unique lifting of factorizations property and the finite fiber property. Then, we explain how to extend this notion of automaton to functors of operads, which generalize tree automata, allowing us to lift an automaton over a category to an automaton over its operad of spliced arrows. We show that every CFG over a category can be pulled back along a ND finite state automaton over the same category, and hence that CF languages are closed under intersection with regular languages. The last important ingredient is the identification of a left adjoint $C[-] : Operad \to Cat$ to the operad of spliced arrows functor, building the "contour category" of an operad. Using this, we generalize the C-S representation theorem, proving 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.


    Volume: Volume 1 - Proceedings of MFPS XXXVIII
    Published on: February 22, 2023
    Accepted on: December 20, 2022
    Submitted on: December 20, 2022
    Keywords: Mathematics - Category Theory,Computer Science - Formal Languages and Automata Theory
    Funding:
      Source : OpenAIRE Graph
    • Reasoning with Circular proofs for Programming; Funder: French National Research Agency (ANR); Code: ANR-21-CE48-0019
    • a cartographic quest between lambda-calculus, logic, and combinatorics; Funder: French National Research Agency (ANR); Code: ANR-21-CE48-0017

    Consultation statistics

    This page has been seen 882 times.
    This article's PDF has been downloaded 149 times.