# The categorical contours of the Chomsky-Schützenberger representation theorem

Paul-André Melliès, Noam Zeilberger

► To cite this version:

Paul-André Melliès, Noam Zeilberger. The categorical contours of the Chomsky-Schützenberger representation theorem. Logical Methods in Computer Science, 2025, Volume 21, Issue 2, 10.46298/lmcs-21(2:12)2025 . hal-04399404v2

HAL Id: hal-04399404

https://hal.science/hal-04399404v2

Submitted on 22 May 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# THE CATEGORICAL CONTOURS OF THE CHOMSKY-SCHÜTZENBERGER REPRESENTATION THEOREM

PAUL-ANDRÉ MELLIÈS AND NOAM ZEILBERGER

a IRIF, Université Paris Cité, CNRS, Inria, Paris, France
*e-mail address*: paul-andre.mellies@cnrs.fr

b LIX, École Polytechnique, Inria, Palaiseau, France
*e-mail address*: noam.zeilberger@polytechnique.edu

**ABSTRACT.** We develop fibrational perspectives on context-free grammars and on non-deterministic finite-state automata over categories and operads. A generalized CFG is a functor from a free colored operad (aka multicategory) generated by a pointed finite species into an arbitrary base operad: this encompasses classical CFGs by taking the base to be a certain operad constructed from a free monoid, as an instance of a more general construction of an *operad of spliced arrows* WC for any category C. A generalized NFA is a functor from an arbitrary bipointed category or pointed operad satisfying the unique lifting of factorizations and finite fiber properties: this encompasses classical word automata and tree automata without $\epsilon$-transitions, but also automata over non-free categories and operads. We show that generalized context-free and regular languages satisfy suitable generalizations of many of the usual closure properties, and in particular we give a simple conceptual proof that context-free languages are closed under intersection with regular languages. Finally, we observe that the splicing functor $W: \mathrm{Cat} \to \mathrm{Oper}$ admits a left adjoint $C: \mathrm{Oper} \to \mathrm{Cat}$, which we call the *contour category* construction since the arrows of $CO$ have a geometric interpretation as oriented contours of operations of $O$. A direct consequence of the contour / splicing adjunction is that every pointed finite species induces a universal CFG generating a language of *tree contour words*. This leads us to a generalization of the Chomsky-Schützenberger Representation Theorem, establishing that a subset of a homset $L \subseteq C(A, B)$ is a CFL of arrows if and only if it is a functorial image of the intersection of a C-chromatic tree contour language with a regular language.

## INTRODUCTION

In “Functors are Type Refinement Systems” [MZ15], we argued for the idea that rather than being modelled merely as categories, type systems should be modelled as functors $p: \mathcal{D} \to \mathcal{T}$ from a category $\mathcal{D}$ whose morphisms may be considered as abstract typing derivations to a category $\mathcal{T}$ whose morphisms are the terms corresponding to the underlying *subjects* of

*Key words and phrases:* category theory, operads, context-free grammars and context-free languages, finite-state automata and regular languages, tree contour words, representation theorem.

This is a thoroughly revised and expanded version of a paper with a similar title [MZ22] presented at MFPS 2022. The authors are partially supported by ANR projects CoREACT (ANR-22-CE48-0015), LambdaComb (ANR-21-CE48-0017), and ReciProg (ANR-21-CE48-0019).

<figure><img src="image_2.png" /></figure>
those derivations. One consequence 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 $\mathcal{D}$ and a morphism $f$ in $\mathcal{T}$ such that $p(R) = \text{dom}(f)$ and $p(S) = \text{cod}(f)$. The question of finding a derivation for such a judgment then reduces to the “lifting problem” of finding a morphism $\alpha : R \to S$ such that $p(\alpha) = f$. Note that this problem could in general have zero, one, or more solutions.

We developed this perspective in a series of papers [MZ13, MZ15, MZ16, MZ18], 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, we focus on derivability in context-free grammars and on recognition by nondeterministic finite-state automata – two classic topics in formal language theory with wide applications in computer science. Although grammars and automata are of a very different nature, both may be naturally described as certain kinds of functors.

Free operads<fnref n="1" /> play an important role in our treatment of context-free grammars. Indeed, we will ultimately propose that a “generalized CFG” may be defined simply as a functor *from a free operad generated by a pointed finite species* into an arbitrary base operad. In order to recover the classical definition of CFG, we rely on a construction $\mathcal{W}: \text{Cat} \to \text{Oper}$ turning any category $\mathcal{C}$ into an operad $\mathcal{W}\mathcal{C}$, which we call its *operad of spliced arrows*. One recovers the classical definition by taking $\mathcal{C} = \mathcal{F}\mathbb{B}_{\Sigma}$ to be the one-object category freely generated from the one-node “bouquet” graph with a loop $a : * \to *$ for every letter of the alphabet $a \in \Sigma$. However, as we will see, it is very natural to consider context-free languages of arrows in an arbitrary category, or even generalized context-free languages of constants in an arbitrary operad.

Nondeterministic finite-state automata, it turns out, may be naturally modelled as functors satisfying the unique lifting of factorizations and finite fiber properties. One nice aspect of this formulation is that it captures both word automata and tree automata, which correspond to functors satisfying these two properties into free categories and into free operads respectively. However, again we will see that it is very natural and at times essential to work with a more general definition of NFA over a non-free category or operad.

A benefit of expressing both context-free grammars and nondeterministic finite-state automata as functors is that they are placed within a common framework, which facilitates comparison and combination. The germ of this paper was planted early on in the wake of our type refinement systems work, in 2017, when we began considering context-free grammars as functors of multicategories. But ultimately it was only in 2022 that the key mathematical definitions emerged very quickly (over the span of a couple weeks), when we mused that it could be interesting to analyze the Chomsky-Schützenberger Representation Theorem, a classic result in formal language theory that in its now-standard formulation states that a language is context-free if and only if it is a homomorphic image of the intersection of a Dyck language of well-bracketed words with a regular language. One reason the theorem is interesting is that it invokes a non-trivial closure property of context-free languages, namely closure under intersection with regular languages. Another reason is that it suggests, intuitively, that Dyck languages are in some sense “universal” context-free languages.

We will see that both of these aspects of the theorem have good categorical explanations. First, the intersection of a context-free language with a regular language may be computed by

<footnote n="1">¹In this paper, when we say “operad” we always mean *colored operad*, in the sense that our operads always carry a (potentially trivial) set of colors and operations are sorted $f : A_1, \dots, A_n \to B$ in addition to having an arity *n*. An operad in this sense is also called a *multicategory*, and we use the two words interchangeably.</footnote>
first taking the *pullback* of the functor representing the corresponding context-free grammar along the corresponding nondeterministic finite-state automaton, which for non-trivial but elementary reasons defines a context-free grammar over the *runs* of the automaton. Second, the aforementioned “spliced arrows” construction $\mathcal{W}$ extends to an *adjunction* between the category of categories and the category of operads,

<figure><img src="image_3.png" /></figure>

where the left adjoint builds what we call the “contour category” $CO$ of an operad $O$. This contour / splicing adjunction, which seems to be of independent interest, has as an immediate consequence that every pointed finite species induces a universal CFG generating a language of *tree contour words*. Such contour words are closely related to Dyck words, and allow us to prove a generalization of the representation theorem for context-free languages of arrows in an arbitrary category.

The rest of the paper is organized as follows. Section 1 is devoted to context-free grammars, Section 2 to nondeterministic finite-state automata, and Section 3 to the representation theorem. We discuss related work at the end of each of these sections, and we conclude in Section 4.

# 1. CONTEXT-FREE LANGUAGES OF ARROWS IN A CATEGORY

In this section, after some preliminaries on free operads and species, we describe the operad of spliced arrows construction, explain how to use it to define context-free grammars over arbitrary categories generating *context-free languages of arrows*, and show that many standard properties of CFGs and CFLs may be naturally reformulated in this general setting. We also spend some time developing the fibrational view of parsing as a lifting problem, explaining how any functor from a free operad $FS \to O$ may be represented as a “displayed free operad” corresponding to a lax functor $O \to \text{Span}(\text{Set})$ that admits a certain inductive definition. Finally, we describe how the definition of categorical CFG admits a further natural generalization by allowing the base operad to be arbitrary, and show that this encompasses several extensions of the notion of context-free grammar from the literature.

## 1.1. Preliminaries on free operads and species.
We assume some basic familiarity with operads, otherwise known as multicategories, as introduced for example in Chapter 2 of Leinster's book [Lei04]. We write $f \circ (g_1, \dots, g_n)$ for parallel composition of operations, and $f \circ_i g$ for partial composition after the first $i$ inputs (so $f \circ_0 g$ denotes composition of $g$ into the 0th input of $f$). Here we recall the notion of a (colored non-symmetric) species, and how one gives rise to a free operad.

**Definition 1.1.** A *colored non-symmetric species*, which we abbreviate to **species** for short, is a tuple $S = (C, V, i, o)$ consisting of a span of sets $C^* \leftarrow^i V \rightarrow^o C$ with the following interpretation: $C$ is a set of *colors*, $V$ is a set of *nodes*, and $i: V \rightarrow C^*$ and $o: V \rightarrow C$ return respectively the list of input colors and the unique output color of each node.

Species in this sense could also be called “signatures”, and are sometimes called “multigraphs” [Lam89, Wal89] since they bear the same relationship to multicategories as graphs do to categories (though that terminology has an unfortunate clash with a different concept in
graph theory); we use “species” to emphasize the link with Joyal’s theory of (symmetric) species [Joy81] and with generalized species [FGHW08]. Adopting the same notation as we use for operations of an operad, we write $x : R_1, \dots, R_n \to R$ to indicate that $x \in V$ is a node with list of input colors $i(x) = (R_1, \dots, R_n)$ and output color $o(x) = R$. However, it should be emphasized that a species by itself only contains bare coloring information about the nodes, and does not say how to compose them as operations. We will be primarily interested in finite species.

**Definition 1.2.** We say that a species is **finite** (also called *polynomial* [Joy86]) just in case both sets $C$ and $V$ are finite.

A map of species $\phi : \mathbb{S} \to \mathbb{T}$ from $\mathbb{S} = (C, V, i, o)$ to $\mathbb{T} = (D, W, i', o')$ is given by a pair $\phi = (\phi_C, \phi_V)$ of functions $\phi_C : C \to D$ and $\phi_V : V \to W$ making the diagram commute:

<figure><img src="image_4.png" /></figure>

Equivalently, writing $\phi$ for both $\phi_C$ and $\phi_V$, every node $x : R_1, \dots, R_n \to R$ of $\mathbb{S}$ must be sent to a node $\phi(x) : \phi(R_1), \dots, \phi(R_n) \to \phi(R)$ of $\mathbb{T}$. Just as every category has an underlying graph, every operad $\mathcal{O}$ has an underlying species with the same colors and whose nodes are the operations of $\mathcal{O}$, and this extends to a forgetful functor $\mathbb{U} : \text{Oper} \to \text{Spec}$ from the category of operads and functors of operads to the category of species and maps of species. Moreover, this forgetful functor has a left adjoint

<figure><img src="image_5.png" /></figure>

which sends any species $\mathbb{S}$ to a free operad with the same set of colors and whose operations are generated from the nodes of $\mathbb{S}$, analogous to the free category over a graph. By the universal property of the adjoint pair, there is a natural isomorphism of homsets

$$ \mathrm{Oper}(\mathbb{FS}, \mathcal{O}) \cong \mathrm{Spec}(\mathbb{S}, \mathbb{U}\mathcal{O}) $$

placing functors of operads $p : \mathbb{FS} \to \mathcal{O}$ and maps of species $\phi : \mathbb{S} \to \mathbb{U}\mathcal{O}$ in one-to-one correspondence. In the sequel, we will leave the action of the forgetful functor implicit, writing $\mathcal{O}$ for both an operad and its underlying species $\mathbb{U}\mathcal{O}$.

## 1.2. The operad of spliced arrows of a category.

**Definition 1.3.** Let $\mathcal{C}$ be a category. The operad $\mathcal{W}\mathcal{C}$ of spliced arrows in $\mathcal{C}$ is defined as follows:

* its colors are pairs $(A, B)$ of objects of $\mathcal{C}$;

* its $n$-ary operations $(A_1, B_1), \dots, (A_n, B_n) \to (A, B)$ consist of sequences $w_0-w_1-\dots-w_n$ of $n+1$ arrows in $\mathcal{C}$ separated by $n$ gaps denoted by “-”s, where each arrow must have type $w_i : B_i \to A_{i+1}$ for $0 \le i \le n$, under the convention that $B_0 = A$ and $A_{n+1} = B$;

* composition of spliced arrows is performed by “splicing into the gaps”: formally, the partial composition $f \circ_i g$ of a spliced arrow $g = u_0-\dots-u_m$ into another spliced arrow $f = w_0-\dots-w_n$ is defined by substituting $g$ for the $i$th occurrence of $-$ in $f$ (starting from the left using 0-indexing) and interpreting juxtaposition by sequential composition in $\mathcal{C}$ (see Fig. 1 for an illustration);
<figure><img src="image_6.png" /><figcaption>Figure 1: Left: a constant of $WC$. Middle: an identity operation. Right: example of partial composition, plugging $g = u_0-u_1-u_2 : (C_1, D_1), (C_2, D_2) \to (A_2, B_2)$ into gap 1 of $f = w_0-w_1-w_2-w_3 : (A_1, B_1), (A_2, B_2), (A_3, B_3) \to (A, B)$ to obtain $f \circ_1 g = w_0-w_1u_0-u_1-u_2w_2-w_3 : (A_1, B_1), (C_1, D_1), (C_2, D_2), (A_3, B_3) \to (A, B)$.</figcaption></figure>

• the identity operation on $(A, B)$ is given by $id_A-id_B$.

It is routine to check that $WC$ satisfies the associativity and neutrality axioms of an operad, these reducing to associativity and neutrality of composition of arrows in $C$. Indeed, the spliced arrows operad construction defines a functor $W: \text{Cat} \to \text{Oper}$ since any functor of categories $F: C \to D$ induces a functor of operads $WF: WC \to WD$, acting on colors by $(A, B) \mapsto (FA, FB)$ and on operations by $w_0-\dots-w_n \mapsto Fw_0-\dots-Fw_n$.

**Example 1.4.** As referenced in the Introduction, for any alphabet $\Sigma$ there is a one-object category $\mathcal{F}\mathbb{B}_{\Sigma}$, freely generated from the bouquet graph with a loop $a : * \to *$ for every letter of $a \in \Sigma$, so that words $w \in \Sigma^*$ may be regarded as arrows $w : * \to *$ in $\mathcal{F}\mathbb{B}_{\Sigma}$. In this case, the construction yields an operad $W\Sigma := W\mathcal{F}\mathbb{B}_{\Sigma}$ that we like to call the **operad of spliced words** in $\Sigma$. It has a single color, and its $n$-ary operations are sequences $w_0-\dots-w_n$ of $n+1$ words over $\Sigma$. For example, in the operad of spliced words over the ASCII alphabet, we have that `"Hell"-`, `"-"rld!"` $\circ$ `("o", "Wo") = "Hello, World!"$.

**Remark 1.5.** Although $\mathcal{F}\mathbb{B}_{\Sigma}$ is a free category, this property of being freely generated does not extend to its operad of spliced words. Indeed, an operad of spliced arrows $WC$ is almost never a free operad. That is because any pair of objects $A$ and $B$ induces a binary operation $id_A-id_A-id_B : (A, A), (A, B) \to (A, B)$, and any arrow $w : A \to B$ of $C$ induces a corresponding constant $w : (A, B)$. Since $id_A-id_A-id_B \circ (id_A, w) = w$, $WC$ cannot be a free operad except in the trivial case where $C$ has no objects and no arrows.

**Example 1.6.** Arrows in free categories with more than one object may be seen as “typed” words, in the sense that concatenation (= composition) is only a partial operation that combines a word $u : A \to B$ with a word of compatible type $v : B \to C$ to produce a word $uv : A \to C$. For example, consider the graph

$$ \mathbb{B}_{\Sigma}^{\mathbb{S}} := \underset{\perp}{\otimes} \xrightarrow{a \in \Sigma} \underset{\perp}{\otimes} \xleftarrow{*} \underset{\perp}{\otimes} \xrightarrow{\mathbb{S}} \underset{\perp}{\otimes} $$

obtained by extending the bouquet graph $\mathbb{B}_{\Sigma}$ into a “cylinder”. Arrows $w : * \to *$ of $\mathcal{F}\mathbb{B}_{\Sigma}^{\mathbb{S}}$ correspond to ordinary words, which may be concatenated freely, but arrows $u : \perp \to *$
<figure><img src="image_7.png" /><figcaption>Figure 2: Example of a context-free grammar represented by a functor $\mathcal{FS} \to W\Sigma$, where we have indicated the action of the functor on the generators as well as the induced action on a closed derivation tree.</figcaption></figure>

may only be prepended to the beginning of a word, while arrows $v : * \to \top$ may only be appended to the end of a word. As we will see in examples later on, it becomes interesting to consider the spliced arrow operad over $\mathcal{F}\mathbb{B}_{\Sigma}^{\$}$, which includes operations of the form $f = w_0 - \dots - w_n$$\$ : (*,*)$, $\dots$, $(*,*) \to (*, \top)$ and $g = \hat{w}_0 - \dots - w_n : (*,*)$, $\dots$, $(*,*) \to (\bot,*)$ that may be seen as spliced words with explicit “end of input” and “beginning of input” markers.

**Remark 1.7.** The operad $W1$ of spliced arrows over the terminal category is isomorphic to the terminal operad, with a single color $(*,*)$, and a single $n$-ary operation $id - \dots - id : (*,*)$, $\dots$, $(*,*) \to (*,*)$ of every arity $n$. Likewise, the operad of spliced arrows over the product of two categories decomposes as a product of spliced arrow operads $W(C \times D) \simeq WC \times WD$. This might suggest that the functor $W: \mathrm{Cat} \to \mathrm{Oper}$ is a right adjoint, and we will see in §3.2 that this is indeed the case.

**1.3. Context-free grammars over a category.** Classically, a context-free grammar is defined as a tuple $G = (\Sigma, N, S, P)$ consisting of a finite set $\Sigma$ of terminal symbols, a finite set $N$ of nonterminal symbols, a distinguished nonterminal $S \in N$ called the start symbol, and a finite set $P$ of production rules of the form $R \to \sigma$ where $R \in N$ and $\sigma \in (N \cup \Sigma)^*$ is a string of terminal or nonterminal symbols. Observe that any sequence $\sigma$ on the right-hand side of a production can be factored as $\sigma = w_0 R_1 w_1 \dots R_n w_n$ where $w_0, \dots, w_n$ are words of terminals and $R_1, \dots, R_n$ are nonterminal symbols, thus yielding

$$R \to w_0 R_1 w_1 \dots R_n w_n$$

as the general form of a production rule. We can use this simple observation that production rules factor into nonterminal and terminal components to capture derivations in context-free grammars by functors $p : \mathcal{FS} \to W\Sigma$, as illustrated in Figure 2, and more generally we can use it to define context-free grammars over arbitrary categories.

**Definition 1.8.** A context-free grammar over a category (or categorical CFG) is a tuple $G = (C, \mathcal{S}, S, p)$ consisting of a category $C$, a finite species $\mathcal{S}$ equipped with a distinguished color $S \in \mathcal{S}$, and a functor of operads $p : \mathcal{FS} \to WC$. We then refer to the colors of $\mathcal{S}$ as
nonterminals and to the operations of $\mathcal{F}\mathbb{S}$ as derivations or parse trees. The context-free language of arrows $\mathcal{L}_G$ generated by the grammar $G$ is the subset of arrows in $\mathcal{C}$ which, seen as constants of $\mathcal{W}\mathcal{C}$, are in the image of a closed derivation of $S$, that is, $\mathcal{L}_G = \{p(\alpha) \mid \alpha : S\} \subseteq \mathcal{C}(A, B)$, where $p(S) = (A, B)$.

As suggested in the Introduction, every context-free grammar in the classical sense $G = (\Sigma, N, S, P)$ corresponds to a context-free grammar over $\mathcal{F}\mathbb{B}_{\Sigma}$. For the grammar of Figure 2, the corresponding species $\mathbb{S}$ has three colors NP, VP, S and four nodes,

$$ 
\begin{array}{l}
x_1 : \text{NP, VP} \to \mathbb{S} \\
x_2, x_3 : \text{NP} \\
x_4 : \text{NP} \to \text{VP}
\end{array}
$$

with the functor $p : \mathcal{F}\mathbb{S} \to \mathcal{W}\Sigma (= \mathcal{W}\mathcal{F}\mathbb{B}_{\Sigma})$ uniquely defined by the action

$$ 
\begin{array}{l}
x_1 \mapsto \varepsilon - \varepsilon - \varepsilon \\
x_2 \mapsto \text{mom} \\
x_3 \mapsto \text{tom} \\
x_4 \mapsto \text{loves} - \varepsilon
\end{array}
$$

on the generators as displayed in the middle of the figure. Conversely, any finite species $\mathbb{S}$ equipped with a color $S \in \mathbb{S}$ and a functor of operads $p : \mathcal{F}\mathbb{S} \to \mathcal{W}\Sigma$ uniquely determines a context-free grammar over the alphabet $\Sigma$. Indeed, the colors of $\mathbb{S}$ give the nonterminals of the grammar and $S$ the distinguished start symbol, while the nodes of $\mathbb{S}$ together with the functor $p$ give the production rules, with each node $x : R_1, \dots, R_n \to R$ such that $p(x) = w_0 - \dots - w_n$ determining a context-free production rule $x : R \to w_0 R_1 w_1 \dots R_n w_n$.

**Proposition 1.9.** A language $\mathcal{L} \subseteq \Sigma^*$ is context-free in the classical sense if and only if it is the language of arrows of a context-free grammar over $\mathcal{F}\mathbb{B}_{\Sigma}$.

An interesting feature of the general notion of categorical context-free grammar is that the nonterminals of the grammar $G = (\mathcal{C}, \mathbb{S}, S, p)$ are sorted in the sense that every color of $\mathbb{S}$ is mapped by $p$ to a unique color of $\mathcal{W}\mathcal{C}$, corresponding to a pair of objects of $\mathcal{C}$. Adapting the conventions from our work on type refinement systems, we sometimes write $R \sqsubseteq^p (A, B)$ or simply $R \sqsubseteq (A, B)$ to indicate that $p(R) = (A, B)$ and say that the nonterminal $R$ refines the “gap type” $(A, B)$. We emphasize that the language $\mathcal{L}_G$ generated by a grammar with start symbol $S \sqsubseteq (A, B)$ is a subset of the homset $\mathcal{C}(A, B)$.

**Example 1.10.** To illustrate some of the versatility afforded by the more general notion of context-free grammar, consider a CFG over the category $\mathcal{F}\mathbb{B}_{\Sigma}^{\mathbb{S}}$ from Example 1.6. Such a grammar may include production rules that can only be applied upon reaching the end of the input or only at the beginning, which is useful in practice, albeit usually modelled in an ad hoc fashion. For example, the grammar of arithmetic expressions defined by Knuth in the original paper on LR parsing [Knu65, example (27)] may be naturally described as a grammar over $\mathcal{F}\mathbb{B}_{\Sigma}^{\mathbb{S}}$, which in addition to having three “classical” nonterminals $E, T, P \sqsubseteq (*, *)$ contains a distinguished nonterminal $S \sqsubseteq (*, \top)$. Knuth’s “zeroth” production rule $0 : S \to E\mathbb{S}$ is then just a unary node $0 : E \to S$ in $\mathbb{S}$, mapped by $p$ to the operation $\varepsilon - \mathbb{S} : (*, *) \to (*, \top)$ in $\mathcal{W}\mathcal{F}\mathbb{B}_{\Sigma}^{\mathbb{S}}$.
Observe that almost all of these properties can be immediately translated to express properties of context-free grammars over any category $\mathcal{C}$. Basic closure properties [HMU07, §7.3] of classical context-free languages (CFLs) also generalize easily to CFLs of arrows.

**Proposition 1.12.**

(1) If $\mathcal{L}_1, \dots, \mathcal{L}_k \subseteq \mathcal{C}(A, B)$ are CFLs of arrows, so is their union $\bigcup_{i=1}^k \mathcal{L}_i \subseteq \mathcal{C}(A, B)$.

(2) If $\mathcal{L}_1 \subseteq \mathcal{C}(A_1, B_1), \dots, \mathcal{L}_n \subseteq \mathcal{C}(A_n, B_n)$ are CFLs of arrows, and if $w_0 - \dots - w_n : (A_1, B_1), \dots, (A_n, B_n) \to (A, B)$ is an operation of $\mathcal{W}\mathcal{C}$, then the "spliced concatenation" $w_0\mathcal{L}_1 w_1 \dots \mathcal{L}_n w_n = \{w_0 u_1 w_1 \dots u_n w_n \mid u_1 \in \mathcal{L}_1, \dots, u_n \in \mathcal{L}_n\} \subseteq \mathcal{C}(A, B)$ is also context-free.

(3) If $\mathcal{L} \subseteq \mathcal{C}(A, B)$ is a CFL of arrows in a category $\mathcal{C}$ and $F : \mathcal{C} \to \mathcal{D}$ is a functor of categories, then the functorial image $F(\mathcal{L}) \subseteq \mathcal{D}(F(A), F(B))$ is also context-free.

*Proof.* The proofs of (1) and (2) are just refinements of the standard proofs for context-free languages of words, keeping track of the underlying gap types:

(1) Given grammars $G_i = (\mathcal{C}, \mathcal{S}_i, S_i, p_i)$ for $i = 1 \dots k$, where all of the $S_i$ refine the same gap type $(A, B)$, we define a new grammar $G = (\mathcal{C}, \mathcal{S}, S, p)$ that generates the union of the languages $\mathcal{L}_G = \bigcup_{i=1}^k \mathcal{L}_{G_i}$ by taking $\mathcal{S}$ to be the disjoint union of the colors and nodes of $\mathcal{S}_1, \dots, \mathcal{S}_k$ combined with a distinguished color $S$ and unary nodes $x_i : S_i \to S$ for $i = 1 \dots k$, and defining $\phi : \mathcal{S} \to \mathcal{W}\mathcal{C}$ to be the cotupling of $\phi_1, \dots, \phi_k$ extended by the mappings $S \mapsto (A, B)$ and $x_i \mapsto id_A - id_B$ for $i = 1 \dots k$.

(2) Given grammars $G_1 = (\mathcal{C}, \mathcal{S}_1, S_1, p_1), \dots, G_n = (\mathcal{C}, \mathcal{S}_n, S_n, p_n)$ where $S_i \sqsubseteq (A_i, B_i)$ for each $1 \le i \le n$, together with an operation $w_0 - \dots - w_n : (A_1, B_1), \dots, (A_n, B_n) \to (A, B)$ of $\mathcal{W}\mathcal{C}$, we construct a new grammar $G = (\mathcal{C}, \mathcal{S}, S, p)$ that generates the spliced concatenation $w_0\mathcal{L}_{G_1} w_1 \dots \mathcal{L}_{G_n} w_n$ by taking $\mathcal{S}$ to be the disjoint union of the colors and nodes of $\mathcal{S}_1, \dots, \mathcal{S}_n$ combined with a distinguished color $S$ and a single $n$-ary node $x : S_1, \dots, S_n \to S$, and defining $\phi : \mathcal{S} \to \mathcal{W}\mathcal{C}$ to be the cotupling of $\phi_1, \dots, \phi_n$ extended by the mappings $S \mapsto (A, B)$ and $x \mapsto w_0 - \dots - w_n$.

For (3), suppose given a grammar $G = (\mathcal{C}, \mathcal{S}, S, p)$ and a functor of categories $F : \mathcal{C} \to \mathcal{D}$. Then the grammar $F(G)$ generating the language $F(\mathcal{L}_G)$ is defined by postcomposing $p$ with $\mathcal{W}F : \mathcal{W}\mathcal{C} \to \mathcal{W}\mathcal{D}$ while keeping the species $\mathcal{S}$ and start symbol $S$ the same, $F(G) = (\mathcal{D}, \mathcal{S}, S, (\mathcal{W}F) \circ p)$. $\square$

Finally, we note that there is a natural definition of morphisms between context-free grammars over the same category, which we refer to as *translations*.

**Definition 1.13.** Let $G_1 = (\mathcal{C}, \mathcal{S}_1, S_1, p_1)$ and $G_2 = (\mathcal{C}, \mathcal{S}_2, S_2, p_2)$ be two grammars over the same category. A **translation** $T : G_1 \to G_2$ is given by a functor of operads $T : \mathcal{F}\mathcal{S}_1 \to \mathcal{F}\mathcal{S}_2$ that commutes with the projection functors

<figure><img src="image_8.png" /></figure>

and preserves the start symbol $T(S_1) = S_2$. We say that the translation is **full** and/or **faithful** just in case the underlying functor $T : \mathcal{F}\mathcal{S}_1 \to \mathcal{F}\mathcal{S}_2$ is full and/or faithful.

**Proposition 1.14.** For any translation $T : G_1 \to G_2$, we have $\mathcal{L}_{G_1} \subseteq \mathcal{L}_{G_2}$. If $T$ is full then $\mathcal{L}_{G_1} = \mathcal{L}_{G_2}$, and if $T$ is both full and faithful then the grammars moreover generate isomorphic sets of parse trees for every arrow of the language.
*Proof.* A translation induces a function from constants $\alpha : S_1$ of $\mathcal{F}\mathbb{S}_1$ to constants $\beta = T(\alpha) : S_2$ of $\mathcal{F}\mathbb{S}_2$ lying over the same arrow $p_1(\alpha) = p_2(\beta)$, and hence $\mathcal{L}_{G_1} \subseteq \mathcal{L}_{G_2}$. If the translation is full (respectively, fully faithful), then this function is surjective (respectively bijective), which implies that $\mathcal{L}_{G_1} = \mathcal{L}_{G_2}$, with a bijection between sets of derivations,

$$ \{ \alpha : S_1 | p_1(\alpha) = w \} \cong \{ \beta : S_2 | p_2(\beta) = w \} $$

for every arrow $w$, in the case that $T$ is fully faithful. $\square$

We refer to the conclusion of Proposition 1.14 under the strongest condition that the functor $T$ is fully faithful as the **strong translation principle**.

**1.5. A fibrational view of parsing as a lifting problem.** We have seen how any context-free grammar $G = (C, \mathbb{S}, S, p)$ gives rise to a language $\mathcal{L}_G = \{ p(\alpha) | \alpha : S \}$, corresponding to the arrows of $C$ which, seen as constants of $WC$, are in the image of some constant of color $S$ of the free operad $\mathcal{F}\mathbb{S}$. However, beyond characterizing the language defined by a grammar, in practice one is often confronted with a dual problem, namely that of parsing: given a word $w$, we want to compute the set of all its parse trees, or at least determine all of the nonterminals which derive it. In our functorial formulation of context-free derivations, this amounts to computing the inverse image of $w$ along the functor $p$, i.e., the set of constants $p^{-1}(w) = \{ \alpha | p(\alpha) = w \}$, or alternatively the set of colors in the image of $p^{-1}(w)$ along the output-color function.

To better understand this view of parsing as a lifting problem along a functor of operads, we find it helpful to first recall the correspondence between functors of categories $p : \mathcal{D} \to C$ and lax functors $F : C \to \text{Span}(\text{Set})$, where $\text{Span}(\text{Set})$ is the bicategory whose objects are sets, whose 1-cells $S : X \dashrightarrow Y$ are spans $X \leftarrow S \to Y$, and whose 2-cells are morphisms of spans. Suppose given such a functor $p : \mathcal{D} \to C$. To every object $A$ of $C$ there is an associated fiber $F(A) = p^{-1}(A)$ of objects in $\mathcal{D}$ living over $A$, while to every arrow $w : A \to B$ of $C$ there is an associated fiber $F(w) = p^{-1}(w)$ of arrows in $\mathcal{D}$ living over $w$, equipped with a pair of projection functions $F(A) \leftarrow F(w) \to F(B)$ mapping any lifting $\alpha : R \to S$ of $w : A \to B$ to its source $R \in F(A)$ and target $S \in F(B)$. Moreover, given a pair of composable arrows $u : A \to B$ and $v : B \to C$ in $C$, there is a morphism of spans

$$ F(u)F(v) \longrightarrow F(uv) : F(A) \dashrightarrow F(C) \qquad (1.1) $$

from the composite of the spans $F(u) : F(A) \dashrightarrow F(B)$ and $F(v) : F(B) \dashrightarrow F(C)$ associated to $u : A \to B$ and $v : B \to C$ to the span $F(uv) : F(A) \dashrightarrow F(C)$ associated to the composite arrow $uv : A \to C$. This morphism of spans is realized using composition in the category $\mathcal{D}$, namely by the function taking any pair of a lifting $\alpha : R \to S$ of $u$ and a lifting $\beta : S \to T$ of $v$ to the composite $\alpha\beta : R \to T$, which is a lifting of $uv$ by functoriality $p(\alpha\beta) = p(\alpha)p(\beta) = uv$. Similarly, the identity arrows in the category $\mathcal{D}$ define, for every object $A$ of the category $C$, a morphism of spans

$$ \mathrm{id}_{F(A)} \longrightarrow F(id_A) : F(A) \dashrightarrow F(A) \qquad (1.2) $$

from the identity span $F(A) \leftarrow F(A) \to F(A)$ to the span associated to the identity arrow $id_A : A \to A$. Associativity and neutrality of composition in $\mathcal{D}$ ensure that the 2-cells (1.1)
and (1.2) make the diagrams below commute:

<figure><img src="image_9.png" /></figure>

for all triples of composable arrows $u : A \to B$, $v : B \to C$ and $w : C \to D$, and therefore that this collection of data defines what is called a lax functor $F : C \to \text{Span}(\text{Set})$. In general it is *only* lax, in the sense that the 2-cells $F(u)F(v) \Rightarrow F(uv)$ and $\text{id}_{F(A)} \Rightarrow F(\text{id}_A)$ are not necessarily invertible.

Conversely, starting from the data provided by a lax functor $F : C \to \text{Span}(\text{Set})$, we can define a category denoted $\int_C F$ together with a functor $\pi : \int_C F \to C$. The category $\int_C F$ has objects the pairs $(A, R)$ of an object $A$ in $C$ and an element $R \in F(A)$, and arrows $(w, \alpha) : (A, R) \to (B, S)$ the pairs of an arrow $w : A \to B$ in $C$ and an element $\alpha \in F(w)$ mapped to $R \in F(A)$ and $S \in F(B)$ by the respective legs of the span:

<figure><img src="image_10.png" /></figure>

Here we slightly abuse notation by writing $F(w)$ for the apex of the span $F(A) \dashrightarrow F(B)$ assigned to $w : A \to B$. The composition and identity of the category $\int_C F$ are then given by the morphisms of spans $F(u)F(v) \Rightarrow F(uv)$ and $\text{id}_{F(A)} \Rightarrow F(\text{id}_A)$ witnessing the lax functoriality of $F : C \to \text{Span}(\text{Set})$. The functor $\pi : \int_C F \to C$ is given by the first projection. This construction of a category $\int_C F$ equipped with a functor $\pi : \int_C F \to C$ starting from a lax functor $F : C \to \text{Span}(\text{Set})$, apparently first made explicit in [PA97, Prop. 4], is a mild variation of Bénabou's construction [Bén72, Bén00] of the same starting from a lax normal functor $F : C^{\text{op}} \to \text{Dist}$, which is itself a generalization of the well-known Grothendieck construction of a fibration starting from a pseudofunctor $F : C^{\text{op}} \to \text{Cat}$. One can show that given a functor of categories $p : \mathcal{D} \to C$, the construction applied to the associated lax functor $F : C \to \text{Span}(\text{Set})$ induces a category $\int_C F$ isomorphic to $\mathcal{D}$, in such a way that $p$ coincides with the isomorphism composed with $\pi$. Recently, Ahrens and Lumsdaine [AL19] have introduced the useful terminology “displayed category” to refer to this way of presenting a category $\mathcal{D}$ equipped with a functor $\mathcal{D} \to C$ as a lax functor $C \to \text{Span}(\text{Set})$, with their motivations coming from formalization of mathematics.

The constructions which turn a functor of categories $p : \mathcal{D} \to C$ into a lax functor $F : C \to \text{Span}(\text{Set})$ and back into a functor $\pi : \int_C F \to C$ can be adapted smoothly to functors of operads, viewing $\text{Span}(\text{Set})$ as a 2-categorical operad whose $n$-ary operations $S : X_1, \dots, X_n \dashrightarrow Y$ are multi-legged-spans

<figure><img src="image_11.png" /></figure>

or equivalently spans $X_1 \times \dots \times X_n \leftarrow S \to Y$, and with the same notion of 2-cell. We will follow Ahrens and Lumsdaine's suggestion and refer to the data of such a lax functor
living over $\mathcal{O}$ to a species living over $\mathbb{I} + \mathcal{O} \circ \mathcal{O}$, so that in order to obtain again a species living over $\mathcal{O}$ (and thus define an endofunctor) one needs to “push forward” along the canonical $W_{\mathcal{O}}$-algebra $[e, m] : \mathbb{I} + \mathcal{O} \circ \mathcal{O} \to \mathcal{O}$ that encodes the operad structure of $\mathcal{O}$, seen as a monoid in $(\text{Spec}, \circ, \mathbb{I})$. A detailed discussion is beyond the scope of this paper, but we nevertheless state the following proposition, whose intuitive content should be clear:

**Proposition 1.15.** Let $\phi : \mathbb{S} \to \mathcal{O}$ be a map of species from a species $\mathbb{S}$ into an operad $\mathcal{O}$, and let $p : \mathcal{F}\mathbb{S} \to \mathcal{O}$ be the corresponding functor from the free operad. Then the associated lax functor $F : \mathcal{O} \to \text{Span}(\text{Set})$ computing the fibers of $p$ is given by $F(A) = \phi^{-1}(A)$ on colors of $\mathcal{O}$, and by the least family of spans $F(f)$ indexed by operations $f : A_1, \dots, A_n \to A$ of $\mathcal{O}$ such that

$$F(f) \cong \sum_{\substack{f=id_A \\ \phi(R)=A}} id_R + \sum_{f=g^{\circ}(h_1, \dots, h_k)} \phi^{-1}(g) \cdot (F(h_1), \dots, F(h_k)) \quad (1.4)$$

where we write $\circ$ for composition in the operad $\mathcal{O}$ and $\bullet$ for formal composition of nodes in $\mathbb{S}$ with operations in $\mathcal{F}\mathbb{S}$. Specializing the formula to constant operations, the left summand disappears and (1.4) simplifies to:

$$F(c) \cong \sum_{c=g^{\circ}(c_1, \dots, c_k)} \phi^{-1}(g) \cdot (F(c_1), \dots, F(c_k)) \quad (1.5)$$

For the benefit of readers with a background in logic, we note that the inductive characterization of displayed free operads may be equivalently expressed as a sequent calculus parameterized by an underlying map of species $\phi : \mathbb{S} \to \mathcal{O}$, see Figure 3. Adapting a convention from our type refinement systems work, we write

$$R_1, \dots, R_k \underset{g}{\stackrel{\phi}{\rightleftharpoons}} R$$

for the judgment whose evidence is provided by a node $x : R_1, \dots, R_k \to R$ in $\mathbb{S}$ such that $\phi(x) = g$, and similarly

$$S_1, \dots, S_n \underset{f}{\stackrel{p}{\rightleftharpoons}} R$$

for the judgment whose evidence is provided by an operation $f : S_1, \dots, S_n \to R$ in $\mathcal{F}\mathbb{S}$ such that $p(\alpha) = f$. Again, we write $R \sqsubseteq^p A$ to indicate that $R$ is a color of $\mathcal{F}\mathbb{S}$ with image $p(R) = A$ in $\mathcal{O}$. As standard, we treat the inference rules as an inductive definition, in the sense that the set of derivations of the calculus is the least set closed under the inference rules. Then formulas (1.4) and (1.5) are equivalent to the following:

**Proposition 1.16.** For the sequent calculus of Fig. 3, parameterized with respect to a map of species $\phi : \mathbb{S} \to \mathcal{O}$ and the corresponding functor $p : \mathcal{F}\mathbb{S} \to \mathcal{O}$, derivations of $\Gamma \Rightarrow_f^p R$ are in one-to-one correspondence with operations $\alpha : \Gamma \to R$ in $\mathcal{F}\mathbb{S}$ such that $p(\alpha) = f$. As a special case, constants $\alpha : R$ such that $p(\alpha) = c$ are in one-to-one correspondence with derivations of $\Rightarrow_c^p R$, which necessarily only use instances of the NODE rule.
$$ \begin{array}{c} \text{LEAF} \\ \frac{R \underset{\text{id}_A}{\overset{p}{\sqsubseteq}} A}{R \underset{\text{id}_A}{\overset{p}{\Rightarrow}}} \end{array} \qquad \text{NODE} \qquad \frac{f = g \circ (h_1, \dots, h_k)}{\frac{R_1, \dots, R_k \underset{g}{\overset{\phi}{\Rightarrow}} R \quad \Gamma_1 \underset{h_1}{\overset{p}{\Rightarrow}} R_1 \quad \dots \quad \Gamma_k \underset{h_k}{\overset{p}{\Rightarrow}} R_k}{\Gamma_1, \dots, \Gamma_k \underset{f}{\overset{p}{\Rightarrow}} R}} $$

<caption>Figure 3: A sequent calculus for displayed free operads.</caption>

1.7. **Application to parsing.** Instantiating (1.5) with the underlying functor of a categorical CFG generated by a map of species $\phi: \mathbb{S} \to \mathcal{WC}$, we immediately obtain the following characteristic formula for the family of sets of parse trees $F(w)$ of an arrow $w$ in $\mathcal{C}$, seen as liftings of the constant $w$ in $\mathcal{WC}$ to a constant in $\mathcal{FS}$:

$$ F(w) \cong \sum_{w=w_0 u_1 w_1 \dots u_n w_k} \phi^{-1}(w_0 - \dots - w_k) \bullet (F(u_1), \dots, F(u_k)) \quad (1.6) $$

Equivalently, specializing the sequent calculus of Figure 3 and translating the generic judgment forms into traditional CFG notation by

$$ \begin{array}{rcl} R_1, \dots, R_k & \underset{w_0 - \dots - w_n}{\overset{\phi}{\Rightarrow}} & R \quad \rightsquigarrow \quad R \to w_0 R_1 w_1 \dots R_n w_n \\ & \underset{w}{\overset{p}{\Rightarrow}} & R \quad \rightsquigarrow \quad R \to^+ w \end{array} $$

we obtain the following inference rule:

$$ \frac{w = w_0 u_1 w_1 \dots u_k w_k \quad R \to w_0 R_1 w_1 \dots R_k w_k \quad R_1 \to^+ u_1 \quad \dots \quad R_k \to^+ u_k}{R \to^+ w} \quad (1.7) $$

inductively defining the set of closed context-free derivations. For any given word $w$, let $N_w = \{R \mid R \to^+ w\}$ be the set of nonterminals that derive it, corresponding to the image of $F(w)$ along the function returning the root label of a parse tree. We have that:

$$ R \in N_w \iff w = w_0 u_1 w_1 \dots u_k w_k \wedge \\ R \to w_0 R_1 w_1 \dots R_k w_k \wedge R_1 \in N_{u_1} \wedge \dots \wedge R_k \in N_{u_k} \quad (1.8) $$

This equation is essentially the characteristic formula expressed by Leermakers [Lee89] for the defining relation of the “C-parser”, which generalizes the well-known Cocke-Younger-Kasami (CYK) algorithm. Presentations of the CYK algorithm are usually restricted to grammars in Chomsky normal form (cf. [LL09]), but as observed by Leermakers, the relation $N_w$ defined by (1.8) can be solved effectively for any context-free grammar $G$ and given word $w = a_1 \dots a_n$ by building up a parse matrix $N_{i,j}$ indexed by the subwords $w_{i,j} = a_{i+1} \dots a_j$ for all $1 \le i \le j \le n$, and yields a cubic complexity algorithm in the case that $G$ is bilinear in the sense of §1.4. Moreover, by adding nonterminals, it is always possible to transform a CFG into a bilinear CFG that generates the same language, even preserving the original derivations up to isomorphism.

**Proposition 1.17.** For any categorical context-free grammar $G = (\mathcal{C}, \mathbb{S}, S, p)$, there is a bilinear CFG $G_{\text{bin}} = (\mathcal{C}, \mathbb{S}_{\text{bin}}, S, p_{\text{bin}})$ together with a fully faithful functor of operads $B: \mathcal{FS} \to \mathcal{FS}_{\text{bin}}$ such that $p = Bp_{\text{bin}}$. In particular, by the strong translation principle (Prop. 1.14) we have that $\mathcal{L}_G = \mathcal{L}_{G_{\text{bin}}}$ with isomorphic sets of parse trees.
*Proof.* Given $G = (C, \mathbb{S}, S, p)$, a bilinear grammar $G_{\text{bin}} = (C, \mathbb{S}_{\text{bin}}, S, p_{\text{bin}})$ is constructed as follows. $\mathbb{S}_{\text{bin}}$ includes all of the colors and all of the nullary nodes of $\mathbb{S}$, with $\phi_{\text{bin}}(R) = \phi(R)$ and $\phi_{\text{bin}}(c) = \phi(c)$. Additionally, for every node $x: R_1, \dots, R_n \to R$ of $\mathbb{S}$ of positive arity $n > 0$, where $\phi(x) = w_0 - \dots - w_n: (A_1, B_1), \dots, (A_n, B_n) \to (A, B)$ in $WC$, we include:

* $n$ new colors $I_{x,0}, \dots, I_{x,n-1}$, with $\phi_{\text{bin}}(I_{x,i-1}) = (A_i, A_i)$ for $1 \le i \le n$;

* one nullary node $x_0: I_{x,0}$, with $\phi_{\text{bin}}(x_0) = w_0$;

* $n$ binary nodes $x_1, \dots, x_n$, where $x_i: I_{x,i-1}, R_i \to I_{x,i}$ and $\phi_{\text{bin}}(x_i) = id_A - id_{A_i} - w_i$ for all $1 \le i \le n$, under the convention that $I_{x,n} = R$.

We define the functor $B: \mathcal{FS} \to \mathcal{FS}_{\text{bin}}$ on colors by $B(R) = R$, on nullary nodes by $B(c) = c$, and on nodes $x: R_1, \dots, R_n \to R$ of positive arity by $B(x) = x_n \circ_0 \dots \circ_0 x_1 \circ_0 x_0$. By induction on $n$, there is a one-to-one correspondence between nodes $x: R_1, \dots, R_n \to R$ of $\mathbb{S}$ and operations $B(x): R_1, \dots, R_n \to R$ of $\mathcal{FS}_{\text{bin}}$, so the functor $B$ is fully faithful. $\square$

**1.8. Generalized context-free grammars.** We conclude this section by observing that for many purposes, a functor of operads from a free operad generated by a finite species $\mathbb{S}$ into an arbitrary operad $\mathcal{O}$ may be considered (after selection of a start symbol in $\mathbb{S}$) as a “generalized” context-free grammar, generating a language of constants in $\mathcal{O}$.

**Definition 1.18.** A generalized context-free grammar (over an operad) is a tuple $G = (\mathcal{O}, \mathbb{S}, S, p)$ consisting of an operad $\mathcal{O}$, a finite species $\mathbb{S}$ equipped with a distinguished color $S \in \mathbb{S}$, and a functor of operads $p: \mathcal{FS} \to \mathcal{O}$. The generalized context-free language of constants generated by the grammar $G$ is given by the subset of constants $\mathcal{L}_G = \{p(\alpha) \mid \alpha : S\} \subseteq \mathcal{O}(A)$, where $p(S) = A$.

Hence a classical context-free word grammar can be seen as a generalized CFG (gCFG) over a spliced word operad $\mathcal{O} = W\Sigma$, and a categorical CFG as a gCFG over a spliced arrow operad $\mathcal{O} = WC$. By selecting $\mathcal{O}$ appropriately, Definition 1.18 encompasses other extensions of the notion of context-free grammar from the literature.

**Example 1.19.** For any operad $\mathcal{P}$, one can construct a new operad $!_{\text{aff}}\mathcal{P}$ whose colors are lists $[A_1, \dots, A_k]$ of colors in $\mathcal{P}$ and whose $n$-ary operations $[\Gamma_1], \dots, [\Gamma_n] \to [A_1, \dots, A_k]$ are pairs $([f_1, \dots, f_k], \sigma)$ of a list of operations $f_1: \Omega_1 \to A_1, \dots, f_k: \Omega_k \to A_k$ in $\mathcal{P}$ and an injection $\sigma: \Omega_1, \dots, \Omega_k \hookrightarrow \Gamma_1, \dots, \Gamma_n$ from the concatenation of the inputs of the $k$ operations to the concatenation of the $n$ input lists. Observe that if $\mathcal{P}$ is an uncolored operad (i.e., has a unique color, like $W\Sigma$), then the colors of $!_{\text{aff}}\mathcal{P}$ are isomorphic to natural numbers. Let us also remark that $!_{\text{aff}}\mathcal{P}$ is in fact the *free semi-cartesian* (or “affine”) *strict monoidal operad* over $\mathcal{P}$.<fnref n="3" />

A gCFG over $!_{\text{aff}}W\Sigma$ with start symbol $S \sqsubseteq 1$ is precisely a *multiple context-free grammar* [SMFK91], while more generally a gCFG over $!_{\text{aff}}WC$ with $S \sqsubseteq [(A, B)]$ (for some objects $A$ and $B$ of $\mathcal{C}$) could be called a “multiple categorical CFG”. Such a grammar is a *k-multiple CFG* (again in the sense of [SMFK91]) just in case every nonterminal $R \sqsubseteq [\Gamma]$ refines a list of length $|\Gamma| \le k$.

For instance, let $\mathcal{C}$ be the free category over the following graph:

<figure><img src="image_12.png" /></figure>

<footnote n="3">³See [Lei04, p. 56–58] for discussion of the similar constructions of the free PRO(P) over a colored operad.</footnote>
We can define a 3-mCFG generating the language $a^n#b^n#'c^n$ with a pair of nonterminals

$$S \sqsubseteq [(A, C)]$$

$$R \sqsubseteq [(A, A), (B, B), (C, C)]$$

and production rules specified by the triple of nodes in S

$$x_1 : R$$

$$x_2 : R \to R$$

$$x_3 : R \to S$$

mapped respectively to the following operations in $!_{\text{aff}}WC$

$$[id_A, id_B, id_C] : [(A, A), (B, B), (C, C)]$$

$$[a-id_A, b-id_B, c-id_C] : [(A, A), (B, B), (C, C)] \to [(A, A), (B, B), (C, C)]$$

$$[-\#-\#'-] : [(A, A), (B, B), (C, C)] \to [(A, C)]$$

where we have elided the injection component and only shown the lists of operations in WC, since the injection $\sigma$ used is always the identity.

**Example 1.20.** The free cartesian strict monoidal operad $!_{\text{cart}}P$ over an operad $P$ is constructed just as $!_{\text{aff}}P$, but replacing injections by arbitrary functions $\sigma : \Omega_1, \dots, \Omega_k \to \Gamma_1, \dots, \Gamma_n$. A gCFG over $!_{\text{cart}}W\Sigma$ is precisely a *parallel multiple context-free grammar* in the sense of [SMFK91], and more generally a gCFG over $!_{\text{cart}}WC$ could be called a “parallel multiple categorical CFG”.

Examples of generalized context-free languages of a more semantic flavor can also be derived by taking $\mathcal{O}$ to be Set or similar. Recall that Set is the (large) operad whose colors are sets and whose operations $f : X_1, \dots, X_n \to X$ are $n$-ary functions $f : X_1 \times \dots \times X_n \to X$, with composition defined as expected.

**Example 1.21.** (Adapted from [CE12, §1.1.3].) Let DiGr$_{•,•}$ be the set of finite directed graphs equipped with two distinct vertices labeled src and tgt. The *parallel composition* $G \parallel H$ of a pair of graphs $(G, H) \in \text{DiGr}_{•,•} \times \text{DiGr}_{•,•}$ is formed by starting from the disjoint union of the two graphs and identifying their two sources and two targets to form a graph $G \parallel H \in \text{DiGr}_{•,•}$ with $\text{src}(G \parallel H) = \text{src}(G) = \text{src}(H)$ and $\text{tgt}(G \parallel H) = \text{tgt}(G) = \text{tgt}(H)$. The *series composition* $G;H$ is formed by similarly starting from the disjoint union of $G$ and $H$ but then identifying $\text{tgt}(G) = \text{src}(H)$ and taking $\text{src}(G;H) = \text{src}(G)$ and $\text{tgt}(G;H) = \text{tgt}(H)$. We can define a gCFG over Set with one nonterminal $S \sqsubseteq \text{DiGr}_{•,•}$ and three production rules corresponding to a pair of binary nodes par : $S, S \to S$ and seq : $S, S \to S$ mapped to the operations $\parallel$ and $;$ respectively, plus a constant $e : S$ mapped to the unique directed graph $\bullet \to \bullet$ with one edge and two vertices. The language of constants generated by this gCFG is exactly the set of *series-parallel graphs*.

Many of the properties of categorical CFGs discussed in §1.4 extend directly to gCFGs, as do all of the closure properties of CFLs and the translation principles. For the record, we state here the appropriate generalizations for gCFLs of the closure properties listed in Proposition 1.12, omitting the proofs since they are essentially identical.

**Proposition 1.22.**

$$(1) \text{ If } \mathcal{L}_1, \dots, \mathcal{L}_k \subseteq \mathcal{O}(A) \text{ are gCFLs, then so is their union } \bigcup_{i=1}^k \mathcal{L}_i \subseteq \mathcal{O}(A).$$
(2) If $\mathcal{L}_1 \subseteq \mathcal{O}(A_1), \dots, \mathcal{L}_n \subseteq \mathcal{O}(A_n)$ are gCFLs, and if $f : A_1, \dots, A_n \to A$ is an operation of $\mathcal{O}$, then the application $f(\mathcal{L}_1, \dots, \mathcal{L}_n) = \{f(u_1, \dots, u_n) \mid u_1 \in \mathcal{L}_1, \dots, u_n \in \mathcal{L}_n\} \subseteq \mathcal{O}(A)$ is also a gCFL.

(3) If $\mathcal{L} \subseteq \mathcal{O}(A)$ is a gCFL of constants in an operad $\mathcal{O}$ and $F : \mathcal{O} \to \mathcal{P}$ is a functor of operads, then the functorial image $F(L) \subseteq \mathcal{P}(F(A))$ is also a gCFL.

**1.9. Related work.** Although the notion of context-free grammar over a category seems to be new, the idea of viewing classical context-free grammars vibrationally and representing them as functors appears in various guises in the literature. Walters briefly described in [Wal89] how context-free grammars may be represented by certain morphisms of multigraphs that we would call maps of species (see comment immediately after Definition 1.1) and might notate $\phi : \mathcal{S} \to \tilde{\Sigma}$, where $\tilde{\Sigma}$ is defined similarly to the underlying species of $\mathcal{W}\Sigma$ but with two distinct kinds of nodes: nullary nodes $a : *$ for every letter $a \in \Sigma$, and $n$-ary nodes $\mu_n : *^n \to *$ standing for concatenation. Note that taking $\tilde{\Sigma}$ so-defined as the target of $\phi$ imposes a restriction on the grammar (similar to Chomsky normal form), that all production rules are either of the form $R \to a$ or $R \to R_1 \dots R_n$. In order to recover the language generated by a grammar with start symbol $S$, Walters next considers the functor $\mathcal{F}_\times \phi : \mathcal{F}_\times \mathcal{S} \to \mathcal{F}_\times \tilde{\Sigma}$ between the free categories with products generated by the species, then composes with the canonical functor $\psi : \mathcal{F}_\times \tilde{\Sigma} \to \mathrm{Mon}_\Sigma$ into the Lawvere theory of monoids containing $\Sigma$, and finally takes the image $\psi(\mathcal{F}_\times \phi(\mathcal{F}_\times \mathcal{S}(1, S)))$. All in all, we find the encoding of classical CFGs by functors of operads $\mathcal{F}\mathcal{S} \to \mathcal{W}\Sigma$ to be simpler, more direct and more general, but Walters' approach is certainly similar in spirit.

The methodology of abstract categorial grammars introduced by De Groote [dG01] is probably even more closely related to our approach. Based on linear lambda-calculus, the approach consists of expressing different kinds of grammars by specifying a signature $\Sigma_1$ as an "abstract vocabulary", a signature $\Sigma_2$ as an "object vocabulary", and a "lexicon" given by a morphism of signatures $\Sigma_1 \to \Sigma_2$. In particular, context-free grammars are represented by taking the abstract vocabulary $\Sigma_1$ to have a type for each nonterminal and a constant $x : R_1 \stackrel{\circ}{\to} \dots \to R_n \stackrel{\circ}{\to} R$ for every production rule $x : R \to w_0 R_1 \dots R_n w_n$, the object vocabulary $\Sigma_2$ to have a single type $*$ and a constant $a : * \stackrel{\circ}{\to} *$ for every letter, and the lexicon to map every nonterminal $R$ to $* \stackrel{\circ}{\to} *$, and every constant $x$ as above to the lambda-term $\lambda u_1 \dots u_n \cdot w_0 \circ u_1 \circ \dots \circ u_n \circ w_n$. Although the definition of ACGs was originally given type-theoretically rather than categorically, the framework could very clearly be reformulated naturally in an operadic setting, using free closed operads, and seems to have deep connections with the approach described here. One way of making this connection more precise could be to prove that the interpretation of pairs $(A, B)$ as types $A \stackrel{\circ}{\to} B$ extends to a full and faithful embedding $\mathcal{W}C \to \mathcal{F}_{\circ}C$ of the operad of spliced arrows $\mathcal{W}C$ into the free closed operad over $C$, where the operations of $\mathcal{F}_{\circ}C$ may be represented by $\beta\eta$-normal (ordered) linear lambda terms. It is worth emphasizing that ACGs were introduced to capture a wide variety of grammatical formalisms, including categorial grammars in the style of Lambek calculus but also extensions of context-free grammars like we discussed in §1.8 such as multiple CFGs [dGP04].
<figure><img src="image_13.png" /><figcaption>Figure 4: Left: an NFA represented with a traditional state-diagram. Right: the bare NFA as a finitary ULF functor $p : \mathcal{F}Q \to \mathcal{F}\mathbb{B}_{\Sigma}$. (We do not label the generators of $\mathcal{F}Q$ or indicate composite arrows, and we use colors to indicate the images of the generators in $\mathcal{F}\mathbb{B}_{\Sigma}$.)</figcaption></figure>

## 2. FINITE-STATE AUTOMATA OVER CATEGORIES AND OPERADS

We have seen how the classical notion of context-free grammar generalizes naturally to define context-free grammars over any category $\mathcal{C}$, or even over any operad $\mathcal{O}$, presented by a functor of operads $\mathcal{FS} \to \mathcal{WC}$ or $\mathcal{FS} \to \mathcal{O}$ together with a distinguished start symbol in $\mathcal{S}$. In this section, we carry on in the same fibrational vein and begin by explaining how classical nondeterministic finite-state word automata may be generalized to define NFAs over any category, presented by functors of categories $\mathcal{Q} \to \mathcal{C}$ that are both *finitary* and have the *unique lifting of factorizations* (ULF) property, together with distinguished initial and accepting states in $\mathcal{Q}$. The base category $\mathcal{C}$ is often freely generated, as in the case of word automata, but we also give natural examples of automata over non-free categories. One important aspect of this approach is that it adapts smoothly when one shifts from word automata to tree automata, simply by replacing categories with operads. Indeed, a key fact is that the splicing construction transports any finitary ULF functor of categories $p : \mathcal{Q} \to \mathcal{C}$ to a finitary ULF functor of operads $\mathcal{W}p : \mathcal{W}\mathcal{Q} \to \mathcal{W}\mathcal{C}$, thereby transforming an NFA over a category into an NFA over its operad of spliced arrows. As we will see in the following section (§3), this observation greatly facilitates the proof that context-free languages are closed under intersection with regular languages.

### 2.1. Nondeterministic word automata as finitary ULF functors over categories.
Classically, a nondeterministic finite-state automaton may be represented by a finite alphabet $\Sigma$, a finite set $Q$ of states, a finite set $\text{Tran}$ of transitions together with a labelling function $\delta : \text{Tran} \to Q \times \Sigma \times Q$, and a choice of initial and accepting states. We will focus first on the underlying “bare” automaton $M = (\Sigma, Q, \delta)$ before the choice of initial and accepting states. Every such bare automaton $M$ induces a functor of categories $p : \mathcal{Q} \to \mathcal{F}\mathbb{B}_{\Sigma}$ where $\mathcal{Q}$ is the category with set of objects $\mathcal{Q}$ and with arrows freely generated by arrows of the form $t : q \to q'$ for every transition $t \in \text{Tran}$ such that $\delta(t) = (q, a, q')$, and where the functor $p : \mathcal{Q} \to \mathcal{F}\mathbb{B}_{\Sigma}$ transports every such generator $t : q \to q'$ to the arrow $a : * \to *$ representing the letter $a \in \Sigma$ in the category $\mathcal{F}\mathbb{B}_{\Sigma}$. See Figure 4 for an example. Under this formulation, any composite arrow $\alpha : q_0 \to q_f$ of the category $\mathcal{Q}$ describes a run of the automaton $M$.
over the word $w = p(\alpha) : * \to *$ which starts in state $q_0 \in Q$ and ends in state $q_f \in Q$, as depicted below:

<figure><img src="image_14.png" /></figure>

One distinctive property of the functor $p : Q \to \mathcal{F}\mathbb{B}_\Sigma$ is that it has the unique lifting of factorizations (ULF) property [Law86, BN00, BF00, LM10]. Recall that a functor of categories has the ULF property (or “is ULF”) when any factorization of the image of an arrow lifts uniquely to a factorization of that arrow.

**Definition 2.1.** A functor $p : \mathcal{D} \to \mathcal{C}$ is said to be **ULF** if for every arrow $\alpha$ of $\mathcal{D}$, if $p(\alpha) = uv$ for some pair of arrows $u$ and $v$ of $\mathcal{C}$, there exists a unique pair of arrows $\beta$ and $\gamma$ in $\mathcal{D}$ such that $\alpha = \beta\gamma$ and $p(\beta) = u$ and $p(\gamma) = v$.

Such functors are also known as *discrete Conduché fibrations* [Joh99, Gue20], and they provide a common generalization of both discrete fibrations and discrete opfibrations. The ULF condition arises naturally when considering the correspondence recalled in §1.5 between functors $\mathcal{D} \to \mathcal{C}$ and lax functors $\mathcal{C} \to \operatorname{Span}(\operatorname{Set})$.

**Proposition 2.2.** A functor of categories $p : \mathcal{D} \to \mathcal{C}$ is ULF iff the associated lax functor $F : \mathcal{C} \to \operatorname{Span}(\operatorname{Set})$ is a pseudofunctor.

*Proof.* The definition of ULF says precisely that the structure maps $F(u)F(v) \implies F(uv)$ of the lax fiber functor are invertible, thus establishing the right-to-left direction. Moreover, it is an immediate consequence of the ULF property that $p(\alpha) = \mathrm{id}_A$ implies $\alpha$ is an identity arrow, since otherwise there would be two distinct liftings $\alpha = \mathrm{id} \alpha$ and $\alpha = \alpha \mathrm{id}$ of the factorization $\mathrm{id}_A = \mathrm{id}_A \mathrm{id}_A$. Hence the structure maps $\mathrm{id}_{F(A)} \implies F(\mathrm{id}_A)$ are also invertible and $F$ is a pseudofunctor, thus establishing the left-to-right implication. $\square$

The ULF property reflects an important structural property of nondeterministic finite-state automata: that every arrow $\alpha : q_0 \to q_f$ lying above some arrow $p(\alpha) = w$ corresponding to a run of the automaton can be factored uniquely as a sequence of transitions along the letters of the word $w$. In the case of the ULF functor $p : Q \to \mathcal{F}\mathbb{B}_\Sigma$ that we construct from a classical NFA, both the categories $Q$ and $\mathcal{F}\mathbb{B}_\Sigma$ are freely generated, and the functor $p$ is generated from a homomorphism of graphs. (In effect, on the right-hand side of Figure 4 we visualize the functor by this generating graph homomorphism.) This is not a coincidence, as any ULF functor into a free category is necessarily of this form.

**Proposition 2.3** ([Str96], [Gue20]). Let $p : \mathcal{D} \to \mathcal{C}$ be a functor into a category $\mathcal{C} = \mathcal{F}\mathbb{G}$ freely generated by some graph $\mathbb{G}$. Then $p$ is ULF iff $\mathcal{D} = \mathcal{F}\mathbb{H}$ is free over some graph $\mathbb{H}$ and $p = \mathcal{F}\phi$ is generated by a graph homomorphism $\phi : \mathbb{H} \to \mathbb{G}$.

*Proof.* The right-to-left direction is immediate. For the left-to-right implication, we take $\mathbb{H} = p^{-1}(\mathbb{G})$ to be the graph containing just those arrows of $\mathcal{D}$ lying over the generators of $\mathcal{C}$. Since the image of any arrow $\alpha$ in $\mathcal{D}$ uniquely decomposes as a composition of edges $p(\alpha) = e_1 \cdots e_n$ in $\mathbb{G}$, the ULF property implies that $\alpha$ uniquely decomposes as a composition of edges in $\mathbb{H}$, and $p$ is generated by its restriction to the generators $\phi : \mathbb{H} \to \mathbb{G}$. $\square$

Of course another important property of NFAs is their finite nature, which may also be expressed as a property of the corresponding functor $p : Q \to \mathcal{F}\mathbb{B}_\Sigma$.
**Definition 2.4.** We say that a functor $p : \mathcal{D} \to \mathcal{C}$ is **finitary** if either of the following equivalent conditions hold:

* the fiber $p^{-1}(A)$ as well as the fiber $p^{-1}(w)$ is finite for every object $A$ and arrow $w$ in the category $\mathcal{C}$;

* the associated lax functor $F : \mathcal{C} \to \text{Span}(\text{Set})$ factors via $\text{Span}(\text{FinSet})$.

The unique lifting of factorizations and finitary fiber properties characterize classical NFAs in the following sense.

**Proposition 2.5.** Let $\phi : \mathbb{H} \to \mathbb{G}$ be a homomorphism into a finite graph $\mathbb{G}$. Then $\mathcal{F}\phi : \mathcal{F}\mathbb{H} \to \mathcal{F}\mathbb{G}$ is finitary iff $\mathbb{H}$ is finite.

*Proof.* By the infinite pigeonhole principle. □

<figure><img src="image_15.png" /></figure>

**Proposition 2.6.** A functor $p : \mathcal{Q} \to \mathcal{F}\mathbb{B}_{\Sigma}$ corresponds to the underlying bare automaton of a NFA iff $p$ is ULF and finitary.

*Proof.* By Props. 2.3 and 2.5, $p$ is ULF and finitary iff $\mathcal{Q} \cong \mathcal{F}\mathbb{Q}$ is generated by a finite graph with $p$ induced by a homomorphism, thereby defining the transition graph of a bare NFA. □

<figure><img src="image_16.png" /></figure>

This leads us to the following definition of NFA over an arbitrary category.

**Definition 2.7.** A nondeterministic finite-state automaton over a category is given by a tuple $M = (\mathcal{C}, \mathcal{Q}, p, q_0, q_f)$ consisting of two categories $\mathcal{C}$ and $\mathcal{Q}$, a finitary ULF functor $p : \mathcal{Q} \to \mathcal{C}$, and a pair $q_0, q_f$ of objects of $\mathcal{Q}$. An object of $\mathcal{Q}$ is then called a **state** and an arrow of $\mathcal{Q}$ is called a **run** of the automaton. The **regular language of arrows $\mathcal{L}_M$** recognized by the automaton is the set of arrows $w$ in $\mathcal{C}$ that can be lifted along $p$ to an arrow $\alpha : q_0 \to q_f$ in $\mathcal{Q}$, that is $\mathcal{L}_M = \{p(\alpha) \mid \alpha : q_0 \to q_f\} \subseteq \mathcal{C}(A, B)$, where $p(q_0) = A, p(q_f) = B$.

Similarly to the way a categorical CFG may be considered as a functor of pointed operads (see Remark 1.11), it is also sometimes helpful to view a categorical NFA as a finitary ULF functor of bipointed categories $p_M : (\mathcal{Q}, q_0, q_f) \to (\mathcal{C}, A, B)$. We emphasize that the definition does not require the base category $\mathcal{C}$ to be free, which we will see in examples later on.

Before continuing to develop this definition, let us briefly comment on our treatment of initial and accepting states, as well as the treatment of determinism and $\epsilon$-transitions. Rabin and Scott’s original definition of NFA [RS59] (also adopted by Eilenberg [Eil74]), takes a set of initial states together with a set of accepting states, while some more recent authors [HMU07, Sip13] take a single initial state together with a set of accepting states. By Rabin and Scott’s determinization theorem, a language $\mathcal{L} \subseteq \Sigma^*$ may be recognized by a NFA with a set of initial and accepting states just in case it may be recognized by a DFA with a single initial state and a set of accepting states, so the choice of having a single initial state or a set of initial states does not matter in terms of recognition power. Classically, the same is not quite true for NFAs over a fixed alphabet with a single initial state and a single accepting state (in the absence of $\epsilon$-transitions), since the language recognized by such an automaton is necessarily closed under concatenation if it contains the empty word. Nevertheless, it is easy to see that any NFA with a set of initial and accepting states may be converted to an equivalent NFA with a single initial state and a single accepting state, over an alphabet extended with distinguished symbols marking the beginning and the end of the word. This construction is particularly natural to express using the category $\mathcal{F}\mathbb{B}_{\Sigma}^{\mathbb{S}}$ introduced in Example 1.6.
**Proposition 2.8.** A language $\mathcal{L} \subseteq \Sigma^*$ is regular in the classical sense if and only if $\hat{\mathcal{L}}$ is
the language of arrows recognized by a nondeterministic finite-state automaton over $\mathcal{F}\mathbb{B}_{\Sigma}^{\mathcal{S}}$.

*Proof.* Given a classical NFA $M$ with underlying bare automaton $Q \to \mathcal{F}\mathbb{B}_{\Sigma}^{\mathcal{S}}$, we construct an NFA $M^{\mathcal{S}} = (\mathcal{F}\mathbb{B}_{\Sigma}^{\mathcal{S}}, Q', p' : Q' \to \mathcal{F}\mathbb{B}_{\Sigma}^{\mathcal{S}}, q_0, q_f)$ where $Q'$ and the functor $p'$ are constructed from $Q$ and $p$ by freely adjoining a pair of objects $q_0$ and $q_f$ lying over $\perp$ and $\top$ respectively, together with an arrow $q_0 \to q$ over $\hat{\mathcal{S}} : \perp \to *$ for every initial state $q$ and an arrow $q' \to q_f$ over $\mathcal{S} : * \to \top$ for every accepting state $q'$ of $M$. By construction, every accepting run of $M$ over the word $w$ corresponds to an accepting run of $M^{\mathcal{S}}$ over the arrow $\hat{w}\mathcal{S} : \perp \to \top$. $\square$

Although Definition 2.7 could be adapted to take a set of initial and accepting states, we find the convention of taking a single pair $(q_0, q_f)$ of initial and accepting states to align well with the definition of context-free languages of arrows generated by a single nonterminal (Definition 1.8). Let us also observe here that the category $\mathcal{F}\mathbb{B}_{\Sigma}^{\mathcal{S}}$ in the statement of Proposition 2.8 is isomorphic to the *input category* $\mathcal{I}_{\text{word}}$ used in Colcombet and Petrişan’s definition of categorical automata. (See bottom of Figure 1 of [CP20]; we will give a more detailed comparison with Colcombet and Petrişan’s framework in §2.5 below.)

**Definition 2.9.** An NFA $M = (\mathcal{C}, \mathcal{Q}, p : \mathcal{Q} \to \mathcal{C}, q_0, q_f)$ is **deterministic** if the functor $p$ is a discrete opfibration, i.e., for any arrow $w : A \to B$ in $\mathcal{C}$ and any state $q \in \mathcal{Q}$ such that $p(q) = A$, there is a unique arrow $\alpha : q \to q'$ such that $p(\alpha) = w$. $M$ is **codeterministic** if $p$ is a discrete fibration, i.e., for any arrow $w : A \to B$ in $\mathcal{C}$ and any state $q' \in \mathcal{Q}$ such that $p(q') = B$, there exists a unique arrow $\alpha : q \to q'$ such that $p(\alpha) = w$. $M$ is **bideterministic** if it is both deterministic and codeterministic, i.e., $p$ is a discrete bifibration. Finally, $M$ is a **partial (co/bi) deterministic automaton** if the functor $p : \mathcal{Q} \to \mathcal{C}$ is a partial discrete op/bi/fibration, in the sense that for any $w : A \to B$ in $\mathcal{C}$ and $q \in \mathcal{Q}$ such that $p(q) = A$ (or $q'$ such that $p(q') = B$), there is at most one $\alpha : q \to q'$ such that $p(\alpha) = w$.

**Remark 2.10.** With this way of representing finite-state automata by functors $p : \mathcal{Q} \to \mathcal{C}$, $\epsilon$-transitions may be naturally interpreted as non-identity arrows $\alpha : q \to q'$ in $\mathcal{Q}$ mapped by $p$ to an identity arrow $\mathrm{id}_A : A \to A$ in $\mathcal{C}$. However, it is an immediate consequence of the ULF property that an NFA in the sense of Definition 2.7 cannot contain any non-trivial fiber categories $p^{-1}(A)$ (Proposition 2.2). One would therefore need a more general notion of ULF functor in order to accommodate categorical NFAs with $\epsilon$-transitions. This seems to raise some subtle issues. In particular, the standard treatment of $\epsilon$-removal [HMU07, §2.5] seems to indicate that one needs to design a notion between ULF functors and general Conduché fibrations. Recall that the standard notion of Conduché fibration weakens the ULF property by only requiring uniqueness of factorizations up to zigzag in the fiber, which means here zigzag of $\epsilon$-transitions. The right definition of categorical NFA with $\epsilon$-transitions should probably ensure more, that there is a universal (initial or terminal) solution in the space of possible factorizations.

As we have seen, our definition of NFA over a category does not require the base category $\mathcal{C}$ to be free. We now list some examples of such automata and the regular languages of arrows that they generate.

**Example 2.11 (Product automata).** The product of two finitary ULF functors $p : \mathcal{Q} \to \mathcal{C}$ and $p' : \mathcal{Q}' \to \mathcal{C}'$ is again a finitary ULF functor $p \times p' : \mathcal{Q} \times \mathcal{Q}' \to \mathcal{C} \times \mathcal{C}'$. This enables us to construct the product of two NFAs $M$ and $M'$ as an NFA $M \times M'$ whose underlying bare automaton is $p \times p'$ and whose initial and accepting states are given by the pairing of the
respective initial states $(q_0, q'_0)$ and $(q_f, q'_f)$. Note that even if $M$ and $M'$ are NFAs over free categories $C = \mathcal{FG}$ and $C' = \mathcal{FG'}$, the product automaton $M \times M'$ will not be since the product of free categories is not a free category. Intuitively, $M \times M'$ may be interpreted as an automaton that reads pairs of arrows in parallel. It recognizes the cartesian product $\mathcal{L} \times \mathcal{L}'$ of the languages recognized by $M$ and $M'$.

**Example 2.12** (Singleton automata). For any word $w = a_1 \dots a_n$ of length $n$, there is a partial bideterministic $(n+1)$-state automaton $M_w$ that recognizes the singleton language $\{w\}$, with initial state 0, accepting state $n$, and transitions of the form $(i, a_{i+1}, i+1)$ for each $0 \le i < n$. This construction may be generalized to define a (not necessarily deterministic or codeterministic) NFA $M_w$ recognizing any arrow $w$ in any category satisfying a certain finitariness assumption. Indeed, for any arrow $w : A \to B$ of a category $C$, the category of factorizations $\text{Fact}_w$ of $w$ (also called the interval category of $w$ in [LM10]) is defined by taking objects to be triples $(X, u, v)$ of an object $X \in C$ and a pair of arrows $u : A \to X$, $v : X \to B$ such that $w = uv$, and arrows $(X, u, v) \to (X', u', v')$ to be arrows $x : X \to X'$ such that $u' = ux$ and $v = xv'$. This category has an initial object $(id_A, w)$ and a terminal object $(w, id_B)$, and it comes equipped with an evident forgetful functor $\mu_w : \text{Fact}_w \to C$ returning the middle of a factorization, which is always ULF [Joh99, LM10]. Hence

$$M_w = (C, \text{Fact}_w, \mu_w, (id_A, w), (w, id_B)) \qquad (2.1)$$

may be considered as a nondeterministic automaton recognizing the singleton language $\{w\}$, although it is not necessarily a finite-state automaton since the functor $\mu_w$ need not be finitary in general. Let us say that a category $C$ has finitary factorizations if this is always the case, in other words, if the ULF functor $\mu_w : \text{Fact}_w \to C$ is finitary for every arrow $w$ of $C$. Then we see that to any arrow $w$ of a category $C$ with finitary factorizations, (2.1) defines an NFA $M_w$ recognizing exactly that arrow.

Free categories always have finitary factorizations, and indeed the category of factorizations of any arrow of a free category is isomorphic to a non-empty finite ordinal, as in the example above of the $(n+1)$-state automaton associated to a word of length $n$.

A category with finitely many objects has finitary factorizations just in case every arrow has finitely many factorizations $w = uv$ of length 2.<fnref n="4" /> For example, consider the one-object category $\mathcal{E}$ containing a single non-identity arrow $f : * \to *$ that is idempotent $ff = f$. The NFA $M_f$ recognizing the language $\{f\} \subseteq \mathcal{E}(*, *)$ has three states $(id, f)$, $(f, id)$, and $(f, f)$, as depicted by the following transition diagram in which all paths of length $\ge 1$ commute:

<figure><img src="image_17.png" /></figure>

**Example 2.13** (Total automata). The identity functor $id_C : C \to C$ on a category is trivially ULF and finitary, since every object and arrow has a unique lifting. Hence for any pair of objects $A$ and $B$ of $C$, there is an NFA $M_{C(A,B)} = (C, C, id_C, A, B)$ recognizing the total

<footnote n="4">⁴Note that having finitary factorizations is weaker than the Möbius condition on a category [LM10], which asks that the set of non-trivial decompositions $\{(u_1, \dots, u_n) \mid n \ge 0, w = u_1 \cdots u_n (\forall 1 \le i \le n, u_i \ne id)\}$ of every arrow $w$ is finite (cf. [LM10, Prop. 2.6]). As a property of monoids, having finitary factorizations is standardly called the finite decomposition property, which is weaker than what Eilenberg called the local finiteness property [Eil74, §VII.4, p.170] corresponding to the Möbius condition.</footnote>
language $\mathcal{C}(A, B)$, i.e., accepting every arrow $w : A \to B$. In the case of the one-object category $\mathcal{C} = \mathcal{F}\mathbb{B}_\Sigma$, this is just the familiar automaton with a single (initial and accepting) state and a transition on that state for every letter of $\Sigma$. On the other hand, it is worth emphasizing that $M_{\mathcal{C}(A,B)}$ defines an NFA in our sense even when $\mathcal{C}$ has infinitely many objects. In particular, this example shows that what is important is finiteness of the fibers of the functor $p : Q \to \mathcal{C}$ defining an NFA, and not of the total category of states $Q$.

**Example 2.14** (Asynchronous automata). One good reason for considering NFAs whose base category $\mathcal{C}$ is not free is that they provide for interesting notions of automata when the category $\mathcal{C}$ is presented by generators and relations. Let us say that an equation in a graph $G$ is a pair $(f, g)$ of paths $f, g : A \to B$ with same source and target. Every set $\mathcal{R}$ of such equations induces a congruence $\sim_{\mathcal{R}}$ on the paths of $G$, defined as the smallest equivalence relation between paths of $G$ with same source and target, compatible to composition, and such that $f \sim_{\mathcal{R}} g$ for every equation $(f, g) \in \mathcal{R}$. We say that a category $\mathcal{C}$ is presented by a graph $G$ of generators and a set $\mathcal{R}$ of equations when it comes equipped with an isomorphism $c : \mathcal{F}G/\sim_{\mathcal{R}} \to \mathcal{C}$ from the category $\mathcal{F}G/\sim_{\mathcal{R}}$ whose objects are nodes of $G$ and whose arrows are $\sim_{\mathcal{R}}$-equivalence classes of paths.

A remarkable property of ULF functors $p : \mathcal{D} \to \mathcal{C}$ into a category $\mathcal{C}$ presented by a graph $G$ and a set $\mathcal{R}$ of equations, with isomorphism $c : \mathcal{F}G/\sim_{\mathcal{R}} \to \mathcal{C}$, is that the category $\mathcal{D}$ inherits a presentation by a graph $p^*G$ and a set $p^*\mathcal{R}$ of equations derived from $G$ and $\mathcal{R}$. The graph $p^*G$ has nodes the pairs $(x, A)$ of a node $x$ in $G$ and an object $A$ of $\mathcal{D}$ such that $c(x) = p(A)$, and edges the pairs $(e, u)$ of an edge $e : x \to y$ in $G$ and an arrow $u : A \to B$ in $\mathcal{D}$ such that $c(e) = p(u)$. The set $p^*\mathcal{R}$ contains all equations $(f, g)$ between paths of $p^*G$ of the form

$$f = (e_1, u_1) \cdots (e_m, u_m), g = (e'_1, v_1) \cdots (e'_n, v_n) \quad : \quad (x, A) \longrightarrow (y, B)$$

such that $(e_1 \cdots e_m, e'_1 \cdots e'_n) \in \mathcal{R}$ and the composite arrows $u_1 \cdots u_m = v_1 \cdots v_n$ are equal in the category $\mathcal{D}$. The isomorphism $d : p^*G/\sim_{p^*\mathcal{R}} \to \mathcal{D}$ is given by the second projection $(x, A) \mapsto A$ on objects, and by the map $[e_1 \cdots e_m, u_1 \cdots u_m] \mapsto u_1 \cdots u_m$ sending an equivalence class of lists of edge/arrow pairs to the composition of the arrows in $\mathcal{D}$.

We illustrate the property by giving a direct description of NFAs on a category $\mathcal{C}$ defined by a Mazurkiewicz alphabet. A concurrent alphabet $(\Sigma, D)$ as defined by Mazurkiewicz [Maz89] is a set $\Sigma$ of letters, equipped with a reflexive and symmetric binary relation $D \subseteq \Sigma \times \Sigma$. Two letters $a, b \in \Sigma$ are called *dependent* when $(a, b) \in D$ and *independent* otherwise. The *permutation equivalence* on finite words is defined as the smallest equivalence relation $\sim$ such that $w_1 ab w_2 \sim w_1 ba w_2$ for every pair of words $w_1, w_2 \in \Sigma^*$ and independent letters $a, b \in \Sigma$. A *trace* is an equivalence class of the permutation equivalence. Traces $w \in \Sigma^*/\sim$ may be regarded as the arrows $w : * \to *$ of a one-object category $\mathcal{F}\mathbb{B}_\Sigma/\sim_D$ obtained by quotienting the category $\mathcal{F}\mathbb{B}_\Sigma$ with an equation between arrows $ab = ba : * \to *$ for every pair of independent letters $a, b \in \Sigma$.

Unpacking the definitions, a NFA over $\mathcal{F}\mathbb{B}_\Sigma/\sim_D$ may be equivalently described as follows, starting from the data of a finite set $Q$ of states, a finite set *Tran* of transitions together with a labelling function $\delta : \text{Tran} \to Q \times \Sigma \times Q$, and a choice of initial and accepting states. The transition graph is moreover equipped with a set $\diamond$ of permutation tiles defined as pairs $(\alpha, \beta)$ of paths $\alpha = st$ and $\beta = t's'$ of length 2 of the form

$$\delta(s) = (q, a, q'), \delta(t) = (q', b, q''), \delta(t') = (q, b, q''') \text{ and } \delta(s') = (q'''', a, q'')$$
where $q, q', q'', q''' \in Q$ are states and the two letters $a, b \in \Sigma$ are independent. We write $\alpha \diamond \beta$ when $(\alpha, \beta) \in \diamond$. The set of permutation tiles is required to satisfy the following properties:

(1) permutation tiles are deterministic: $\alpha \diamond \beta$ and $\alpha \diamond \beta'$ implies $\beta = \beta'$,

(2) permutation tiles are symmetric: $\alpha \diamond \beta$ implies $\beta \diamond \alpha$,

(3) successive transitions with independent letters can permute: for every transition path $\alpha = st$ of length 2 with $\delta(s) = (q, a, q')$ and $\delta(t) = (q', b, q'')$ where the two letters $a, b \in \Sigma$ are independent, there exists a permutation tile $\alpha \diamond \beta$.

The correspondence works as follows. Given a finite transition system $(Q, \text{Tran}, \delta)$ equipped with a set $\diamond$ of permutation tiles, one defines the category $\mathcal{C}$ presented by the corresponding graph $\mathcal{G}$ with an equation $(\alpha, \beta)$ for every permutation tile $\alpha \diamond \beta$; the three properties (1), (2), and (3) ensure then that the labelling functor $q: \mathcal{C} \to \mathcal{F}\mathcal{B}_{\Sigma}/\sim_D$ is finitary ULF. Conversely, every finitary ULF functor $p: \mathcal{C} \to \mathcal{F}\mathcal{B}_{\Sigma}/\sim_D$ induces a finite graph $\mathcal{G} = p^*\mathcal{B}_{\Sigma}$ and a set of equations $\diamond = p^*\mathcal{R}_D$ where $\mathcal{R}_D$ denotes the set of equations $(ab, ba)$ for $a$ and $b$ two independent letters; one checks that the nodes and edges of $\mathcal{G}$ define a transition system $(Q, \text{Tran}, \delta)$ which satisfies properties (1), (2), and (3). Note that property (3) reflects the ULF property for the factorisation of the arrow $ab$ in $\mathcal{F}\mathcal{B}_{\Sigma}/\sim_D$ as $b$ followed by $a$, for any pair of independent letters $a$ and $b$ in $\Sigma$.

This establishes that the notion of NFA over the category $\mathcal{F}\mathcal{B}_{\Sigma}/\sim_D$ of Mazurkiewicz traces captures a natural notion of asynchronous automaton, corresponding to a nondeterministic version of Bednarczyk's asynchronous systems [Bed88, HM00, Mor05, BM06] where property (3) is called the Independent Diamond (ID) property. A detailed comparison of this class of asynchronous automaton with the more liberal notion of automaton with concurrency relations [DS02, GM10] appears in [Mor05]. The ID property implies that every NFA over $\mathcal{F}\mathcal{B}_{\Sigma}/D$ satisfies the cube property (CP) discussed in [HM00] and thus defines what is called an asynchronous graph in [MM07, Mel21]. We leave for future work the connection with Zielonka's theorem which is based on a more concrete and process-based notion of concurrent automaton [Zie87, BM06].

**2.2. From word automata to tree automata and beyond.** Reassuringly, the foregoing fibrational analysis of nondeterministic finite-state automata based on finitary ULF functors adapts smoothly when one shifts from word automata to tree automata [CDG$^+$08]. As a first step in that direction, we describe how the ULF and finite fiber properties may be extended to functors of operads.

**Definition 2.15.** A functor of operads $p: \mathcal{D} \to \mathcal{O}$ has the **unique lifting of factorizations property** (or **is ULF**) if any of the following equivalent conditions hold:

(1) for any operation $\alpha$ of $\mathcal{D}$, if $p(\alpha) = g \circ (h_1, \dots, h_n)$ for some operation $g$ and list of operations $h_1, \dots, h_n$ of $\mathcal{O}$, there exists a unique operation $\beta$ and list of operations $\gamma_1, \dots, \gamma_n$ of $\mathcal{D}$ such that $\alpha = \beta \circ (\gamma_1, \dots, \gamma_n)$ and $p(\beta) = g$, $p(\gamma_1) = h_1, \dots, p(\gamma_n) = h_n$;

(2) for any operation $\alpha$ of $\mathcal{D}$, if $p(\alpha) = g \circ_i h$ for some operations $g$ and $h$ of $\mathcal{O}$ and index $i$, there exists a unique pair of operations $\beta$ and $\gamma$ of $\mathcal{D}$ such that $\alpha = \beta \circ_i \gamma$ and $p(\beta) = g$ and $p(\gamma) = h$;

(3) the structure maps of the associated lax functor of operads $F: \mathcal{O} \to \text{Span}(\text{Set})$ discussed in §1.5 are invertible.

**Definition 2.16.** We say that a functor of operads $p: \mathcal{D} \to \mathcal{O}$ is **finitary** if either of the following equivalent conditions hold:
* the fiber $p^{-1}(A)$ as well as the fiber $p^{-1}(f)$ is finite for every color $A$ and operation $f$ of the operad $\mathcal{O}$;

* the associated lax functor of operads $F: \mathcal{O} \to \text{Span}(\text{Set})$ factors via $\text{Span}(\text{FinSet})$.

Just as we saw in the previous section, one can easily check that the underlying bare automaton $M = (\Sigma, Q, \delta)$ of a (bottom-up or top-down) nondeterministic finite-state tree automaton (cf. §1.1 and §1.6 of [CDG+08]) gives rise to a finitary ULF functor of operads $p: Q \to \mathcal{F}\Sigma$, where

* $\mathcal{F}\Sigma$ is the free operad generated by the ranked alphabet $\Sigma$ (seen as an uncolored species);

* the operad $Q$ has states of the automaton as colors and operations freely generated by $n$-ary nodes of the form $t: q_1, \dots, q_n \to q$ for every transition $t \in \text{Tran}$ of the form $\delta(t) = (q_1, \dots, q_n, a, q)$, with $a \in \Sigma_n$;

* the functor $p$ transports every such $n$-ary transition $t: q_1, \dots, q_n \to q$ to the underlying $n$-ary letter $a: *, \dots, * \to *$.

Moreover, this correspondence is one-to-one.

**Proposition 2.17.** Let $p: \mathcal{D} \to \mathcal{O}$ be a functor into an operad $\mathcal{O} = \mathcal{F}\Sigma$ freely generated by some species $\Sigma$. Then $p$ is ULF iff $\mathcal{D} = \mathcal{F}\mathcal{S}$ is free over some species $\mathcal{S}$ and $p = \mathcal{F}\phi$ is generated by a map of species $\phi: \mathcal{S} \to \Sigma$.

**Proposition 2.18.** A functor of operads $p: Q \to \mathcal{F}\Sigma$ corresponds to a bare nondeterministic finite-state tree automaton iff $p$ is ULF and finitary.

This motivates us to proceed as for word automata and propose a more general notion of finite-state automaton over an arbitrary operad.

**Definition 2.19.** A nondeterministic finite-state automaton over an operad is given by a tuple $M = (\mathcal{O}, Q, p: Q \to \mathcal{O}, q_r)$ consisting of two operads $\mathcal{O}$ and $Q$, a finitary ULF functor of operads $p: Q \to \mathcal{O}$, and a color $q_r$ of $Q$. A color of $Q$ is called a **state**, and an operation of $Q$ is called a **run tree** of the automaton $p: Q \to \mathcal{O}$. The **regular language of constants** $\mathcal{L}_M$ recognized by the automaton is the set of constants $c$ in $\mathcal{O}$ that can be lifted along $p$ to a constant $\alpha: q_r$ in $Q$, that is $\mathcal{L}_M = \{p(\alpha) \mid \alpha: q_r\} \subseteq \mathcal{O}(A)$, where $p(q_r) = A$.

Let us refer to NFAs over categories in the sense of Definition 2.7 as *categorical automata* for short, and NFAs over operads in the foregoing sense as *operadic automata*.

We now state a simple property of ULF and finitary functors establishing a useful connection between categorical automata and operadic automata.

**Proposition 2.20.** Suppose that $p: Q \to C$ is a functor of categories. If $p$ is ULF (respectively, finitary) then so is the functor of operads $Wp: WQ \to WC$.

*Proof.* Follows immediately from the fact that a lifting of an operation $f_0-\dots-f_n$ in $WC$ along $Wp$ is a sequence of liftings of the arrows $f_0, \dots, f_n$ in $C$ along $p$. $\square$

**Corollary 2.21.** For any categorical automaton $M = (\mathcal{C}, Q, p, q_0, q_f)$ there is an associated operadic automaton $WM = (WC, WQ, Wp, (q_0, q_f))$ generating the same language $\mathcal{L}_M = \mathcal{L}_{WM}$.

*Proof.* By Proposition 2.20, and because constants of $WC$ are exactly arrows of $C$. $\square$

We will see that the $WM$ construction transforming an automaton over a category into an automaton over its operad of spliced arrows is fundamental for computing the intersection of a context-free language with a regular language of arrows. Moreover, we highlight that
since operads of spliced arrows are not freely generated (Remark 1.5), the $WM$ construction provides an important example of how operadic automata truly generalize classical tree automata.

**Remark 2.22.** As an aside, we mention that it is also interesting to consider deterministic finite-state automata over spliced arrow operads. To see why, let us first observe that any discrete opfibration over $WC$, which may be viewed equivalently as a functor of operads $WC \to \text{Set}$, induces a category $\mathcal{D}$ equipped with an identity-on-objects functor of categories $C \to \mathcal{D}$, and conversely. Indeed, given a functor $F: WC \to \text{Set}$ one can construct a new category $\mathcal{D}_F$ with same objects as $C$ and whose arrows $\alpha: A \to B$ are given by the elements of $F(A, B)$, with composition and identities defined by the interpretations

$$F(id_A - id_B - id_C) : F(A, B) \times F(B, C) \to F(A, C) \\ F(id_A) : F(A, A)$$

of the corresponding spliced arrow operations. Moreover, there is an identity-on-objects functor $C \to \mathcal{D}_F$ given by sending every arrow $w: A \to B$ of $C$, seen as a constant $w: (A, B)$ of $WC$, to its interpretation $F(w): F(A, B)$. Conversely, given a category $\mathcal{D}$ and an identity-on-objects functor $h: C \to \mathcal{D}$, one can define $F_h: WC \to \text{Set}$ by taking $F_h(A, B) = \mathcal{D}(A, B)$ and defining the interpretation of the spliced arrow operations by mapping the arrows of $C$ into $\mathcal{D}$ along $h$ and then composing:

$$F_h(w_0 - w_1 - \dots - w_n) = (u_1, \dots, u_n) \mapsto h(w_0)u_1h(w_1) \dots u_nh(w_n)$$

From the description of this correspondence, it is clear it restricts to one between finitary discrete opfibrations over $WC$ (equivalent to functors $WC \to \text{FinSet}$) and locally finite categories $\mathcal{D}$ equipped with an identity-on-objects functor $C \to \mathcal{D}$. Thus what is a DFA over $WC$? Nothing more than a locally finite category $\mathcal{D}$, an identity-on-objects functor $h: C \to \mathcal{D}$, and an arrow $q_r: A \to B$ of $\mathcal{D}$, with the DFA accepting an arrow $w: A \to B$ of $C$ just in case $h(w) = q_r$. In the case that $C$ is a one-object category, this is essentially the notion of recognition by a finite monoid, which is one of the classical equivalent characterizations of regular languages [Eil74, §III.10, p.62].<fnref n="5" />

**2.3. Additional properties of ULF and finitary functors.** We state here a few more basic properties of ULF and finitary functors, in both categorical and operadic versions, that will be important in the rest of the paper.

**Proposition 2.23.** If $p: Y \to X$ is a ULF (resp. finitary) functor of categories or operads, and $G: Z \to X$ is an arbitrary functor, then the functor $G^*p: Z \times_X Y \to Z$ defined by pulling back $p$ along $G$ is ULF (resp. finitary).

<figure><img src="image_18.png" /></figure>

<footnote n="5">⁵A language $\mathcal{L} \subseteq \Sigma^*$ is said to be recognizable by a finite monoid $X$ if there exists a subset $S \subseteq X$ and a homomorphism $h: \Sigma^* \to X$ such that $\mathcal{L} = h^{-1}(S)$. Our formulation requires $S$ to be a singleton, cf. Proposition 2.8 above and the preceding discussion.</footnote>
Closure of both classes of functors under pullback along arbitrary functors may be verified directly, or may be seen as an immediate consequence of the fact that both classes of functors $p: Y \to X$ admit “Grothendieck-type” correspondences with pseudo or lax functors $F: X \to \mathcal{U}$ into a certain universe (namely, ULF functors as pseudo functors into $\mathcal{U} = \operatorname{Span}(\operatorname{Set})$, and finitary functors as lax functors into $\mathcal{U} = \operatorname{Span}(\operatorname{FinSet})$), so that the pullback along an ordinary functor $G: Z \to X$ is simply the composite $F \circ G: Z \to \mathcal{U}$.

As we already saw in Example 2.13, the identity functor $id_C: C \to C$ on any category is trivially finitary and ULF, as is the identity functor $id_O: O \to O$ on any operad. It is also easy to check that both classes of functors are closed under composition. Moreover, ULF functors satisfy a property analogous to the pasting law for pullbacks in a category, while finitary functors behave similarly to monomorphisms.

**Proposition 2.24.** *Consider a commutative triangle of functors of categories or operads:*

<figure><img src="image_19.png" /></figure>

(1) if $F$ and $G$ are ULF, then so is $H$

(2) if $F$ and $G$ are finitary, then so is $H$

(3) if $G$ and $H$ are ULF then so is $F$

(4) if $H$ is finitary then so is $F$

*Proof.* For concreteness, we take $X$, $Y$, and $Z$ to be categories. (The case where they are operads is completely analogous.)

(1) Let $\alpha$ be an arrow in $X$. Any factorization $H(\alpha) = uv$ in $Z$ lifts uniquely to a factorization of $\alpha = \beta\gamma$ with $H(\beta) = u$, $H(\gamma) = v$, by first lifting along $G$ to obtain a unique factorization of $F(\alpha)$, and then lifting along $F$.

(2) All of the fibers of $H$ are finite (for both the objects and arrows of $Z$) since they may be decomposed as a finite union of finite fibers $H^{-1}(z) = \bigcup_{y \in G^{-1}(z)} F^{-1}(y)$.

(3) Let $\alpha$ be an arrow in $X$ and $F(\alpha) = st$ a factorization in $Y$. By projecting down along $G$ and then lifting the resulting factorization $H(\alpha) = G(s)G(t)$ along $H$, we obtain unique $\beta$ and $\gamma$ such that $\alpha = \beta\gamma$, $H(\beta) = G(s)$, $H(\gamma) = G(t)$. But since $F(\alpha) = F(\beta)F(\gamma)$ is a lifting of the factorization $G(st) = G(s)G(t)$ along $G$, this implies that $F(\beta) = s$ and $F(\gamma) = t$ by the ULF property of $G$.

(4) All of the fibers $F^{-1}(y)$ are finite, since they are contained in the fibers $H^{-1}(G(y))$. $\square$

We remark in passing that finitary ULF functors may be arranged into various categories and bicategories of interest, which we describe now for the case of categorical automata (the operadic case again being completely analogous), although we will not make explicit use of these (bi)categories in the paper. For any category $C$, finitary ULF functors over $C$ and commutative triangles

<figure><img src="image_20.png" /></figure>

define a category of bare NFAs over $C$ and morphisms between them, where the functor $F: Q \to Q'$ may be seen as a **functional simulation** since it sends any run $\alpha: q_0 \to q_f$ in $Q$ over an arrow $w: A \to B$ of $C$ to a run $F(\alpha): F(q_0) \to F(q_f)$ in $Q'$ over the same arrow.
By Proposition 2.24, $F$ is itself finitary ULF, and this category is just the slice finULF/$C$ of the category finULF of small categories and finitary ULF functors between them. It is possible to formulate an analogue of Proposition 1.14: if $M$ and $M'$ are two NFAs over the same category, and $F: Q \to Q'$ is a functional simulation between their underlying bare automata that preserves initial and accepting states, then $\mathcal{L}_M \subseteq \mathcal{L}_{M'}$, where equality holds $\mathcal{L}_M = \mathcal{L}_{M'}$ when $F$ is full, extending to an isomorphism of runs when $F$ is fully faithful.
In a different direction of abstraction, a span

<figure><img src="image_21.png" /></figure>

of a finitary ULF functor $Q \to C$ and an arbitrary functor $O: Q \to D$ may be considered
as a **nondeterministic finite-state transducer** $C \to D$, since it associates to every
run $\alpha: q_0 \to q_f$ in $Q$ over an arrow $w: A \to B$ of $C$ a corresponding output arrow
$O(\alpha): O(q_0) \to O(q_f)$ in $D$. By Propositions 2.23 and 2.24, ordinary composition of spans

<figure><img src="image_22.png" /></figure>

combines a transducer $C \to D$ with a transducer $D \to \mathcal{E}$ to produce a transducer $C \to \mathcal{E}$,
and one obtains a bicategory by defining a 2-cell between transducers of the same type as a
functional simulation between the underlying bare automata that commutes with the output
functors.

**2.4. Closure properties of regular languages.** Closure of finitary ULF functors under pullback along arbitrary functors (Proposition 2.23) implies that regular languages of arrows and constants are closed under inverse functorial image, restricted to a suitable choice of objects in the source category or operad.

**Proposition 2.25.** Let $\mathcal{L} \subseteq \mathcal{C}(A, B)$ be a regular language of arrows in $\mathcal{C}$, let $F: \mathcal{D} \to \mathcal{C}$ be a functor of categories, and let $R, S$ be objects of $\mathcal{D}$ such that $F(R) = A, F(S) = B$. Then the homset-restricted inverse image $F^{-1}(\mathcal{L}) \cap \mathcal{D}(R, S)$ is regular.

**Proposition 2.26.** Let $\mathcal{L} \subseteq \mathcal{O}(A)$ be a regular language of constants in $\mathcal{O}$, let $F: \mathcal{P} \to \mathcal{O}$ be a functor of operads, and let $R$ be a color of $\mathcal{P}$ such that $F(R) = A$. Then the conset-restricted inverse image $F^{-1}(\mathcal{L}) \cap \mathcal{P}(R)$ is regular.

Note that restricting the inverse image to a homset/conset is necessary due to our conventions
for the initial and accepting states of categorical and operadic automata (although variations
of those conventions could certainly be envisaged, see discussion above after Def. 2.7). Indeed,
given a categorical automaton $M = (\mathcal{C}, \mathcal{Q}, p, q_0, q_f)$, a functor $F: \mathcal{D} \to \mathcal{C}$, and a pair of
objects $R, S$ of $\mathcal{D}$ such that $F(R) = p(q_0), F(S) = p(q_f)$, the restricted pullback automaton
is given by $F^*M|_{R,S} = (\mathcal{D}, \mathcal{D} \times_{\mathcal{C}} \mathcal{Q}, F^*p, (R, q_0), (S, q_f))$. The restricted pullback of an
operadic automaton is constructed similarly.
Conversely, since finitary ULF functors are closed under composition (Proposition 2.24), we immediately obtain closure of regular languages under functorial image along a finitary ULF functor.

**Proposition 2.27.** If $\mathcal{L} \subseteq \mathcal{C}(A, B)$ is a regular language of arrows in $\mathcal{C}$ and $F: \mathcal{C} \to \mathcal{D}$ is a finitary ULF functor of categories, then the image $F(\mathcal{L}) \subseteq \mathcal{D}(F(A), F(B))$ is also regular.

**Proposition 2.28.** If $\mathcal{L} \subseteq \mathcal{O}(A)$ is a regular language of constants in $\mathcal{O}$ and $F: \mathcal{O} \to \mathcal{P}$ is a finitary ULF functor of operads, then the image $F(\mathcal{L}) \subseteq \mathcal{P}(F(A))$ is also regular.

For example, the pushforward of a categorical automaton $M = (\mathcal{C}, \mathcal{Q}, p, q_0, q_f)$ along a finitary ULF functor $F: \mathcal{C} \to \mathcal{D}$ is the automaton $F_* M = (\mathcal{D}, \mathcal{Q}, F \circ p, q_0, q_f)$.

On the other hand, regular languages are not closed under image along an arbitrary functor, as the following counterexamples demonstrate.

**Counterexample 2.29.** Let $\mathcal{W}$ be the category of Dyck walks freely generated by the graph whose nodes are natural numbers and with a pair of edges

$$n \xrightarrow[d_n]{u_n} n + 1$$

for every $n \in \mathbb{N}$. Let $\Sigma$ be the alphabet containing a pair of brackets `[` and `]` and consider the functor $F: \mathcal{W} \to \mathcal{F}\mathbb{B}_{\Sigma}$ defined by

$$n \mapsto * \quad u_n \mapsto [ \quad d_n \mapsto ]$$

for every $n \in \mathbb{N}$. The total language $\mathcal{W}(0, 0)$ is regular (Example 2.13), but its image $F(\mathcal{W}(0, 0)) \subseteq \mathcal{F}\mathbb{B}_{\Sigma}(*, *)$ is the Dyck language of well-bracketed words, which is not a regular language in the classical sense [HMU07, p. 195] and hence cannot be a regular language of arrows in our sense by Prop. 2.6. Observe in this case that the functor $F$ is ULF since it is generated from a graph homomorphism, but it is manifestly not finitary.

**Counterexample 2.30.** Let $2 = 0 \xrightarrow{f} 1$ be the walking arrow category, and consider any functor $F: 2 \to \mathcal{C}$, which picks out an arrow $F(f) = w: A \to B$ in $\mathcal{C}$. Observe that the functor $F$ is finitary, but will typically not be ULF unless $w$ is indecomposable. The singleton language $\{f\}$ is regular (Example 2.12), and its image $F(\{f\}) = \{w\} \subseteq \mathcal{C}(A, B)$ will be as well if the category $\mathcal{C}$ has finitary factorizations, but otherwise need not be regular. In particular, let $\mathcal{C} = \mathcal{B}_{\mathbb{R}_{\ge 0}}$ be the monoid of non-negative real numbers $(\mathbb{R}_{\ge 0}, +, 0)$ considered as a one-object category, and let $w = 1$ be the unit value considered as an arrow $1: * \to *$. We claim that the language $\{1\} \subseteq \mathbb{R}_{\ge 0}$ is not regular. Suppose by way of contradiction that there is an automaton $M$ recognizing $\{1\}$ equipped with a finitary ULF functor $p: \mathcal{Q} \to \mathcal{B}_{\mathbb{R}_{\ge 0}}$ and initial and accepting states $q_0$ and $q_f$. Since 1 factors in the monoid as

$$1 = \frac{1}{n} + \frac{n-1}{n}$$

for all $n \ge 1$, the accepting run $\alpha: q_0 \to q_f$ of 1 factors as

$$\alpha = q_0 \xrightarrow{\beta_n} q_n \xrightarrow{\gamma_n} q_f$$

for some unique arrows $\beta_n$ and $\gamma_n$ lying over $\frac{1}{n}$ and $\frac{n-1}{n}$, by assumption that $p$ is ULF. Now there are two possibilities:

(1) The objects $q_n$ are distinct for all $n \ge 1$. In this case the fiber $p^{-1}(*)$ is infinite, contradicting the assumption that $p$ is finitary.
(2) There exist $i < j$ such that $q_i = q_j$. In this case

$$ \alpha' = q_0 \xrightarrow{\alpha_i} q_i = q_j \xrightarrow{\gamma_j} q_f $$

is another accepting run of the automaton over the element $p(\alpha') = \frac{1}{i} + \frac{j-1}{j} > 1$, contradicting the assumption that $M$ recognizes just the singleton language $\{1\}$.

Finally, we can easily derive that regular languages are closed under intersection.

**Proposition 2.31.** If $\mathcal{L}_1, \mathcal{L}_2 \subseteq \mathcal{C}(A, B)$ (resp. $\mathcal{L}_1, \mathcal{L}_2 \subseteq \mathcal{O}(A)$) are regular languages of arrows (resp. constants), then so is their intersection $\mathcal{L}_1 \cap \mathcal{L}_2$.

*Proof.* Given two automata $M_1$ and $M_2$ with underlying bare automata $p_1 : Q_1 \to \mathcal{C}$ and $p_2 : Q_2 \to \mathcal{C}$ over the same category $\mathcal{C}$, and with initial and accepting states mapped to the same pair of objects $A$ and $B$, the intersection automaton $M_1 \cap M_2$ can be constructed in either of two equivalent ways:

(1) By pulling back $p_1$ along $p_2$, and then taking the image along $p_2$.

(2) By forming the product automaton $M_1 \times M_2$ (Example 2.11) over $\mathcal{C} \times \mathcal{C}$ and then pulling back along the diagonal functor $\mathcal{C} \to \mathcal{C} \times \mathcal{C}$.

The construction of the intersection of operadic automata is completely analogous. $\square$

At this point, we should mention that we expect regular languages of arrows and constants to satisfy some additional closure properties just as in the classical case, including suitably formulated versions of closure under union, concatenation, and Kleene star. However, the usual proof of these facts is greatly facilitated by the use of $\epsilon$-transitions, which are ruled out by our working definition of categorical and operadic NFAs based on ULF functors (see Remark 2.10). We therefore defer consideration of these additional closure properties to the future introduction of an appropriate notion of categorical/operadic automaton with $\epsilon$-transitions. In any case, we will not need them to prove the representation theorem.

**2.5. Related work.** It is standard to represent finite-state automata by their transition graphs, and natural to consider such transition graphs as ordinary (finite directed) graphs equipped with a homomorphism into the bouquet graph on the underlying alphabet. Such a perspective on nondeterministic finite-state automata without $\epsilon$-transitions was developed by Steinberg [Ste01], motivated by monoid and semigroup theory, and with special prominence given to graph homomorphisms that are *immersions*, which correspond to partial bideterministic automata in the sense of Definition 2.9. Walters' short note on context-free languages [Wal89] that we mentioned in §1.9 also opens with a treatment of automata as graph homomorphisms, but taking morphisms of *reflexive graphs* in order to allow $\epsilon$-transitions. As discussed in Remark 2.10, an important question is how to adapt our approach based on finitary ULF functors to allow for $\epsilon$-transitions, although we are confident that this can be done by appropriately generalizing the notion of ULF. Walters' approach to automata and context-free grammars was further developed by Rosenthal [Ros95], considering also tree automata, and more recently by Earnshaw and Sobociński [ES22] to define regular languages in free monoidal categories.

The fibrational perspective on nondeterministic finite-state automata over categories and operads that we introduced here is closely related to the “functorial approach” to automata theory developed by Colcombet and Petrişan [CP20]. Roughly speaking, the approaches are dual and related by Grothendieck-type correspondences: whereas we consider automata
as functors into a category (or operad) with certain fibrational properties, Colcombet and Petrişan consider them as functors *out of* a category into different large categories of interest, such as Set for deterministic automata, Rel for nondeterministic automata, or Vec for weighted automata. Given that in many cases such Grothendieck-type correspondences rise to the level of equivalences, generally the approaches provide two complementary perspectives on the same objects. Still, it is worth drawing attention to a few small but important differences between our approach and the approach described in [CP20]. First, although many of the definitions and constructions given by Colcombet and Petrişan are stated for an arbitrary “input category” $\mathcal{I}$, in practice they consider automata over a fixed category $\mathcal{I}_{\text{word}}$, isomorphic to the category we call $\mathcal{F}\mathbb{B}_{\Sigma}^{\mathcal{S}}$, and they do not impose any finiteness condition on automata. Second, rather than having a single initial and accepting state, Colcombet and Petrişan take a more abstract definition of the “behavior” of an automaton given by precomposing with a full and faithful functor $\iota: \mathcal{O} \to \mathcal{I}$ from some “output category” $\mathcal{O}$, typically the full subcategory of $\mathcal{I}_{\text{word}} \cong \mathcal{F}\mathbb{B}_{\Sigma}^{\mathcal{S}}$ spanned by the arrows $\perp \to \top$. The idea is that precomposing with $\iota$ abstracts away the internal states of the automaton, remembering just the language that it recognizes. Colcombet and Petrişan use this to give an elegant analysis of automata minimization based on factorization systems.

Finally, and although it is by no means forced by the functorial approach, let us observe that modelling nondeterministic automata as functors into Rel (rather than as pseudofunctors into Span(Set) or Span(FinSet)) means equating all of the runs over a given word between a given pair of states. For instance, the NFA shown on the left has two distinct runs $q_0 \to q_f$ over the word $ab$, but these are identified when considering it as a Rel-automaton.

<figure><img src="image_23.png" /></figure>

The idea of generalizing regular languages from recognizable subsets of free monoids $\mathcal{L} \subseteq \Sigma^*$ to recognizable subsets of arbitrary monoids $\mathcal{L} \subseteq X$ is classic. For instance, it is discussed in Eilenberg’s book (see [Eil74, §III.12, p.68]) using several of the equivalent characterizations of regular languages, including recognition by a finite monoid. He mentions that the definition of automaton could also be suitably generalized, but does not do so explicitly “since all the known properties of recognizable sets already follow from the definition adopted above”. There is also precedent for the idea of generalizing from languages of words in free monoids to languages of arrows in free categories, having been proposed at least as early as the mid-1980s in the work of Thérien and collaborators [TSG88, WT86], who argued that this was well-motivated by automata-theoretic considerations:

> For example, we are often interested in decompositions of automata. In such situations a component may receive its input from the output of some other component. This “preprocessing” imposes restrictions on the possible input sequences that need to be considered. A simple way to take into account these restrictions is to view a machine as processing input sequences that are paths in a finite directed multigraph. [TSG88, p.395]

Again, though, rather than taking NFAs or DFAs as a starting point, these authors started from the alternative characterization of regular word languages as unions of equivalence classes of a finite index congruence on a free monoid, and explained how to generalize it to free categories in a way that allowed proving Kleene’s theorem among other results. We take one more opportunity to emphasize that our definition of regular language is not restricted to free categories and operads, and that non-free categories and operads are required in
some key examples. (The work by Thérien et al. was, incidentally, revisited by Jones who took a similar approach to define regular languages in a certain class of *profinite categories* [Jon96].) We do *not* expect Kleene's theorem on the equivalence between regular and rational languages to hold for regular languages of arrows in arbitrary categories – indeed classically it is a theorem about recognizable subsets of free monoids with counterexamples in the non-free case [Eil74, §IV.5, p.175–178], and Counterexample 2.30 demonstrates that some singleton languages of arrows cannot be recognized by any NFA. On the other hand, we mention that Fahrenberg et al. have recently proved a Kleene theorem for higher-dimensional automata (without $\epsilon$-transitions) recognizing languages of interval pomsets [FJSZ22], which it would be interesting to analyze within our framework.

Although it is beyond the scope of this paper, we expect that regular languages of arrows or constants in the sense of Definitions 2.7 and 2.19 should also have other equivalent characterizations related to the aforementioned classical ones – in particular there seem to be natural notions of *recognition by a locally finite category* and *recognition by a locally finite operad* (cf. Remark 2.22). It may be fruitful to connect this with Salvati's notion of regular language of $\lambda$-terms [Sal09] (in part inspired by [dG01]), which may be formulated as recognition by a locally finite and well-pointed cartesian closed category (cf. [MN24]).

Finally, we only briefly touched upon the subject of constructing categories of automata and transducers in §2.3, but this also has precedent in the literature. Our definition of a nondeterministic finite-state transducer as a span $C \leftarrow Q \rightarrow D$ where the left leg satisfies a fibrational condition (namely, is finitary and ULF) is similar to the notion of “Mealy morphism” defined by Paré using slightly different conditions [Par12]. Another line of work by Katis, Sabadini, and Walters [KSW97] models automata as spans of graphs, with sequential composition given by composition of spans. This graph-theoretic approach is certainly related to ours, since spans of graphs are in one-to-one correspondence with spans of ULF functors between the associated free categories (Prop. 2.3), and moreover the two notions of composition agree. Hyland defined a *traced monoidal category* Aut whose objects are natural numbers and whose morphisms $m \rightarrow n$ are finite-state automata (over a fixed alphabet $\Sigma$) equipped with $m$ distinct initial states and $n$ distinct accepting states [Hyl08]. He then exhibited a traced monoidal functor Aut $\rightarrow$ Rat to a category whose arrows are matrices of rational languages, as one direction of Kleene's theorem. It could be interesting to adapt Hyland's analysis to our setting.

### 3. THE CHOMSKY-SCHÜTZENBERGER REPRESENTATION THEOREM

In this section, we give a relatively simple and conceptual proof of the representation theorem, generalized to context-free languages of arrows in an arbitrary category. We begin in §3.1 by explaining how to represent the intersection of a context-free language with a regular language by first taking the *pullback* of a CFG along an NFA. Next, in §3.2, we exhibit a left adjoint to the spliced arrow operad construction, which we call the *contour category* construction. As a direct consequence of this adjunction, we show in §3.3 that every pointed finite species induces a CFG that is universal in a precise sense and that generates a language of *tree contour words*, which are closely related to Dyck words. Finally, in §3.4 we state and prove an appropriate generalization of the representation theorem, which also relies in a crucial way on the strong translation principle.
**3.1. Pulling back context-free grammars along finite-state automata.** To compute the pullback, we apply two lemmas.

**Lemma 3.1.** Suppose given a species $\mathcal{S}$, a functor of operads $p: \mathcal{FS} \to \mathcal{O}$ and a ULF functor of operads $p_Q: \mathcal{Q} \to \mathcal{O}$. In that case, the pullback of $p$ along $p_Q$ in the category of operads is obtained from a corresponding pullback of $\phi: \mathcal{S} \to \mathcal{O}$ along $p_Q: \mathcal{Q} \to \mathcal{O}$ in the category of species:

$$ \phi'=p_Q^*\phi \begin{tikzpicture}[baseline={([yshift=-1ex]current bounding box.center)}] \node (S) at (0,0) {$\mathcal{S}'$}; \node (S') at (1,0) {$\mathcal{S}$}; \node (Q) at (0,-1) {$\mathcal{Q}$}; \node (pQ) at (0,-2) {$p_Q$}; \draw[->] (S) -- (S'); \draw[->] (Q) -- (pQ); \draw[->] (Q) -- (S); \node[above] at (S) {$\psi'$}; \node[above] at (S') {$\phi$}; \node[right] at (pQ) {$\to$}; \node[right] at (Q) {$\to$}; \end{tikzpicture} \in \text{Spec} \quad \left\| \quad \begin{tikzpicture}[baseline={([yshift=-1ex]current bounding box.center)}] \node (FS) at (0,0) {$\mathcal{FS}'$}; \node (FS') at (1,0) {$\mathcal{FS}$}; \node (p) at (0,-1) {$p'$}; \node (pQ) at (0,-2) {$p_Q$}; \draw[->] (FS) -- (FS'); \draw[->] (Q) -- (p); \draw[->] (Q) -- (pQ); \draw[->] (Q) -- (FS); \node[above] at (FS) {$\mathcal{F}\psi'$}; \node[right] at (pQ) {$\to$}; \node[right] at (Q) {$\to$}; \end{tikzpicture} \in \text{Oper} $$

*Proof.* By Proposition 2.23, the pullback of the ULF functor $p_Q$ along the functor of operads $p$ is a ULF functor $\mathcal{Q}' \to \mathcal{FS}$, which must be of the form $\mathcal{F}\psi': \mathcal{FS}' \to \mathcal{FS}$ for some map of species $\psi': \mathcal{S}' \to \mathcal{S}$ by Proposition 2.17. We therefore have a pullback in Oper as on the right above, which is sent to a pullback in Spec by the right adjoint forgetful functor. The unit of the adjunction induces another pullback diagram

$$ \begin{tikzpicture}[baseline={([yshift=-1ex]current bounding box.center)}] \node (S) at (0,0) {$\mathcal{S}'$}; \node (S') at (1,0) {$\mathcal{S}$}; \node (Q) at (0,-1) {$\mathcal{Q}'$}; \node (pQ) at (0,-2) {$p_Q$}; \draw[->] (S) -- (S'); \draw[->] (Q) -- (pQ); \draw[->] (Q) -- (S); \node[above] at (S) {$\psi'$}; \node[right] at (pQ) {$\to$}; \node[right] at (Q) {$\to$}; \node[right] at (Q) {$\to$}; \node[right] at (S') {$\phi'$}; \node[right] at (Q) {$\to$}; \end{tikzpicture} \quad \begin{tikzpicture}[baseline={([yshift=-1ex]current bounding box.center)}] \node (FS) at (0,0) {$\mathcal{FS}'$}; \node (FS') at (1,0) {$\mathcal{FS}$}; \node (p) at (0,-1) {$p_Q$}; \node (pQ) at (0,-2) {$p_Q$}; \draw[->] (FS) -- (FS'); \draw[->] (Q) -- (p); \draw[->] (Q) -- (pQ); \draw[->] (Q) -- (FS); \node[above] at (FS) {$\mathcal{F}\psi'$}; \node[right] at (pQ) {$\to$}; \node[right] at (Q) {$\to$}; \end{tikzpicture} $$

and by composing these

$$ \begin{tikzpicture}[baseline={([yshift=-1ex]current bounding box.center)}] \node (S) at (0,0) {$\mathcal{S}'$}; \node (S') at (1,0) {$\mathcal{S}$}; \node (Q) at (0,-1) {$\mathcal{Q}'$}; \node (pQ) at (0,-2) {$p_Q$}; \draw[->] (S) -- (S'); \draw[->] (Q) -- (pQ); \draw[->] (Q) -- (S); \node[above] at (S) {$\psi'$}; \node[right] at (pQ) {$\to$}; \node[right] at (Q) {$\to$}; \node[right] at (Q) {$\to$}; \node[right] at (S') {$\phi'$}; \node[right] at (Q) {$\to$}; \node[right] at (Q) {$\to$}; \node[right] at (S') {$\phi$}; \node[right] at (Q) {$\to$}; \end{tikzpicture} = \begin{tikzpicture}[baseline={([yshift=-1ex]current bounding box.center)}] \node (S) at (0,0) {$\mathcal{S}'$}; \node (S') at (1,0) {$\mathcal{S}$}; \node (Q) at (0,-1) {$\mathcal{Q}'$}; \node (pQ) at (0,-2) {$p_Q$}; \draw[->] (S) -- (S'); \draw[->] (Q) -- (pQ); \draw[->] (Q) -- (S); \node[above] at (S) {$\psi'$}; \node[right] at (pQ) {$\to$}; \node[right] at (Q) {$\to$}; \node[right] at (Q) {$\to$}; \node[right] at (S') {$\phi'$}; \node[right] at (Q) {$\to$}; \node[right] at (Q) {$\to$}; \node[right] at (S') {$\phi$}; \node[right] at (Q) {$\to$}; \end{tikzpicture} $$

we obtain the desired pullback in the category of species. $\square$

<figure><img src="image_24.png" /></figure>

**Lemma 3.2.** Consider a pullback in the category of species:

$$ \begin{tikzpicture}[baseline={([yshift=-1ex]current bounding box.center)}] \node (S) at (0,0) {$\mathcal{S}'$}; \node (S') at (1,0) {$\mathcal{S}$}; \node (Q) at (0,-1) {$\mathcal{Q}'$}; \node (pQ) at (0,-2) {$p_Q$}; \draw[->] (S) -- (S'); \draw[->] (Q) -- (pQ); \draw[->] (Q) -- (S); \node[above] at (S) {$\psi'$}; \node[right] at (pQ) {$\to$}; \node[right] at (Q) {$\to$}; \node[right] at (Q) {$\to$}; \node[right] at (S') {$\phi'$}; \node[right] at (Q) {$\to$}; \node[right] at (Q) {$\to$}; \node[right] at (S') {$\phi$}; \node[right] at (Q) {$\to$}; \end{tikzpicture} $$

If $\mathcal{S}$ is finite and $\psi$ is finitary (i.e., has finite fibers) then $\mathcal{S}'$ is finite.

*Proof.* The pullback species $\mathcal{S}' = \mathcal{S} \times_T \mathcal{T}'$ admits a simple description: its colors (resp. nodes) are pairs of colors (resp. nodes) from $\mathcal{S}$ and $\mathcal{T}'$ lying over the same color (resp. node) in $\mathcal{T}$. Hence finiteness of $\mathcal{S}'$ follows immediately from the assumption that $\mathcal{S}$ is finite and that $\psi$ has finite fibers. $\square$

<figure><img src="image_25.png" /></figure>
Explicitly, the grammar generating $L \cap L_M$ is defined by starting with the pullback grammar $G' = M^*G$ from Theorem 3.3 above and postcomposing the functor $p'_G: \mathcal{FS}' \to \mathcal{W}Q$ with $\mathcal{W}p_M: \mathcal{W}Q \to \mathcal{W}C$. This grammar admits almost the same concrete description as $G'$ but where the production rules instead take the form

$$ (q, R, q') \to w_0(q_1, R_1, q'_1)w_1 \dots (q_n, R_n, q'_n)w_n $$

for every production rule $R \to w_0R_1w_1 \dots R_nw_n$ of $G$ and sequence of $n+1$ runs $q \to q_1$, $q'_1 \to q_2, \dots, q'_n \to q'$ of $M$ over the respective arrows $w_0, \dots, w_n$. The reader familiar with the classic “Bar-Hillel construction” for combining a CFG with an NFA [BHPS61, Theorem 8.1] may recognize that our construction is very similar, but completely uniform and with the benefit of being derived systematically.

Although it will not be relevant to the representation theorem for categorical CFGs, let us observe that the construction of the pullback of a CFG along a categorical NFA works just as well to construct the pullback of a generalized CFG (in the sense of §1.8) along an operadic NFA.

**Theorem 3.6.** For any gCFG $G = (\mathcal{O}, \mathcal{S}, S, p_G)$ and operadic NFA $M = (\mathcal{O}, \mathcal{Q}, p_M, q_r)$ over the same operad, with $p_G(S) = p_M(q_r)$, there is a gCFG $G' = M^*G$ generating the language $\mathcal{L}_{G'} = p_M^{-1}(\mathcal{L}_G) \cap \mathcal{Q}(q_r)$.

Indeed, the proof is almost identical to the proof of Theorem 3.3, simply omitting the first step where we applied the functor $\mathcal{W}$ before applying Lemma 3.1. We immediately obtain that gCFLs are closed under intersection with regular languages of constants.

**Corollary 3.7.** If $\mathcal{L} \subseteq \mathcal{O}(A)$ is a gCFL and $\mathcal{L}_M \subseteq \mathcal{O}(A)$ is regular then $L \cap \mathcal{L}_M \subseteq \mathcal{O}(A)$ is a gCFL.

**3.2. The contour category of an operad and the contour / splicing adjunction.** In §1.2, we began by explaining how to construct a functor $\mathcal{W}: \mathrm{Cat} \to \mathrm{Oper}$ transforming any category $\mathcal{C}$ into an operad $\mathcal{W}\mathcal{C}$ of spliced arrows of arbitrary arity, which played a central role in our definition of context-free language of arrows in a category. We construct now a left adjoint functor

$$ \mathrm{Oper} \xrightarrow[\mathcal{W}]{\mathcal{C}} \mathrm{Cat} \qquad (3.1) $$

which extracts from any given operad $\mathcal{O}$ a category $\mathcal{C}\mathcal{O}$ whose arrows may be interpreted as “oriented contours” along the boundary of the operations of the operad.

**Definition 3.8.** The contour category $\mathcal{C}\mathcal{O}$ of an operad $\mathcal{O}$ is defined as a quotient of the following free category:

* objects are given by oriented colors $R^\epsilon$ consisting of a color $R$ of $\mathcal{O}$ and an orientation $\epsilon \in \{u, d\}$ (“up” or “down”);

* arrows are generated by pairs $(f, i)$ of an operation $f: R_1, \dots, R_n \to R$ of $\mathcal{O}$ and an index $0 \le i \le n$, defining an arrow $R_i^d \to R_{i+1}^u$ under the conventions that $R_0^d = R^u$ and $R_{n+1}^u = R^d$;
<figure><img src="image_26.png" /><figcaption>Figure 5: Left: interpretation of the generating arrows of the contour category $CO$. Right: interpretation of equations (3.2) and (3.3).</figcaption></figure>

subject to the conditions that $id_{R^u} = (id_R, 0)$ and $id_{R^d} = (id_R, 1)$ as well as the following equations:

$$ (f \circ_i g, j) = \begin{cases} (f, j) & \text{if } j < i \\ (f, i)(g, 0) & \text{if } j = i \\ (g, j - i) & \text{if } i < j < i + m \\ (g, m)(f, i + 1) & \text{if } j = i + m \\ (f, j - m + 1) & \text{if } j > i + m \end{cases} \quad (3.2) $$

$$ (f \circ_i c, j) = \begin{cases} (f, j) & \text{if } j < i \\ (f, i)(c, 0)(f, i + 1) & \text{if } j = i \\ (f, j + 1) & \text{if } j > i \end{cases} \quad (3.3) $$

whenever the left-hand side is well-formed, for every operation $f$, operation $g$ of positive arity $m > 0$, constant $c$, and indices $i$ and $j$ in the appropriate range.

We refer to each generating arrow $(f, i)$ of the contour category $CO$ as a **sector** of the operation $f$. See Fig. 5 for a graphical interpretation of sectors and of the equations on contours seen as compositions of sectors.

The contour construction provides a left adjoint to the spliced arrow construction because a functor of operads $O \to WC$ is entirely described by the data of a pair of objects $(A, B) = (R^u, R^d)$ in $C$ for every color $R$ in $O$ together with a sequence $f_0, f_1, \dots, f_n$ of $n+1$ arrows in $C$, where $f_i : R_i^d \to R_{i+1}^u$ for $0 \le i \le n$ for each operation $f : R_1, \dots, R_n \to R$ of $O$, under the same conventions as above. The equations (3.2) and (3.3) on the generators of $CO$ reflect the equations imposed by the functor of operads $O \to WC$ on the spliced arrows of $C$ appearing as the image of operations in $O$. In that way we transform any functor of operads $O \to WC$ into a functor $CO \to C$ which may be seen as an interpretation of the contours of the operations of $O$ in $C$.

The unit and counit of the contour / splicing adjunction also have nice descriptions. The unit of the adjunction defines, for any operad $O$, a functor of operads $O \to WC O$ that acts on colors by $R \mapsto (R^u, R^d)$, and on operations by sending an operation $f : R_1, \dots, R_n \to R$ of $O$ to the spliced word of sectors $(f, 0) - \dots - (f, n) : (R_1^u, R_1^d), \dots, (R_n^u, R_n^d) \to (R^u, R^d)$. The counit of the adjunction defines, for any category $C$, a functor of categories $CWC \to C$
that acts on objects by $(A, B)^u \mapsto A$ and $(A, B)^d \mapsto B$, and on arrows by sending the $i$th sector of a spliced word to its $i$th word, $(w_0 - \dots - w_n, i) \mapsto w_i$.

**Remark 3.9.** In the case of a free operad over a species $\mathcal{S}$, the contour category $\mathcal{C}\mathcal{F}\mathcal{S}$ admits an even simpler description as a free category $\mathcal{C}\mathcal{F}\mathcal{S} \cong \mathcal{F}\mathcal{C}\mathcal{S}$ generated by the arrows $(x, i) : R_i^d \to R_{i+1}^u$ for every node $x : R_1, \dots, R_n \to R$ of the species $\mathcal{S}$. Indeed, it is easy to verify that there is an analogous adjunction between species and graphs, and that this pair of contour / splicing adjunctions commutes with the pair of respective free / forgetful adjunctions:

$$ \begin{tikzcd}[column sep=2.8em, row sep=2.8em]
    \begin{tikzpicture}[baseline={([yshift=-.5ex]current bounding box.center)}, scale=0.7]
        % Coordinates for vertices
        \coordinate (top) at (0,1);
        \coordinate (bottom) at (0,0);
        \coordinate (left) at (0,0.3);
        \coordinate (right) at (0,0.7);

        % Edges
        \draw[->] (top) -- (left);
        \draw[->] (top) -- (right);
        \draw[->] (bottom) -- (left);
        \draw[->] (bottom) -- (right);

        % Vertices
        \node[circle, fill, inner sep=1.2pt] at (0,0.5) {};
        \node[circle, fill, inner sep=1.2pt] at (0.3,0.5) {};
        \node[circle, fill, inner sep=1.2pt] at (0.7,0.5) {};
        \node[circle, fill, inner sep=1.2pt] at (1,0.5) {};
    \end{tikzpicture} &
    \begin{tikzcd}[column sep=2.8em, row sep=2.8em]
        \begin{tikzpicture}[baseline={([yshift=-.5ex]current bounding box.center)}, scale=0.7]
            % Coordinates for vertices
            \coordinate (top) at (0,1);
            \coordinate (bottom) at (0,0);
            \coordinate (left) at (0,0.3);
            \coordinate (right) at (0,0.7);
            \coordinate (topleft) at (0.3,0.5);
            \coordinate (topright) at (0.7,0.5);
            \coordinate (bottomleft) at (0,0.3);
            \coordinate (bottomright) at (0,0.7);

            % Edges
            \draw[->] (top) -- (left);
            \draw[->] (top) -- (right);
            \draw[->] (bottom) -- (left);
            \draw[->] (bottom) -- (right);
            \draw[->] (topleft) -- (bottomleft);
            \draw[->] (topright) -- (bottomright);

            % Vertices
            \node[circle, fill, inner sep=1.2pt] at (0,0.5) {};
            \node[circle, fill, inner sep=1.2pt] at (0.3,0.5) {};
            \node[circle, fill, inner sep=1.2pt] at (0.7,0.5) {};
            \node[circle, fill, inner sep=1.2pt] at (1,0.5) {};
        \end{tikzpicture} &
        \begin{tikzcd}[column sep=2.8em, row sep=2.8em]
            \begin{tikzpicture}[baseline={([yshift=-.5ex]current bounding box.center)}, scale=0.7]
                % Coordinates for vertices
                \coordinate (top) at (0,1);
                \coordinate (bottom) at (0,0);
                \coordinate (left) at (0,0.3);
                \coordinate (right) at (0,0.7);
                \coordinate (topleft) at (0.3,0.5);
                \coordinate (topright) at (0.7,0.5);
                \coordinate (bottomleft) at (0,0.3);
                \coordinate (bottomright) at (0,0.7);

                % Edges
                \draw[->] (top) -- (left);
                \draw[->] (top) -- (right);
                \draw[->] (bottom) -- (left);
                \draw[->] (bottom) -- (right);
                \draw[->] (topleft) -- (bottomleft);
                \draw[->] (topright) -- (bottomright);

                % Vertices
                \node[circle, fill, inner sep=1.2pt] at (0,0.5) {};
                \node[circle, fill, inner sep=1.2pt] at (0.3,0.5) {};
                \node[circle, fill, inner sep=1.2pt] at (0.7,0.5) {};
                \node[circle, fill, inner sep=1.2pt] at (1,0.5) {};
            \end{tikzpicture} &
            \begin{tikzcd}[column sep=2.8em, row sep=2.8em]
                \begin{tikzpicture}[baseline={([yshift=-.5ex]current bounding box.center)}, scale=0.7]
                    % Coordinates for vertices
                    \coordinate (top) at (0,1);
                    \coordinate (bottom) at (0,0);
                    \coordinate (left) at (0,0.3);
                    \coordinate (right) at (0,0.7);
                    \coordinate (topleft) at (0.3,0.5);
                    \coordinate (topright) at (0.7,0.5);
                    \coordinate (bottomleft) at (0,0.3);
                    \coordinate (bottomright) at (0,0.7);

                    % Edges
                    \draw[->] (top) -- (left);
                    \draw[->] (top) -- (right);
                    \draw[->] (bottom) -- (left);
                    \draw[->] (bottom) -- (right);
                    \draw[->] (topleft) -- (bottomleft);
                    \draw[->] (topright) -- (bottomright);

                    % Vertices
                    \node[circle, fill, inner sep=1.2pt] at (0,0.5) {};
                    \node[circle, fill, inner sep=1.2pt] at (0.3,0.5) {};
                    \node[circle, fill, inner sep=1.2pt] at (0.7,0.5) {};
                    \node[circle, fill, inner sep=1.2pt] at (1,0.5) {};
                \end{tikzpicture} &
                \begin{tikzcd}[column sep=2.8em, row sep=2.8em]
                    \begin{tikzpicture}[baseline={([yshift=-.5ex]current bounding box.center)}, scale=0.7]
                        % Coordinates for vertices
                        \coordinate (top) at (0,1);
                        \coordinate (bottom) at (0,0);
                        \coordinate (left) at (0,0.3);
                        \coordinate (right) at (0,0.7);
                        \coordinate (topleft) at (0.3,0.5);
                        \coordinate (topright) at (0.7,0.5);
                        \coordinate (bottomleft) at (0,0.3);
                        \coordinate (bottomright) at (0,0.7);

                        % Edges
                        \draw[->] (top) -- (left);
                        \draw[->] (top) -- (right);
                        \draw[->] (bottom) -- (left);
                        \draw[->] (bottom) -- (right);
                        \draw[->] (topleft) -- (bottomleft);
                        \draw[->] (topright) -- (bottomright);

                        % Vertices
                        \node[circle, fill, inner sep=1.2pt] at (0,0.5) {};
                        \node[circle, fill, inner sep=1.2pt] at (0.3,0.5) {};
                        \node[circle, fill, inner sep=1.2pt] at (0.7,0.5) {};
                        \node[circle, fill, inner sep=1.2pt] at (1,0.5) {};
                    \end{tikzpicture} &
                \end{tikzcd}
            \end{tikzcd}
        \end{tikzcd}
    \end{tikzcd}
    \tag{3.4} $$

We refer to the generating arrows $(x, i)$ of the contour graph $\mathcal{C}\mathcal{S}$ as **corners** in the sense of the theory of planar maps [Sch15], since geometrically they indeed correspond to the corners of $\mathcal{S}$-rooted trees seen as rooted planar maps. By (3.4), every sector of an operation of $\mathcal{F}\mathcal{S}$ factors uniquely in the contour category $\mathcal{C}\mathcal{F}\mathcal{S}$ as a sequence of corners.

In contrast to the situation for $\mathcal{W}$ (Prop. 2.20), it is *not* the case that $\mathcal{C}$ always preserves the ULF property.

**Remark 3.10.** Consider the category $\mathbf{1} + \mathbf{1}$ with two objects $A$ and $B$ and only identity arrows, and the unique functor $p$ to the terminal category $\mathbf{1}$. We claim that the associated ULF functor of operads $\mathcal{W}p$ induces a functor of categories $\mathcal{C}\mathcal{W}p$ which is not ULF. Consider the two binary operations $f = id_A - id_A - id_A$ and $g = id_A - id_A - id_B$ and the constant $c = id_A$ in $\mathcal{W}(\mathbf{1} + \mathbf{1})$, as well as the binary operations $h = id_* - id_* - id_*$ and the constant $d = id_*$ in $\mathcal{W}\mathbf{1}$. The category $\mathcal{C}\mathcal{W}(\mathbf{1} + \mathbf{1})$ has the sequence of sectors $\alpha = (f, 0)(c, 0)(g, 1)$ as an arrow, which is different from the identity. On the other hand, it is mapped by $\mathcal{C}\mathcal{W}p$ to the sequence $w = (h, 0)(d, 0)(h, 1)$, which is equal thanks to Equation (3.3) to the sector $(h \circ_0 d, 0)$ of the unary operation $h \circ_0 d = id_* - id_*$ of $\mathcal{W}\mathbf{1}$, and hence $w = id_{(*)}$. Since the factorization $id = id \circ id$ in $\mathcal{W}\mathbf{1}$ lifts to two distinct factorizations $\alpha = id \alpha = \alpha \circ id$ in $\mathcal{W}(\mathbf{1} + \mathbf{1})$, $p$ is not ULF.

Still, we can verify that maps of species induce ULF functors between their contour categories, as an immediate consequence of Prop. 2.3 and the factorization (3.4).

**Proposition 3.11.** If $\psi : \mathcal{S} \to \mathcal{T}$ is a map of species, then $\mathcal{C}\mathcal{F}\psi : \mathcal{C}\mathcal{F}\mathcal{S} \to \mathcal{C}\mathcal{F}\mathcal{T}$ is a ULF functor of categories.

### 3.3. The universal context-free grammar of a pointed species, and its associated tree contour language.
Every finite species $\mathcal{S}$ equipped with a color $S$ comes with a universal context-free grammar $(\mathcal{C}\mathcal{F}\mathcal{S}, \mathcal{S}, S, p_{\mathcal{S}})$, characterized by the fact that $p_{\mathcal{S}} : \mathcal{F}\mathcal{S} \to \mathcal{W}\mathcal{C}\mathcal{F}\mathcal{S}$ is the unit of the contour / splicing conjunction. We denote the universal grammar associated to a pointed species $\mathcal{S} := (\mathcal{S}, S)$ by $\text{Univ}_{\mathcal{S}}$. By “universal” context-free grammar, we mean that any categorical context-free grammar $\mathcal{G} = (\mathcal{C}, \mathcal{S}, S, p)$ with the same underlying
<figure><img src="image_27.png" /><figcaption>Figure 6: Left: an $\mathcal{S}$-rooted tree of root color 1 and its corresponding contour word $a_0b_0a_1c_0d_0c_1e_0c_2a_2f_0g_0f_1a_3 : 1^u \to 1^d$. Right: the corresponding Dyck word obtained by splitting each corner of the contour in two pieces.</figcaption></figure>

species and start symbol factors uniquely through $\mathcal{U}\mathcal{N}\mathcal{I}\mathcal{V}_{\mathcal{S}}$ in the sense that there exists a unique functor $q_G : \mathcal{C}\mathcal{F}\mathcal{S} \to \mathcal{C}$ satisfying the equation

$$ \mathcal{F}\mathcal{S} \xrightarrow{p} \mathcal{W}\mathcal{C} = \mathcal{F}\mathcal{S} \xrightarrow{p_S} \mathcal{W}\mathcal{C}\mathcal{F}\mathcal{S} \xrightarrow{Wq_G} \mathcal{W}\mathcal{C} \quad (3.5) $$

We refer to the language of arrows of a universal grammar $\mathcal{U}\mathcal{N}\mathcal{I}\mathcal{V}_{\mathcal{S}}$ as the **tree contour language** associated to a pointed species, denoted $\mathcal{CL}_{\mathcal{S}}$, and to its arrows as **tree contour words**, or more precisely as $\mathcal{S}$-tree contour words. Tree contour words in $\mathcal{CL}_{\mathcal{S}}$ describe the contours of $\mathcal{S}$-rooted trees with root color $S$, see left side of Fig. 6 for an illustration. The factorization above shows that any context-free grammar $G$ is the functorial image of the universal grammar $\mathcal{U}\mathcal{N}\mathcal{I}\mathcal{V}_{\mathcal{S}}$ along the functor of categories $q_G$, whose purpose is to transport each corner of a node in $\mathcal{S}$ to the corresponding arrow in $\mathcal{C}$ as determined by $G$. At the level of languages, we have

**Proposition 3.12.** *The language of a context-free grammar $G$ coincides with the image of its tree contour language, $\mathcal{L}_G = q_G \mathcal{CL}_{\mathcal{S}}$.*

**Example 3.13.** Consider the context-free grammar of Figure 2. The production rules of the universal grammar $\mathcal{U}\mathcal{N}\mathcal{I}\mathcal{V}_{\mathcal{S}}$ may be depicted in traditional CFG syntax as

$$ \begin{aligned} \mathcal{S} &\to 1_0 \mathcal{N} \mathcal{P} 1_1 \mathcal{V} \mathcal{P} 1_2 \\ \mathcal{N} \mathcal{P} &\to 2_0 \\ \mathcal{N} \mathcal{P} &\to 3_0 \\ \mathcal{V} \mathcal{P} &\to 4_0 \mathcal{N} \mathcal{P} 4_1 \end{aligned} $$

where we have written $i_j$ as shorthand for the sector $(x_i, j)$. The language $\mathcal{L}_G$ is then obtained as the image of $\mathcal{CL}_{\mathcal{S}}$ under the functor $q_G : \mathcal{C}\mathcal{F}\mathcal{S} \to \mathcal{F}\mathbb{B}_{\Sigma}$ defined by:

$$ \begin{array}{l} 1_0 \mapsto id \quad 1_1 \mapsto \_ \quad 1_2 \mapsto id \\ 2_0 \mapsto \text{mom} \quad 3_0 \mapsto \text{tom} \quad 4_0 \mapsto \text{loves}_\_ \quad 4_1 \mapsto id \end{array} $$
**Remark 3.14.** The notion of tree contour language makes sense even for infinite species, although in that case the resulting universal grammar $\mathbf{Univ}_{\mathbb{S}}$ is no longer a CFG, having infinitely many nonterminals or infinitely many productions. Still, it may be an interesting object of study. In particular, the tree contour language $\mathbf{Univ}_{(\mathbb{N},*)}$ generated by the terminal species $\mathbb{N}$ with one color * and a single operation of every arity appears to be of combinatorial interest, with words in the language describing the shapes of rooted planar trees with arbitrary node degrees. Nevertheless, from now on when we refer to a “tree contour language” we will always mean the context-free tree contour language generated by a finite pointed species.

**3.4. Representation theorem.** The achievement of the classical Chomsky-Schützenberger representation theorem is to separate any context-free grammar $G = (\Sigma, N, S, P)$ into two independent components:

(1) a context-free grammar $G'$ with only one nonterminal over an alphabet

$$ \Sigma_{2k} = \{ [1,]_1, \dots, [k,]_k \} $$

of size $2k$, for some $k$, which generates Dyck words of balanced brackets describing the shapes of parse trees with nodes labelled by production rules of $G$; and

(2) a finite-state automaton $M$ to check that the edges of these trees may be appropriately colored by the nonterminals of $G$ according to the labels of the nodes specifying the productions.

The original context-free language generated by $G$ is then obtained as the image of the intersection of the Dyck language generated by $G'$ with the regular language recognized by $M$, under a homomorphism $\Sigma_{2k}^* \to \Sigma^*$ that interprets each bracket of the Dyck word by a word in the original alphabet, with some arbitrary choice involved in selecting whether to interpret opening or closing brackets as empty words.

In this section, we give a new proof of the representation theorem, generalized to context-free grammars $G$ over any category $\mathcal{C}$. Since the category $\mathcal{C}$ may have more than one object, the appropriate statement of the representation theorem cannot require the grammar describing the shapes of parse trees to have only one nonterminal. Nonetheless, we can construct one that is $\mathcal{C}$-chromatic in the following sense.

**Definition 3.15.** A categorical context-free grammar $G = (\mathcal{C}, \mathbb{S}, S, p)$ is $\mathcal{C}$-chromatic if the functor $p: \mathcal{F}\mathbb{S} \to \mathcal{W}\mathcal{C}$ is injective on colors.

The nonterminals of a $\mathcal{C}$-chromatic grammar may thus be considered as pairs $(A, B)$ of objects of $\mathcal{C}$.

Moreover, rather than using Dyck words to represent parse trees, we find it more natural to use tree contour words, based on the observation given above in §3.3 that every context-free language may be *canonically* represented as the image of a tree contour language generated by a context-free grammar with the same set of nonterminals. (We will discuss the relationship between contour words and Dyck words as Remark 3.20 below.)

As preparation to our proof of the representation theorem, we establish:

**Proposition 3.16.** Any map of species $\phi: \mathbb{S} \to \mathbb{T}$ factors as

$$ \mathbb{S} \xrightarrow{\phi} \mathbb{T} = \mathbb{S} \xrightarrow{\phi_{\text{colors}}} \phi_{\mathcal{C}} \mathbb{S} \xrightarrow{\phi_{\text{nodes}}} \mathbb{T} $$

for some species $\phi_{\mathcal{C}} \mathbb{S}$ such that $\phi_{\text{colors}}$ is the identity on nodes and surjective on colors and $\phi_{\text{nodes}}$ is injective on colors.
*Proof.* A map of species is given by a commutative diagram as on the right below:

<figure><img src="image_28.png" /></figure>

After taking the epi-mono factorization of $\phi_C$,

$$C_S \xrightarrow{\phi_C} C_T = C_S \xrightarrow{e} \phi_C C_S \xrightarrow{m} C_T$$

we obtain the desired factorization of $\phi$:

<figure><img src="image_29.png" /></figure>

**Lemma 3.17.** Let $\psi : \mathcal{S} \to \mathcal{S}'$ be a map of species, let $p_S : \mathcal{F}\mathcal{S} \to \mathcal{W}\mathcal{C}\mathcal{F}\mathcal{S}$ and $p_{S'} : \mathcal{F}\mathcal{S}' \to \mathcal{W}\mathcal{C}\mathcal{F}\mathcal{S}'$ be the underlying functors of the universal grammars derived from the unit of the contour / splicing adjunction, and let

$$ \begin{tikzcd} \mathcal{F}\mathcal{S} \arrow[r, "\mathcal{F}\psi"] \arrow[d, "p_S"] & \mathcal{F}\mathcal{S}' \arrow[d, "p_{S'}"] \\ \mathcal{W}\mathcal{C}\mathcal{F}\mathcal{S} \arrow[r, "\psi"] & \mathcal{W}\mathcal{C}\mathcal{F}\mathcal{S}' \end{tikzcd} \qquad (3.6) $$

be the associated naturality square. If $\psi$ is injective on nodes then the canonical functor of operads from $\mathcal{F}\mathcal{S}$ to the pullback of $p_{S'}$ along $\mathcal{W}\mathcal{C}\mathcal{F}\psi$ is fully faithful.

*Proof.* The naturality square (3.6) in Oper induces a commutative square in Spec:

$$ \begin{tikzcd} \mathcal{S} \arrow[r, "\psi"] \arrow[d, "\phi_S"] & \mathcal{S}' \arrow[d, "\phi_{S'}"] \\ \mathcal{W}\mathcal{C}\mathcal{F}\mathcal{S} \arrow[r, "\psi"] & \mathcal{W}\mathcal{C}\mathcal{F}\mathcal{S}' \end{tikzcd} \qquad (3.7) $$

Neither (3.6) nor (3.7) will in general be a pullback square. However, by Lemma 3.1, we know that the pullback of $p_{S'}$ along $\mathcal{W}\mathcal{C}\mathcal{F}\psi$ is obtained from a corresponding pullback in the category of species

$$ \begin{tikzcd} \mathcal{T} \arrow[r, "\pi"] \arrow[d, "\rho"] & \mathcal{S}' \arrow[d, "\phi_{S'}"] \\ \mathcal{W}\mathcal{C}\mathcal{F}\mathcal{S} \arrow[r, "\psi"] & \mathcal{W}\mathcal{C}\mathcal{F}\mathcal{S}' \end{tikzcd} \quad \| \quad \begin{tikzcd} \mathcal{F}\mathcal{T} \arrow[r, "\mathcal{F}\pi"] \arrow[d, "r"] & \mathcal{F}\mathcal{S}' \arrow[d, "p_{S'}"] \\ \mathcal{W}\mathcal{C}\mathcal{F}\mathcal{S} \arrow[r, "\psi"] & \mathcal{W}\mathcal{C}\mathcal{F}\mathcal{S}' \end{tikzcd} \qquad (3.8) $$

where the pullback species $\mathcal{T}$ has colors defined as tuples $(R, (R_1^u, R_2^d))$ of a color $R$ of $\mathcal{S}'$ and colors $R_1, R_2$ of $\mathcal{S}$ such that $\psi(R_1) = \psi(R_2) = R$, and where the $n$-ary nodes of $\mathbb{R}$ are defined as pairs $(x, f)$ of a $n$-ary node $x$ of $\mathcal{S}'$ and an $n$-ary operation $f$ of $\mathcal{W}\mathcal{C}\mathcal{F}\mathcal{S}$,
necessarily of the form $f = (y, 0) - \dots - (y, n)$ for $y$ the unique $n$-ary node of $\mathbb{S}$ such that $\psi(y) = x$, by assumption that $\psi: \mathbb{S} \to \mathbb{S}'$ is injective on nodes. The canonical map of species $\mathbb{S} \to \mathbb{T}$ induced by (3.7) and the left-hand side of (3.8) transports every color $R$ of $\mathbb{S}$ to the color $((\psi(R))^u, \psi(R)^d), R)$ and every $n$-ary node $y$ of $\mathbb{S}$ to the $n$-ary node $(\psi(y), (y, 0) - \dots - (y, n))$ of $\mathbb{T}$. From this follows that the canonical map of species $\mathbb{S} \to \mathbb{T}$ is injective on colors and bijective on nodes. Moreover, there are no nodes in $\mathbb{T}$ whose colors are outside of the image of $\mathbb{S}$. We conclude that the canonical functor of operads $\mathcal{F}\mathbb{S} \to \mathcal{F}\mathbb{T}$ induced by (3.6) and the right-hand side of (3.8) is fully faithful. $\square$

Now, let $G = (C, \mathbb{S}, S, p)$ be any categorical context-free grammar, and using Prop. 3.16 consider the corresponding $C$-chromatic grammar $G_{\text{nodes}} = (C, \phi_C \mathbb{S}, (A, B), p_{\text{nodes}})$, where $p(S) = (A, B)$. Applying the factorization (3.5), we build the commutative diagram below

$$ \begin{tikzcd}[column sep=2.8em, row sep=2.8em]
    \mathcal{F}\mathbb{S} \arrow[r, "\mathcal{F}\phi_{\text{colors}}"] & \mathcal{F}\phi_C \mathbb{S} \arrow[d, "p_S"] \\
    W\mathcal{C}\mathcal{F}\mathbb{S} \arrow[r, "W\mathcal{C}\mathcal{F}\phi_{\text{colors}}"', "Wq_G"] & W\mathcal{C}\mathcal{F}\phi_C \mathbb{S} \arrow[d, "p_{\phi_C \mathbb{S}}"] \\
    W\mathcal{C} \arrow[u, "Wq_G", "W\phi_C"] & W\mathcal{C} \arrow[u, "Wq_{G_{\text{nodes}}}", "W\phi_{\text{nodes}}"]
\end{tikzcd} \quad (3.9) $$

combining a naturality square with a triangle whose commutativity follows from equation $\phi = \phi_{\text{colors}} \phi_{\text{nodes}}$ and the contour / splicing adjunction. Note also that $p_{\text{colors}} := C\mathcal{F}\phi_{\text{colors}}$ is a ULF functor of categories by Prop. 3.11, and finitary because $\phi_{\text{colors}}$ is finitary (and even finite). Therefore pairing the functor with the initial state $S^u$ and accepting state $S^d$ defines a finite-state automaton $M_{\text{colors}} = (C\mathcal{F}\phi_C \mathbb{S}, C\mathcal{F}\mathbb{S}, p_{\text{colors}}, S^u, S^d)$. By the intersection construction (Cor. 3.5) together with Lemma 3.17 and the strong translation principle (Prop. 1.14), we deduce that

$$ p_{\text{colors}} \mathcal{C}\dot{\mathbb{S}} = \mathcal{C}\mathcal{L}_{\phi_C \dot{\mathbb{S}}} \cap \mathcal{L}_{M_{\text{colors}}}. $$

Finally, using that $G$ is the image of the universal grammar $\text{Univ}_{\dot{\mathbb{S}}}$ and considering the commutative diagram (3.9), we conclude that

$$ \mathcal{L}_G = q_G \mathcal{C}\dot{\mathbb{S}} = q_{G_{\text{nodes}}} p_{\text{colors}} \mathcal{C}\dot{\mathbb{S}} = q_{G_{\text{nodes}}} (\mathcal{C}\mathcal{L}_{\phi_C \dot{\mathbb{S}}} \cap \mathcal{L}_{M_{\text{colors}}}) \quad (3.10) $$

and thus derive our generalized Chomsky-Schützenberger representation theorem.

**Theorem 3.18.** A language $L \subseteq C(A, B)$ is a CFL of arrows iff it is a functorial image of the intersection of a $C$-chromatic tree contour language with a regular language.

**Example 3.19.** For the original example of Figure 2, the colors-nodes factorization

$$ \mathbb{S} \xrightarrow{\phi} W\Sigma = \mathbb{S} \xrightarrow{\phi_{\text{colors}}} \phi_C \mathbb{S} \xrightarrow{\phi_{\text{nodes}}} W\Sigma $$

of Prop. 3.16 may be visualized as below:
<figure><img src="image_30.png" /></figure>

Some examples of contour words in the tree contour language $\mathcal{CL}_{\phi_C \hat{s}}$ and their corresponding images under the functor $q_{G_{\text{nodes}}}$ include:

<figure><img src="image_31.png" /></figure>

Observe that only the first contour word encodes a valid parse tree mapping to a word of the language. Finally, the “coloring automaton” $M_{\text{colors}}$ derived by the contour construction may be depicted by the following transition diagram:

<figure><img src="image_32.png" /></figure>

The reader can verify that the automaton only accepts the first contour word above.

**Remark 3.20.** We view the use of contour words rather than Dyck words in Theorem 3.18 as a mild improvement of the original theorem by Chomsky and Schützenberger, since it removes the need for choosing arbitrarily whether to erase left brackets or right brackets in defining the homomorphism. However, there is a close relationship between tree contour words and Dyck words, and the original representation can be recovered from formula (3.10). We now sketch this for the classical case of context-free languages of words over an alphabet $\Sigma$. As suggested by the right-hand side of Figure 6, there is a simple mapping $s$ (for *subdivide*) from contour words to Dyck words defined by translating each corner $(x, i)$ of an $n$-ary node
$x$ into a pair of brackets, as follows:

$$s = (x, i) \mapsto \left\{ \begin{array}{ll} [0]^x_0 & \text{if } i = n = 0 \\ [0]^x_1 & \text{if } i = 0 \text{ and } n > 0 \\ ]^x_i[i+1] & \text{if } 0 < i < n \\ ]^x_n^0 & \text{if } 0 < i = n \end{array} \right.$$

It is easy to check that the image of a tree contour word under this translation is a well-bracketed word over the alphabet containing a pair of brackets $[^x_i$ and $]^x_i$ for every n-ary node $x$ and index $0 \le i \le n$. Indeed, every production rule

$$R \to (x, 0) R_1 (x, 1) \dots R_n (x, n)$$

of the universal grammar $\mathbf{Univ}_{\hat{S}}$ is translated to a production rule

$$R \to [0]^x [1]^x R_1 [1]^x [2]^x \dots R_n [n]^x [0]^x \quad (3.11)$$

which manifestly preserves well-bracketing. Let us refer to the language of well-bracketed words generated by the collection of productions (3.11), indexed by nodes $x: R_1, \dots, R_n \to R$ of a species $\mathcal{S}$ with start symbol $S \in \mathcal{S}$, as the $\dot{S}$-Dyck language $\mathcal{DL}_{\hat{S}}$. By construction, it is immediate that

$$s(\mathcal{DL}_{\hat{S}}) = \mathcal{DL}_{\hat{S}} \quad (3.12)$$

for every pointed species $\dot{S}$. Conversely, there are two natural ways to define a translation from $\dot{S}$-Dyck words back to $\hat{S}$-contour words: the “green” translation

$$g = [i]^x \mapsto \left\{ \begin{array}{ll} (x, 0) & \text{if } i = 0 \\ \epsilon & \text{if } i > 0 \end{array} \right. \quad [i]^x \mapsto \left\{ \begin{array}{ll} \epsilon & \text{if } i = 0 \\ (x, i) & \text{if } i > 0 \end{array} \right. ,$$

which corresponds to interpreting the green arrows in the right hand side of Figure 6 as corners and erasing the red arrows, or alternatively the “red” translation

$$r = [i]^x \mapsto \left\{ \begin{array}{ll} \epsilon & \text{if } i = 0 \\ (x, i) & \text{if } i > 0 \end{array} \right. \quad [i]^x \mapsto \left\{ \begin{array}{ll} (x, 0) & \text{if } i = 0 \\ \epsilon & \text{if } i > 0 \end{array} \right. ,$$

which does the opposite. Both translations are left inverse to the s-translation in the sense that $g \circ s = r \circ s = id$. It follows that if we define the homomorphism $h$ from bracketed words to $\Sigma^*$ to be either $h = q_{G_{\text{nodes}}} \circ g$ or $h = q_{G_{\text{nodes}}} \circ r$, then we can derive that

$$\begin{align}
\mathcal{L}_G &= q_{G_{\text{nodes}}} (\mathcal{L}_{\phi_C \dot{S}} \cap \mathcal{L}_{M_{\text{colors}}}) && \text{by (3.10)} \\
&= h(s(\mathcal{L}_{\phi_C \dot{S}} \cap \mathcal{L}_{M_{\text{colors}}})) && \text{since } g \circ s = r \circ s = id \\
&= h(\mathcal{D}\mathcal{L}_{\phi_C \dot{S}} \cap s(\mathcal{L}_{M_{\text{colors}}})) && \text{by (3.12) and injectivity of } s. \tag{3.13}
\end{align}$$

Next, it is not hard to verify that the image $s(\mathcal{L}_{M_{\text{colors}}})$ of the regular language of the coloring automaton under the s-translation is itself a regular language (just use a pair of transitions to simulate each transition of $M_{\text{colors}}$). We have therefore derived that every context-free language is a homomorphic image of the intersection of a $\phi_C \dot{S}$-Dyck language (for some $\dot{S}$) with a regular language.

Words in $\mathcal{DL}_{\phi_C \dot{S}}$ are generated by productions of the form

$$S \to [0]^x [1]^x S [1]^x [2]^x \dots S [n]^x [0]^x \quad (3.14)$$

for every node $x: R_1, \dots, R_n \to R$ in $\mathcal{S}$ (i.e., replacing every non-terminal in (3.11) by the unique start symbol $S$). Now let $k = \sum_{x \in \mathcal{S}} 1 + |x|$ be the sum of the arity-plus-one of every
node in $\mathbb{S}$, and let us write $\mathcal{D}\mathcal{L}_k$ for the language of unrestricted Dyck words over the family of $k$ different pairs of brackets labelled $[^x_i$ and $]^x_i$ for $0 \le i \le n = |x|$ as above. One can prove by induction that an arbitrary Dyck word is a $(\phi_C \dot{S})$-Dyck word just in case it satisfies the following conditions:

(1) it starts with $[^x_0$ for some $x$;

(2) every $[^x_0$ is immediately followed by either $]^x_0$ (if $|x| = 0$) or $]^x_1$ (if $|x| > 0$);

(3) for $i > 0$, every $]^x_i$ is followed by an opening bracket $]^y_0$ for some $y$;

(4) for $i > 0$, every $]^x_i$ is immediately followed by either $]^x_{i+1}$ (if $i < |x|$) or $]^x_0$ (if $i = |x|$);

(5) $]^x_0$ is never followed by an opening bracket $]^y_i$.

Since these conditions can be checked by a simple finite automaton $M_{\text{index}}$, we have that

$$ \mathcal{D}\mathcal{L}_{\phi_C \dot{S}} = \mathcal{D}\mathcal{L}_k \cap \mathcal{L}_{M_{\text{index}}} \qquad (3.15) $$

from which the Chomsky-Schützenberger representation theorem follows by substituting (3.15) into (3.13) and using that regular languages are closed under intersection.

Although we have limited our attention here to the classical result, we believe that the connection between contour words and Dyck words deserves a deeper categorical analysis, which we leave to future work. The s-translation has a clear geometric interpretation as decomposing each corner of the contour into alternating actions of walking along an edge and turning around a node (we again refer the reader to Figure 6). In the theory of maps on surfaces, an analogous decomposition is used to embed the *oriented cartographic group* into the *unoriented cartographic group* (cf. [SV90, JS94]), which suggests that there may be a corresponding refinement of the contour category construction.

**3.5. Related work.** As already mentioned, our proof that (generalized) context-free languages are closed under intersection with regular languages may be seen as a decomposition of the Bar-Hillel construction [BHPS61]. In a similar spirit, Ludmann, Pogodalla, and De Groote have recently analyzed Kanazawa’s proof that languages generated by abstract categorial grammars are closed under intersection with regular languages, and shown that it defines a pullback in an appropriate category [LPdG22].

The representation theorem is one of many results appearing in Chomsky and Schützenberger’s joint article on “The algebraic theory of context-free languages” [CS63]. The theorem was sketched in a technical report by Chomsky [Cho62] with attribution to their collaboration, while the first detailed proof seems to have been by Schützenberger [Sch63]. The original formulation used two-sided$^6$ Dyck languages, but would have worked just as well with ordinary (one-sided) Dyck languages and most standard treatments of the theorem now adopt that formulation [Koz97, §G]. Numerous variations of the representation theorem and extensions to other classes of languages have since been established, see [CS16] for an overview and bibliography.

The contour / splicing adjunction is fundamental to our analysis of the representation theorem, providing an unexpected geometric lens on context-free languages that is evocative of Girard’s geometry of interaction. Although the adjunction is not identified, this geometric perspective is also apparent in Slavnov’s recent work [Sla20] (inspired both by abstract

<footnote>$^6$The two-sided Dyck language on an alphabet of $2n$ letters $x_{\pm i}$ ($1 \le i \le n$) may be defined as the kernel of the canonical homomorphism $\phi: \text{Mon}(x_{-n}, \dots, x_{-1}, x_{+1}, \dots, x_{+n}) \to \text{Grp}(x_1, \dots, x_n)$ from the free monoid on $2n$ generators to the free group on $n$ generators defined by $\phi(x_{+i}) = x_i$ and $\phi(x_{-i}) = x_i^{-1}$.</footnote>
categorial grammars and by linear logic proof-nets), wherein he constructs a compact closed monoidal category of *word cobordisms* reminiscent of the operad of spliced words.

After the original version of this article was published [MZ22], the contour / splicing adjunction was subsequently analyzed and extended by Earnshaw, Hefford, and Román, who described applications to process algebra [EHR24, Rom23]. They noticed that the splicing functor $\mathcal{W}: \text{Cat} \to \text{Oper}$ is closely related to a construction by Day and Street [DS04, Example 7.3], of a canonical promonoidal structure on $C^{\text{op}} \otimes C$ for any $\mathcal{V}$-enriched category $C$. We have also been further exploring the 2-categorical aspects of the adjunction between categories and operads in ongoing work with Peter Faul.

## 4. CONCLUSION

We have seen that the classical notions of context-free grammar and of nondeterministic finite-state automaton can be reformulated and generalized in a categorical setting, in a way that seems to have significant explanatory power. Clearly many natural questions arise in regards to integrating the deep body of work on automata theory and formal language theory within this setting, some of which we have already signalled. Another obvious question is how to define pushdown automata over categories. We find it remarkable that when one considers the nodes of a species as the production rules of a context-free grammar, the corners of its contour category correspond exactly to the *items* used in LR parsing and Earley parsing [Knu65, Ear70], which we think suggests contour categories have a role to play in analyzing left-to-right parsing algorithms from a categorical perspective. One of our original motivations for studying context-free grammars as functors and looking at parsing as a lifting problem was to develop a better understanding of the universal properties of algorithms like these, having in mind that such an understanding could then be transferred to other settings including type checking and type inference algorithms. This attempt at unification is supported by the emergence of a number of categorical and fibrational structures which seem to connect these different kinds of symbolic systems, revealing that they are founded on many of the same basic patterns.

## ACKNOWLEDGMENT

We thank Peter Faul for many exciting discussions of the contour / splicing adjunction, Thea Li for stimulating conversations about determinization and $\epsilon$-removal for categorical automata, and Farzad Jafarrahmani for fruitful interactions related to the material in [MZ25]. We also gratefully acknowledge Bryce Clarke for many helpful insights into the contents of the paper, which improved some of the proofs, and for telling us about [Par12]. We thank Daniela Petrişan, Thomas Colcombet, and the other members of the working group on "Categories for Automata and Language Theory" at IRIF for helping us to better understand the relationship with [CP20] and with other works. We thank Benjamin Steinberg for telling us about [Jon96], which led us to [TSG88, WT86]. We gratefully thank the LMCS referees for numerous comments that improved the presentation in the article. Finally, special thanks to Hayo Thielecke for giving a very lucid presentation of LL and LR parsing using abstract machines in 2017, which was one of our original sources of inspiration.
REFERENCES

[AL19] Benedikt Ahrens and Peter LeFanu Lumsdaine. Displayed categories. *Logical Methods in Computer Science*, 15(1), 2019. doi:10.23638/LMCS-15(1:20)2019.

[Bed88] M.A. Bednarczyk. *Categories of asynchronous systems*. PhD thesis, University of Sussex, 1988.

[Bén72] Jean Bénabou. 2-dimensional limits and colimits of distributors (or how to glue together categories). Oberwolfach Workshop Report 30, 1972. URL: https://oda.mfo.de/handle/mfo/1575.

[Bén00] Jean Bénabou. Distributors at work. Notes from a course at TU Darmstadt in June 2000, taken by Thomas Streicher, 2000. URL: https://www2.mathematik.tu-darmstadt.de/~streicher/FIBR/DiWo.pdf.

[BF00] Marta Bunge and Marcelo P. Fiore. Unique factorisation lifting functors and categories of linearly-controlled processes. *Mathematical Structures in Computer Science*, 10:137–163, 2000. doi:10.1017/S0960129599003023.

[BHPS61] Y. Bar-Hillel, M. Perles, and E. Shamir. On formal properties of simple phrase structure grammars. *Z. Phonetik, Sprachwissen. Kommun.*, 14(2):143–172, 1961. doi:doi:10.1524/stuf.1961.14.14.143.

[BJT97] Hans-Joachim Baues, Mamuka Jibladze, and Andy Tonks. Cohomology of monoids in monoidal categories. *Contemporary Mathematics*, 202, 1997. doi:10.1090/conm/202/02597.

[BLL98] F. Bergeron, G. Labelle, and P. Leroux. *Combinatorial Species and Tree-Like Structures*. Cambridge University Press, 1998. Translated by Margaret Readdy. doi:10.1017/CBO9781107325913.

[BM06] Nicolas Baudru and Rémi Morin. Unfolding synthesis of asynchronous automata. In Dima Grigoriev, John Harrison, and Edward A. Hirsch, editors, *Computer Science – Theory and Applications*, pages 46–57, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg.

[BN00] Marta Bunge and Susan Niefeld. Exponentiability and single universes. *Journal of Pure and Applied Algebra*, 148:217–250, 2000. doi:10.1016/S0022-4049(98)00172-8.

[CDG+08] Hubert Comon, Max Dauchet, Rémi Gilleron, Florent Jacquemard, Denis Lugiez, Christof Löding, Sophie Tison, and Marc Tommasi. Tree Automata Techniques and Applications, 2008. URL: https://hal.inria.fr/hal-03367725.

[CE12] Bruno Courcelle and Joost Engelfriet. *Graph Structure and Monadic Second-Order Logic - A Language-Theoretic Approach*, volume 138 of *Encyclopedia of mathematics and its applications*. Cambridge University Press, 2012. doi:10.1017/CBO9780511977619.

[Cho62] Noam Chomsky. Context-free grammars and push-down storage. Quarterly Progress Report 65, Research Laboratory of Electronics, M.I.T., 1962. URL: http://hdl.handle.net/1721.1/53697.

[CP20] Thomas Colcombet and Daniela Petrișan. Automata minimization: a functorial approach. *Logical Methods in Computer Science*, 16(1):32:1–32:28, 2020. doi:10.23638/LMCS-16(1:32)2020.

[CS63] N. Chomsky and M. P. Schützenberger. The algebraic theory of context-free languages. In P. Braffort and D. Hirschberg, editors, *Computer Programming and Formal Systems*, volume 35 of *Studies in Logic and the Foundations of Mathematics*, pages 118–161. North-Holland, 1963. doi:10.1016/S0049-237X(08)72023-8.

[CS16] Stefano Crespi-Reghizzi and Pierluigi San Pietro. An enduring trail of language characterizations via homomorphism (talk), March 21–25 2016. Conference dedicated to the scientific legacy of M. P. Schützenberger (Bordeaux). URL: https://mps2016.labri.fr/archives/crespi.pdf.

[dG01] Philippe de Groote. Towards abstract categorial grammars. In *Association for Computational Linguistic, 39th Annual Meeting and 10th Conference of the European Chapter, Proceedings of the Conference, July 9-11, 2001, Toulouse, France*, pages 148–155. Morgan Kaufmann Publishers, 2001. doi:10.3115/1073012.1073045.

[dGP04] Philippe de Groote and Sylvain Pogodalla. On the expressive power of abstract categorial grammars: Representing context-free formalisms. *J. Log. Lang. Inf.*, 13(4):421–438, 2004. doi:10.1007/s10849-004-2114-x.

[DS02] Manfred Droste and R. M. Shortt. From Petri nets to automata with concurrency. *Appl. Categorical Struct.*, 10(2):173–191, 2002. doi:10.1023/A:1014305610452.

[DS04] Brian Day and Ross Street. Quantum categories, star autonomy, and quantum groupoids. In *Galois Theory, Hopf Algebras, and Semiabelian Categories*, pages 187–225. American Mathematical Society, 2004.

[Ear70] Jay Earley. An efficient context-free parsing algorithm. *Commun. ACM*, 13(2):94–102, 1970. doi:10.1145/362007.362035.
[EHR24] Matt Earnshaw, James Hefford, and Mario Román. The produoidal algebra of process decomposition. In Aniello Murano and Alexandra Silva, editors, *32nd EACSL Annual Conference on Computer Science Logic, CSL 2024, February 19-23, 2024, Naples, Italy*, volume 288 of LIPIcs, pages 25:1–25:19, 2024. doi:10.4230/LIPICS.CSL.2024.25.

[Eil74] Samuel Eilenberg. *Automata, Languages, and Machines: volume A*. Pure and applied mathematics. Academic Press, 1974.

[ES22] Matthew Earnshaw and Pawel Sobociński. Regular monoidal languages. In Stefan Szeider, Robert Ganian, and Alexandra Silva, editors, *47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022, August 22-26, 2022, Vienna, Austria*, volume 241 of LIPIcs, pages 44:1–44:14, 2022. doi:10.4230/LIPICS.MFCS.2022.44.

[FGHW08] M. Fiore, N. Gambino, M. Hyland, and G. Winskel. The cartesian closed bicategory of generalised species of structures. *Journal of the London Mathematical Society*, 77(1):203–220, 2008. doi:10.1112/jlms/jdm096.

[FJSZ22] Uli Fahrenberg, Christian Johansen, Georg Struth, and Krzysztof Ziemianski. A Kleene theorem for higher-dimensional automata. In Bartek Klin, Slawomir Lasota, and Anca Muscholl, editors, *33rd International Conference on Concurrency Theory, CONCUR 2022, September 12-16, 2022, Warsaw, Poland*, volume 243 of LIPIcs, pages 29:1–29:18, 2022. doi:10.4230/LIPICS.CONCUR.2022.29.

[GM10] Eric Goubault and Samuel Mimram. Formal relationships between geometrical and classical models for concurrency. In Lisbeth Fajstrup, Eric Goubault, and Martin Raussen, editors, *Proceedings of the workshop on Geometric and Topological Methods in Computer Science, GETCO 2010, Aalborg, Denmark, January 11-15, 2010*, volume 283 of ENTCS, pages 77–109. Elsevier, 2010. doi:10.1016/J.ENTCS.2012.05.007.

[Gue20] Léonard Guetta. Polygraphs and discrete Conduché $\omega$-functors. *Higher Structures*, 4(2):134–166, 2020. doi:10.21136/HS.2020.11.

[HM00] Jean-François Husson and Rémi Morin. On recognizable stable trace languages. In Jerzy Tiuryn, editor, *Proceedings of the 3rd International Conference on Foundations of Software Science and Computation Structures, FOSSACS 2000, Berlin, Germany, March 25 - April 2, 2000*, volume 1784 of LNCS, pages 177–191. Springer, 2000. doi:10.1007/3-540-46432-8\_12.

[HMU07] John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. *Introduction to automata theory, languages, and computation, 3rd Edition*. Pearson international edition. Addison-Wesley, 2007.

[Hyl08] Martin Hyland. Abstract and concrete models for recursion. In O. Grumberg, T. Nipkow, and C. Pfaller, editors, *Proceedings of the NATO Advanced Study Institute on Formal Logical Methods for System Security and Correctness*, pages 175–198. IOS Press, 2008.

[Joh99] Peter Johnstone. A note on discrete Conduché fibrations. *Theory and Applications of Categories*, 5(1):1–11, 1999. URL: http://www.tac.mta.ca/tac/volumes/1999/n1/5-01abs.html.

[Jon96] Peter R Jones. Profinite categories, implicit operations and pseudovarieties of categories. *Journal of Pure and Applied Algebra*, 109(1):61–95, 1996. doi:10.1016/0022-4049(95)00074-7.

[Joy81] André Joyal. Une théorie combinatoire des séries formelles. *Advances in Mathematics*, 42(1):1–82, 1981. doi:10.1016/0001-8708(81)90052-9.

[Joy86] André Joyal. Foncteurs analytiques et espèces de structures. In Gilbert Labelle and Pierre Leroux, editors, *Combinatoire énumérative*, Lecture Notes in Mathematics, pages 126–159, Berlin, Heidelberg, 1986. Springer Berlin Heidelberg. doi:10.1007/BFb0072514.

[JS94] Gareth A. Jones and David Singerman. Maps, hypermaps, and triangle groups. In L. Schneps, editor, *The Grothendieck Theory of Dessins d'Enfants*, number 200 in London Mathematical Society Lecture Note Series. Cambridge University Press, 1994. doi:10.1017/CBO9780511569302.006.

[Knu65] Donald E. Knuth. On the translation of languages from left to right. *Information and Control*, 8(6):607–639, 1965. doi:10.1016/S0019-9958(65)90426-2.

[Koz97] Dexter Kozen. *Automata and Computability*. Undergrad. texts in comp. science. Springer, 1997.

[KSW97] Piergiulio Katis, Nicoletta Sabadini, and Robert F. C. Walters. Span(Graph): A categorical algebra of transition systems. In *Proceedings of the 6th International Conference on Algebraic Methodology and Software Technology, AMAST '97*, page 307–321, Berlin, Heidelberg, 1997. Springer-Verlag.
[Lam89] Joachim Lambek. Multicategories revisited. *Contemporary Mathematics*, 92:217–239, 1989. doi: 10.1090/conm/092.

[Law86] F. W. Lawvere. State categories and response functors. Unpublished, May 1986.

[Lee89] René Leermakers. How to cover a grammar. In Julia Hirschberg, editor, *27th Annual Meeting of the Association for Computational Linguistics, 26-29 June 1989, University of British Columbia, Vancouver, BC, Canada, Proceedings*, pages 135–142. ACL, 1989. doi:10.3115/981623.981640.

[Lei04] Tom Leinster. *Higher Operads, Higher Categories*, volume 298 of *London Mathematical Society Lecture Note Series*. Cambridge University Press, 2004. doi:10.1017/CB09780511525896.

[LL09] Martin Lange and Hans Leiß. To CNF or not to CNF? An efficient yet presentable version of the CYK algorithm. *Informatica Didact.*, 8, 2009. URL: https://www.informaticadidactica.de/index.php?page=LangeLeiss2009_en.

[LM10] F. W. Lawvere and M. Menni. The Hopf algebra of Möbius intervals. *Theory and Applications of Categories*, 24(10):221–265, 2010. URL: http://www.tac.mta.ca/tac/volumes/24/10/24-10abs.html.

[LPdG22] Pierre Ludmann, Sylvain Pogodalla, and Philippe de Groote. Multityped abstract categorial grammars and their composition. In Agata Ciabattoni, Elaine Pimentel, and Ruy J. G. B. de Queiroz, editors, *Logic, Language, Information, and Computation*, pages 105–122, 2022. doi:10.1007/978-3-031-15298-6_7.

[Maz89] Antoni Mazurkiewicz. Basic notions of trace theory. In J. W. de Bakker, W. P. de Roever, and G. Rozenberg, editors, *Linear Time, Branching Time and Partial Order in Logics and Models for Concurrency*, pages 285–363, Berlin, Heidelberg, 1989. Springer Berlin Heidelberg.

[Mel21] Paul-André Melliès. Asynchronous template games and the Gray tensor product of 2-categories. In *Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2021, Roma, Italy, 2021*, doi:10.1109/LICS52264.2021.9470758.

[MM07] Paul-André Mellies and Samuel Mimram. Asynchronous games: innocence without alternation. In *Proceedings of the 18th International Conference on Concurrency Theory, CONCUR 2007*, volume 4703 of LNCS, pages 395–411. Springer, 2007. doi:10.1007/978-3-540-74407-8_27.

[MN24] Vincent Moreau and Lê Thành Dung Nguyên. Syntactically and semantically regular languages of lambda-terms coincide through logical relations. In *32nd EACSL Annual Conference on Computer Science Logic, CSL 2024, February 19-23, 2024, Naples, Italy, LIPIcs*, 2024. doi:10.4230/LIPICS.CSL.2024.40.

[Mor05] Rémi Morin. Concurrent automata vs. asynchronous systems. In Joanna Jedrzejowicz and Andrzej Szepietowski, editors, *Mathematical Foundations of Computer Science 2005, 30th International Symposium, MFCS 2005, Gdansk, Poland, August 29 - September 2, 2005, Proceedings*, volume 3618 of *Lecture Notes in Computer Science*, pages 686–698. Springer, 2005. doi:10.1007/11549345\_59.

[MSS02] Martin Markl, Steve Schnider, and Jim Stasheff. *Operads in Algebra, Topology and Physics*, volume 96 of *Mathematical Surveys and Monographs*. American Mathematical Society, 2002. doi:10.1090/surv/096.

[MZ13] Paul-André Melliès and Noam Zeilberger. Type refinement and monoidal closed bifibrations. Unpublished, arXiv:1310.0263, October 2013. URL: https://arxiv.org/abs/1310.0263.

[MZ15] Paul-André Melliès and Noam Zeilberger. Functors are type refinement systems. In *Proceedings of the 42nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages*, pages 3–16. ACM, 2015. doi:10.1145/2676726.2676970.

[MZ16] Paul-André Melliès and Noam Zeilberger. A bifibrational reconstruction of Lawvere’s presheaf hyperdoctrine. In *Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science*, pages 555–564. ACM, 2016. doi:10.1145/2933575.2934525.

[MZ18] Paul-André Melliès and Noam Zeilberger. An Isbell duality theorem for type refinement systems. *Mathematical Structures in Computer Science*, 28(6):736–774, 2018. doi:10.1017/S0960129517000068.

[MZ22] Paul-André Melliès and Noam Zeilberger. Parsing as a lifting problem and the Chomsky-Schützenberger representation theorem. In *MFPS 2022 - 38th conference on Mathematical Foundations for Programming Semantics*, July 2022. doi:10.46298/entics.10508.
[MZ25] Paul-André Melliès and Noam Zeilberger. Context-free languages as initial models of context-free grammars. In preparation. A draft was originally included as an addendum to an earlier version of this paper, see https://arxiv.org/abs/2405.14703v1, May 2025.

[PA97] Dusko Pavlović and Samson Abramsky. Specifying interaction categories. In Eugenio Moggi and Giuseppe Rosolini, editors, *Category Theory and Computer Science (CTCS 1997)*, volume 1290 of LNCS, pages 147–158. Springer, 1997. doi:10.1007/BFB0026986.

[Par12] Robert Paré. Mealy morphisms of enriched categories. *Applied Categorical Structures*, 20(3):251–273, 2012. doi:10.1007/S10485-010-9238-8.

[Rom23] Mario Román. *Monoidal Context Theory*. PhD thesis, Tallinn University of Technology, 2023.

[Ros95] Kimmo I. Rosenthal. Quantaloids, enriched categories and automata theory. *Applied Categorical Structures*, 3(3):279–301, 1995. doi:10.1007/BF00878445.

[RS59] Michael O. Rabin and Dana S. Scott. Finite automata and their decision problems. *IBM Journal of Research and Development*, 3(2):114–125, 1959.

[Sal09] Sylvain Salvati. Recognizability in the simply typed lambda-calculus. In *WoLLIC*, volume 5514 of LNCS, pages 48–60, 2009. doi:1007/978-3-642-02261-6_5.

[Sch63] M. P. Schützenberger. On context-free languages and push-down automata. *Information and control*, 6(3):246–264, 1963.

[Sch15] Gilles Schaeffer. Planar maps. In Miklós Bóna, editor, *Handbook of Enumerative Combinatorics*, pages 335–396. CRC, 2015.

[Sip13] Michael Sipser. *Introduction to the theory of computation*, 3rd edition. Cengage Learning, 2013.

[Sla20] Sergey Slavnov. Classical linear logic, cobordisms and categorial grammars. Unpublished, arXiv:1911.03962, 2020. URL: https://arxiv.org/abs/1911.03962.

[SMFK91] Hiroyuki Seki, Takashi Matsumura, Mamoru Fujii, and Tadao Kasami. On multiple context-free grammars. *Theoretical Computer Science*, 88(2):191–229, 1991. doi:10.1016/0304-3975(91)90374-B.

[SS88] Seppo Sippu and Eljas Soisalon-Soininen. *Parsing Theory - Volume I: Languages and Parsing*, volume 15 of *EATCS Monographs on Theoretical Computer Science*. Springer, 1988. doi:10.1007/978-3-642-61345-6.

[Ste01] Benjamin Steinberg. Finite state automata: a geometric approach. *Transactions of the American Mathematical Society*, 353(9):3409–3464, 2001.

[Str96] Ross Street. Categorical structures. In M. Hazewinkel, editor, *Handbook of Algebra*, volume 1, pages 529–577. North-Holland, 1996.

[SV90] G. Shabat and V. Voevodsky. Drawing curves over number fields. In P. Cartier, Luc Illusie, Nicholas M. Katz, Gérard Laumon, Yuri I. Manin, and Kenneth A. Ribet, editors, *The Grothendieck festschrift III*, number 88 in Progress in Mathematics, pages 199–227. Birkhäuser, 1990. URL: https://www.math.ias.edu/vladimir/sites/math.ias.edu.vladimir/files/drawing_curves_published.pdf.

[TSG88] Denis Thérien and Małgorzata Sznajder-Glodowski. Finite categories and regular languages. In *Mathematical Problems in Computation Theory*, volume 21 of *Banach Center Publications*, pages 395–402. 1988.

[Wal89] R. F. C. Walters. A note on context-free languages. *Journal of Pure and Applied Algebra*, 62(2):199–203, 1989. doi:10.1016/0022-4049(89)90151-5.

[WT86] Alex Weiss and Denis Thérien. Varieties of finite categories. *Informatique théorique et applications*, 20(3):357–366, 1986.

[Zie87] Wiesław Zielonka. Notes on finite asynchronous automata. *RAIRO – Theoretical Informatics and Applications*, 21:99–135, 1987.