Old and New Minimalism: a Hopf algebra comparison

We begin by reviewing the main constructions of Hopf algebras of rooted trees, focusing on the Loday–Ronco Hopf algebra, which is based on planar binary rooted trees.

Associative algebras can be regarded as the natural algebraic structure that describes linear strings of letters in a given alphabet with the operation of concatenation of words. On the other hand, in Linguistics the emphasis is put preferably on the syntactic trees that provide the parsing of sentences, rather than on the strings of words produced by a given grammar. When dealing with trees instead of strings as the main objects, the appropriate algebraic formalism is no longer associative algebras, but Hopf algebras and more generally operads. These are mathematical structures essentially designed for the parsing of hierarchical compositional rules, by encoding (in a coproduct operation) all the possible “correct parsings”, that is, all available decompositions of an element into its possible building blocks.

We recall here some general facts about Hopf algebras that we will be using in the following.

A Hopf algebra ${\mathcal{H}}$ is a vector space over a field ${\mathbb{K}}$, endowed with

• •

  a multiplication $m:{\mathcal{H}}\otimes_{\mathbb{K}}{\mathcal{H}}\to{\mathcal{H}}$;

• •

  a unit $u:{\mathbb{K}}\to{\mathcal{H}}$;

• •

  a comultiplication $\Delta:{\mathcal{H}}\to{\mathcal{H}}\otimes_{\mathbb{K}}{\mathcal{H}}$;

• •

  a counit $\epsilon:{\mathcal{H}}\to{\mathbb{K}}$;

• •

  an antipode $S:{\mathcal{H}}\to{\mathcal{H}}$

which satisfy the following properties. The multiplication operation is associative, namely the following diagram commutes

and the unit and multiplication are related by the commutative diagram

where the two unmarked downward arrows are the identifications induced by scalar multiplication. The coproduct is coassociative, namely the following diagram commutes

and the comultiplication and the counit are related by the commutative diagram

where the two unmarked upward arrows are the identifications given, respectively, by $x\mapsto 1_{\mathbb{K}}\otimes x$ and $x\mapsto x\otimes 1_{\mathbb{K}}$, with $1_{\mathbb{K}}$ the unit of the field ${\mathbb{K}}$. Moreover, $\Delta$ and $\epsilon$ are algebra homomorphisms, and $m$ and $u$ are coalgebra homomorphisms. The antipode $S:{\mathcal{H}}\to{\mathcal{H}}$ is a linear map such that the following diagram also commutes

In any graded bialgebra it is possible to construct an antipode map inductively by

(2.1)

$$S(X)=-X-\sum S(X^{\prime})X^{\prime\prime},$$

for any element $X$ of the bialgebra, with coproduct $\Delta(X)=X\otimes 1+1\otimes X+\sum X^{\prime}\otimes X^{\prime\prime}$, where the $X^{\prime}$ and $X^{\prime\prime}$ are terms of lower degree. Thus, in the following we will focus only on the bialgebra structure and not discuss the antipode map explicitly.

Heuristically, what these properties of a Hopf algebra describe can be summarized as follows. As we will see in the specific example of trees below, as a vector space ${\mathcal{H}}$ consists of formal linear combinations of a specific class of objects (planar binary rooted trees, Feynman graphs, etc.). The operations will be defined on these generators and extended by linearity. The multiplication structure is a combination operation and the coproduct structure is a decomposition operation that lists all the possible different decompositions (parsings). The antipode is like a group inverse and it establishes the compatibility between multiplication and comultiplication, unit and counit.

A rooted tree $T$ is a finite graph whose geometric realization is simply connected (no loops), defined by a set of vertices $V$, with a distinguished element $v_{r}\in V$, the root vertex, and a set of edges $E$, which we can assume oriented with the uniquely defined orientation away from the root. The source and target maps $s,t:E\to V$ assign to each edge of the tree its source and target vertices. The leaves of the tree are the univalent vertices. They are also the sinks (no outgoing edges). A rooted tree is planar if it is endowed with an embedding of its geometric realization in the plane. Assigning planar embedding is equivalent to assigning a linear ordering of the leaves. The tree is vertex-decorated if there is a map $L_{V}:V\to D_{V}$ to a (finite) set. It is edge-decorated if similarly there is a map $L_{E}:E\to D_{E}$ to a finite set of possible edge decorations. We will assume the trees are vertex-decorated, and we will simply refer to them as decorated trees.

An admissible cut $C$ on a rooted tree $T$ is an operation that

1. (1)

   selects a number of edges of $T$ with the property that every oriented path in $T$ from the root to one of the leaves contains at most one of the selected edges

2. (2)

   removes the selected edges.

The result of an admissible cut is a disjoint union of a tree $\rho_{C}(T)$ that contains the root vertex and a forest $\pi_{C}(T)$, that is, a disjoint union $\pi_{C}(T)=\cup_{i}T_{i}$ of planar trees, where each $T_{i}$ has a unique source vertex (no incoming edges), which we select as root vertex of $T_{i}$,

(2.2)

$$C(T)=\rho_{C}(T)\cup\pi_{C}(T).$$

An elementary admissible cut (or simply elementary cut) is a cut $C$ consisting of a single edge.

We note right away that this algebraic structure is different from that we considered in [37]. Since older forms of Minimalism, such as Stabler’s version that we discuss here, incorporate linear ordering, it is necessary to work with binary rooted trees with an assigned choice of planar embedding (linear ordering of the leaves). This has immediate consequences on the type of algebraic structure that we need to work with, as the possible forms of product and coproduct operations are affected by the presence of this linear ordering. Another difference with respect to our setting in [37] is that in the new Minimalism, Merge acts on workspaces (a Hopf algebra of binary forests with no planar embeddings), while in the old Stabler Minimalism, Merge acts on (a Hopf algebra of) planar binary rooted trees.

Consider the vector space ${\mathcal{V}}_{k}$ spanned by the planar binary rooted trees $T$ with $k$ internal vertices (equivalently, with $k+1$ leaves). It has dimension

$$\dim{\mathcal{V}}_{k}=(\#D_{V})^{k}\frac{(2k)!}{k!(k+1)!},$$

where $\#D_{V}$ is the cardinality of the set $D_{V}$ of possible vertex labels. Let ${\mathcal{V}}=\oplus_{k\geq 0}{\mathcal{V}}_{k}$, with ${\mathcal{V}}_{0}={\mathbb{Q}}$. For a given label $d\in D_{V}$ the grafting operator $\wedge_{d}$ is defined as

(2.3)

$$\wedge_{d}:{\mathcal{V}}\otimes{\mathcal{V}}\to{\mathcal{V}},\ \ \ T_{1}\otimes T_{2}\mapsto T=T_{1}\wedge_{d}T_{2}\,,$$

with $\wedge_{d}:{\mathcal{V}}_{k}\otimes{\mathcal{V}}_{\ell}\to{\mathcal{V}}_{k+\ell-1}$, that attaches the two roots $v_{r_{1}}$ of $T_{1}$ and $v_{r_{2}}$ of $T_{2}$ to a single root vertex $v$ labelled by $d\in D_{V}$.

One also introduces the following associative concatenation operations on planar binary rooted trees: given $S$ and $T$, the tree $S\backslash T$ ($S$ under $T$) is obtained by grafting the root of $T$ to the rightmost leaf of $S$, while $T/S$ ($S$ over $T$) is the tree obtained by grafting the root of $T$ to the leftmost leaf of $S$. The grafting operation (2.3) is related to these concatenations by

(2.4)

$$T_{1}\wedge_{d}T_{2}=T_{1}/S\backslash T_{2},$$

where $S$ is the planar binary tree with a single vertex decorated by $d\in D_{V}$. Each planar binary rooted tree is described as a grafting $T=T_{\ell}\wedge_{d}T_{r}$, of the trees stemming to the left and right of the root vertex. We remove the explicit mention of the vertex decorations when not needed.

The Loday–Ronco Hopf algebra ${\mathcal{H}}_{LR}$ of planar binary rooted trees is obtained from the vector space ${\mathcal{V}}$ by defining a multiplication and a comultiplication inductively by degrees. For trees $T=T_{\ell}\wedge T_{r}$ and $T^{\prime}=T^{\prime}_{\ell}\wedge T^{\prime}_{r}$ the product defined in [35] can be built inductively using the property

$$T\star T^{\prime}=T_{\ell}\wedge(T_{r}\star T^{\prime})+(T\star T^{\prime}_{\ell})\wedge T^{\prime}_{r},$$

with the tree consisting of a single root vertex $\bullet$ as the unit. The coproduct similarly can be built from lower degree terms by the property

$$\Delta(T)=\sum_{j,k}(T_{\ell,j}\star T_{r,k})\otimes(T^{\prime}_{\ell,n-j}\wedge T^{\prime}_{r,m-k})+T\otimes\bullet$$

where $T=T_{\ell}\wedge T_{r}$ and $\Delta(T_{\ell})=\sum_{j}T_{\ell,j}\otimes T^{\prime}_{\ell,n-j}$ and $\Delta(T_{r})=\sum_{k}T_{r,k}\otimes T^{\prime}_{r,m-k}$, for $T_{\ell}\in{\mathcal{V}}_{n}$ and $T_{r}\in{\mathcal{V}}_{m}$.

In [35] this Hopf algebra ${\mathcal{H}}_{LR}$ of planar binary rooted trees is described in terms of the Hopf algebra structure on the group algebra ${\mathbb{Q}}[S_{\infty}]=\oplus_{n}{\mathbb{Q}}[S_{n}]$ of the symmetric group. Namely, the inclusion of the Hopf algebra of non-commutative symmetric functions in the Malvenuto-Reutenauer Hopf algebra of permutations factors through the Loday-Ronco Hopf algebra of planar binary rooted trees, see also [1]. In [7] a version of the Loday-Ronco Hopf algebra of planar binary rooted trees was used for the renormalization of massless quantum electrodynamics and and explicit isomorphisms between the Loday-Ronco Hopf algebra of planar binary rooted trees and the (noncommutative) Connes–Kreimer Hopf algebra of renormalization were constructed in [1], [25], [20].

It is shown in [1] that the coproduct and product of the Loday-Ronco Hopf algebra of planar binary rooted trees can be conveniently visualized in the following way.

Given a tree $T$, one subdivides it into two parts by cutting along the path from one of the leaves to the root (illustration from [1])

and the coproduct then takes the form of a sum over all such decompositions

(2.5)

$$\Delta(T)=\sum T^{\prime}\otimes T^{\prime\prime}$$

where $T^{\prime},T^{\prime\prime}$ are, respectively the parts of $T$ to the left and right of the path from a leaf to the root and all choices of leaves are summed over.

In order to form the product $T_{1}\star T_{2}$, suppose that $T_{1}$ has $n_{1}+1$ leaves and $T_{2}$ has $n_{2}+1$ leaves. Consider again subdivisions of the tree $T_{1}$ obtained by cutting along paths from the leaves to the root, including trees consisting of just the path itself, with the cuts chosen so as to obtain $n_{2}+1$ subtrees of $T_{1}$ (illustration from [1] in a case with $n_{1}=5$, $n_{2}=3$)

We write ${\mathcal{V}}^{(k)}$ for the ${\mathbb{Q}}$-vector space spanned by the planar binary rooted trees with $k$ leaves, and we write the usual operadic composition operation of grafting roots to leaves as above in the form

(2.6)

$$\gamma:{\mathcal{V}}^{(k_{0})}\times\cdots\times{\mathcal{V}}^{(k_{n})}\times{\mathcal{V}}^{(n+1)}\to{\mathcal{V}}^{(k_{0}+\cdots+k_{n})}$$

where $\gamma(T_{0},\ldots,T_{n};T)$ is the tree obtained by grafting the trees $T_{i}\in{\mathcal{V}}^{(k_{i})}$ in collection $(T_{0},\ldots,T_{n})$ to the tree $T\in{\mathcal{V}}^{(n+1)}$, by attaching the root of $T_{i}$ to the $i$-th leaf of $T$, as illustrated above.

The product in ${\mathcal{H}}_{LR}$ is then written in the form

(2.7)

$$T\star T^{\prime}=\sum_{(T_{0},\ldots,T_{n})}\gamma(T_{0},\ldots,T_{n};T^{\prime})$$

with $n+1$ the number of leaves of $T^{\prime}$, and the sum over subdivisions into subtrees extracted according to the rule described above.

The previous subsections only dealt with general mathematical formalism about planar binary rooted trees. We now consider more specifically the case of Stabler’s Computational Minimalism.

In Stabler’s formulation, one considers planar binary rooted trees such as the following example (from [42]).

where the ordering of the leaves determines and is determined by the planar embedding of the tree, and the labels at the inner vertices serve the purpose of pointing toward the head.

More precisely, all internal vertices and the root vertex are labelled by symbols in the set $\{>,<\}$. The purpose of the labels $>$ and $<$ is to identify where the head of the tree is: in the example above the head is the leaf vertex number $8$. In addition to these labels, one also considers a finite set of syntactic features $X\in\{N,V,A,P,C,T,D,\ldots\}$ and “selector” features denoted by the symbol $\sigma X$ for a head selecting a phrase $XP$. More generally we can have labels that are strings (ordered finite sets) $\alpha=X_{0}X_{1}\cdots X_{r}$ of syntactic features as above. We also consider labels given by letters $\omega$ and $\bar{\omega}$ that stand for “licensor” and “licensee”. (Note: in [42] the notation $=X$ is used for feature selector instead of our $\sigma X$, and the notation $\pm X$ is used for licensor/licensee pairs, but we prefer to avoid using mathematical notation with a meaning different from its generally accepted one, to avoid confusion, hence we will use the letters $\sigma$ and $\omega,\bar{\omega}$ instead.)

We write the result of external merge applied to constituents $\alpha$ and $\beta$ as in [42], as the labelled planar binary rooted tree

\Tree

[ .$<$ $\alpha$ $\beta$ ]                rather than \Tree[ .$\alpha$ $\alpha$ $\beta$ ]

This means that we consider as generators of the Loday–Ronco Hopf algebras the binary trees with labels that include the syntactic features, as well as symbols $<$ and $>$, as in [42], used to point towards the head when merge is applied.

By (2.4) it is clear that the head of the tree $T_{1}\wedge_{>}T_{2}$ is the head of $T_{2}$ and the head of the tree $T_{1}\wedge_{<}T_{2}$ is the head of $T_{1}$.

Recall also that a maximal projection in $T$ is a subtree of $T$ that is not a proper subtree of any larger subtree with the same head. As pointed out in [42], in the example illustrated above, the leaves $\{2,3,4\}$ determine a subtree with head vertex the leaf numbered $3$, but any larger subtree in $T$ would have a different head, hence this subtree is a maximal projection. So is the subtree determined by the leaves $\{5,6\}$, for instance.

We will write ${\mathcal{H}}_{ling}$ for the Loday-Ronco Hopf algebra ${\mathcal{H}}_{LR}$ with the choice of labels described above. We will write ${\mathcal{V}}_{ling}$ for the underlying ${\mathbb{Q}}$-vector space spanned by the binary trees with the labeling described above.

As we pointed out already, the choice of working with planar binary rooted trees corresponds to an assigned linear ordering of its leaves, which in turn is the linear ordering of the resulting sentence when spoken or read. Thus, by working with planar trees we are assuming that linear ordering is determined for the result of Merge. This is the same assumption made in [42]. This is the crucial point in the comparison with the new Minimalism, and we will discuss it more explicitly in Section 3 below.

We now discuss the external and internal merge operations in the old formulations of minimalism. We first describe the operations at the level of the underlying combinatorial tree, and then we give the more precise constraints on when the operations can be applied, based on the labels of the trees involved.

Thus, the way we should view external and internal merge is as partially defined operations

$${\mathcal{E}}:{\mathcal{V}}_{ling}\otimes{\mathcal{V}}_{ling}\to{\mathcal{V}}_{ling}$$

$${\mathcal{I}}:{\mathcal{V}}_{ling}\to{\mathcal{V}}_{ling}$$

where we assume that the operations defined on generators are extended by (bi)linearity, so that they are defined on linear subspaces

$${\rm Dom}({\mathcal{E}})\subset{\mathcal{V}}_{ling}\otimes{\mathcal{V}}_{ling}$$

$${\rm Dom}({\mathcal{I}})\subset{\mathcal{V}}_{ling}$$

that we will describe more precisely below.

At the level of the underlying combinatorial trees external and internal merge are simply defined as the following operations.

The combinatorial structure of the external merge is given by

(2.8)

$${\mathcal{E}}(T_{1}\otimes T_{2})=\left\{\begin{array}[]{ll}\bullet\wedge T_{2}&T_{1}=\bullet\\[8.53581pt] T_{2}\wedge T_{1}&\text{otherwise,}\end{array}\right.$$

where $\bullet$ denotes the tree consisting of a single vertex, and the $\wedge$ operation is the grafting operation $\wedge_{d}$ defined as in (2.3), where the specific label $d\in\{>,<\}$ according to a rule that will be discussed more in detail in §2.7 below.

The combinatorial structure of the internal merge is given by

(2.9)

$${\mathcal{I}}(T)=\pi_{C}(T)\wedge\rho_{C}(T),$$

where $C$ is an elementary admissible cut of $T$ with $\rho_{C}(T)$ the remaining pruned tree that contains the root of $T$ and $\pi_{C}(T)$ the part that is severed by the cut (which in the case of an elementary cut is itself a tree rather than a forest). Again $\wedge$ is as in (2.3), with a label that will be made more precise below, and the choice of the elementary cut will also depend on conditions on tree labels, see §2.8.

We now look more precisely at the structure of external and internal merge and at their domains of definition. It should be noted how working with planar structures and with conditions of matching/related labels makes the underlying mathematical operations more difficult to describe, as they are only defined on specific domains and with additional conditions.

The more precise definition of the External Merge in the older forms of Miimalism is given as follows (where we are adapting the description of [42] to our terminology and notation).

As in [42], we use the notation $T[\alpha]$ for a tree where the head is labelled by an ordered set of syntactic features starting with $\alpha$. The label $\alpha$ consists of a string of syntactic features of the form

$$\alpha=X_{0}X_{1}\cdots X_{r}\ \ \ \text{ or }\ \ \ \alpha=\sigma X_{0}X_{1}\cdots X_{r},$$

with $\sigma$ the selector symbol.

We introduce the notation $\hat{\alpha}$ for the string obtained from $\alpha$ after removing the first feature (other than the selection symbol). Namely, for $\alpha=X_{0}X_{1}\cdots X_{r}$ or $\alpha=\sigma X_{0}X_{1}\cdots X_{r}$, we have $\hat{\alpha}=X_{1}\cdots X_{r}$.

The external merge $T={\mathcal{E}}(T_{1}[\sigma\alpha],T_{2}[\alpha])$ of two trees $T_{1}[\sigma\alpha]$ and $T_{2}[\alpha]$ is given by

(2.10)

$${\mathcal{E}}(T_{1}[\sigma\alpha],T_{2}[\alpha])=\left\{\begin{array}[]{ll}T_{1}[\widehat{\sigma\alpha}]\wedge_{<}T_{2}[\hat{\alpha}]&|T_{1}|=1\\ T_{2}[\hat{\alpha}]\wedge_{>}T_{1}[\widehat{\sigma\alpha}]&|T_{1}|>1.\end{array}\right.$$

This clearly agrees with (2.8) at the level of the underlying combinatorial trees. The main difference with (2.8) is that here the operation can be performed only if the heads are decorated with syntactic features $\sigma\alpha$ and $\alpha$, respectively. Thus the domain of definition ${\rm Dom}({\mathcal{E}})\subset{\mathcal{V}}_{ling}\otimes{\mathcal{V}}_{ling}$ of the external merge operation is the vector space on the set of generators

(2.11)

$${\rm Dom}({\mathcal{E}})={\rm span}_{\mathbb{Q}}\{(T_{1}[\beta],T_{2}[\alpha])\,|\,\beta=\sigma\alpha\}.$$

In the older formulations of Minimalism, one considers a second Merge operation, considered as distinct from External Merge, namely the Internal Merge. We again adapt to our notation and terminology the formulation given in [42]. We use the same notation as above for $T[\alpha]$ with $\alpha=X_{0}X_{1}\ldots X_{r}$ or $\alpha=\sigma X_{0}X_{1}\ldots X_{r}$ a string of syntactic features possibly starting with a selector, and we write $\hat{\alpha}=X_{1}\ldots X_{r}$. The internal merge is again modeled on the basic grafting operation of planar rooted binary trees $\wedge_{d}$, but this time its input is a single tree $T[\alpha]$.

Given a planar binary rooted tree $T$ containing a subtree $T_{1}$, and given another binary rooted tree $T_{2}$, we denote as in [42] by $T\{T_{1}\to T_{2}\}$ the planar binary rooted tree obtained by removing the subtree $T_{1}$ from $T$ and replacing it with $T_{2}$. In particular, we write $T\{T_{1}\to\emptyset\}$ for the tree obtained by removing the subtree $T_{1}$ from $T$. Note that, in order to ensure that the result of this operation is still a tree, we need to assume that if an internal vertex of $T$ belongs to the subtree $T_{1}$, then all oriented paths in $T$ from this vertex to a leaf also belong to $T_{1}$, where paths in the tree are oriented from root to leaves. We only consider subtrees that have this property. When it is necessary to stress this fact, we will refer to such subtrees as complete subtrees. Note that these are exactly the subtrees that can be obtained by applying a single elementary admissible cut $C$ to the tree $T$. The tree $T\{T_{1}\to\emptyset\}$ is then the same as the tree $\rho_{C}(T)$.

Consider a tree $T[\alpha]$ where $\alpha=X_{0}\cdots X_{r}$ or $\alpha=\sigma X_{0}\cdots X_{r}$ or $\alpha=\omega X_{0}\cdots X_{r}$ or $\alpha=\bar{\omega}X_{0}\cdots X_{r}$.

The domain ${\rm Dom}({\mathcal{I}})\subset{\mathcal{V}}_{ling}$ of the internal merge is given by the subspace

(2.12)

$${\rm Dom}({\mathcal{I}})={\rm span}_{\mathbb{Q}}\{T[\alpha]\,|\,\exists T_{1}[\beta]\subset T[\alpha],\text{with }\beta=\bar{\omega}X_{0}\hat{\beta},\,\alpha=\omega X_{0}\hat{\alpha}\}\,,$$

where $T_{1}\subset T$ is a subtree (in the sense specified above), and

(2.13)

$${\mathcal{I}}(T[\alpha])=T_{1}^{M}[\hat{\beta}]\wedge_{>}T\{T_{1}[\beta]^{M}\to\emptyset\}=\pi_{C}(T)\wedge_{>}\rho_{C}(T),$$

where $C$ is the elementary admissible cut specified by the subtree $T_{1}^{M}$ (the maximal projection of the head of $T_{1}$) and the condition (given by the matching labels $\omega X_{0}$ and $\bar{\omega}X_{0}$) that $T[\alpha]\in{\rm Dom}({\mathcal{I}})$. The head of $\pi_{C}(T)\wedge_{>}\rho_{C}(T)$ gets the label $\hat{\alpha}$.

Stabler’s External and Internal Merge, that we recalled here in (2.10) and (2.13), have issues at the linguistics level, such as problems with potentially unlabelable exocentric constructions. For example (as observed by Riny Huijbregts) Internal Merge as in (2.13) gives $\{XP,YP\}$ results, and labeling cannot be assigned, unless a further application of Internal Merge takes $XP$ or $YP$ in a criterial position, where structural agreement, SPEC-Head agreement, can take place between specifier and head. In [42], two further variants of External and Internal Merge are introduced in order to deal with “persistent features”. This results in what is referred to in [42] as “conflated minimalist grammars” (CMGs). These additional forms of External and Internal Merge, however, do not solve the problem mentioned above and further complicate the structure, so we will focus here on analyzing the algebraic structure determined by just the forms (2.10) and (2.13) of Stabler’s External and Internal Merge.

As we have discussed above, the internal merge is only partially defined on ${\mathcal{V}}_{ling}$ because it requires the existence of matching conditions on the label, which determine the domain ${\rm Dom}({\mathcal{I}})\subset{\mathcal{V}}_{ling}$. We now discuss now how the domain ${\rm Dom}({\mathcal{I}})$ and the internal merge operation ${\mathcal{I}}$ behave with respect to the coproduct of the Hopf algebra ${\mathcal{H}}_{ling}$.

Consider the coproduct $\Delta(T)$ of a tree $T\in{\rm Dom}({\mathcal{I}})$. This is given by the sum of decompositions $\Delta(T)=\sum T^{\prime}\otimes T^{\prime\prime}$ as illustrated in (2.5). In each of these decompositions one side will contain the head of the tree $T$ (or possibly both sides if the leaf used to cut the tree happens to be also the head).

If both the head of $T$ and the head of $\pi_{C}(T)$ are contained in the same side of the partition, then that side still belongs to ${\rm Dom}({\mathcal{I}})$. Thus, these pieces of the coproduct are in ${\rm Dom}({\mathcal{I}})\otimes{\mathcal{H}}_{ling}+{\mathcal{H}}_{ling}\otimes{\rm Dom}({\mathcal{I}})$. The remaining terms, with the heads of $T$ of $\pi_{C}(T)$ on different sides of the decomposition only belong in general to ${\mathcal{H}}_{ling}\otimes{\mathcal{H}}_{ling}$ and fall outside of the domain of the internal merge.

This suggests a modification of the coproduct on ${\mathcal{H}}_{ling}$ with respect to the usual Loday-Ronco coproduct (2.5). For a generator $T$ that is not in ${\rm Dom}({\mathcal{I}})$ we just set $\pi_{C}(T)=T$, that is, no cut is performed.

For $T\in{\rm Dom}({\mathcal{I}})$, let $h(T)$ and $h(\pi_{C}(T))$ be the leaves of $T$ that are the head of $T$ and the head of $\pi_{C}(T)$, respectively. If $T$ is in ${\rm Dom}({\mathcal{I}})$ then $C$ is, as above, the elementary admissible cut determined by the label conditions. Let ${\mathcal{P}}_{\mathcal{I}}(T)$ denote the set of bipartitions

(2.14)

$${\mathcal{P}}_{\mathcal{I}}(T)=\{T=(T^{\prime},T^{\prime\prime})\,|\,(h(T)\in T^{\prime}\text{ and }h(\pi_{C}(T))\in T^{\prime})\text{ or }(h(T)\in T^{\prime\prime}\text{ and }h(\pi_{C}(T))\in T^{\prime\prime})\}\,.$$

For trees outside the domain ${\rm Dom}({\mathcal{I}})$ the set ${\mathcal{P}}_{\mathcal{I}}(T)$ just counts all bipartitions as we have set $\pi_{C}(T)=T$.

We then define the modified coproduct

(2.15)

$$\Delta_{\mathcal{I}}(T):=\sum_{(T^{\prime},T^{\prime\prime})\in{\mathcal{P}}_{\mathcal{I}}(T)}T^{\prime}\otimes T^{\prime\prime},$$

which is the same as (2.5) outside of ${\rm Dom}({\mathcal{I}})$.

With this modified coproduct ${\rm Dom}({\mathcal{I}})$ is a coideal of the coalgebra ${\mathcal{H}}_{ling}$, namely

(2.16)

$$\Delta_{\mathcal{I}}({\rm Dom}({\mathcal{I}}))\subset{\rm Dom}({\mathcal{I}})\otimes{\mathcal{H}}_{ling}+{\mathcal{H}}_{ling}\otimes{\rm Dom}({\mathcal{I}})\,.$$

We now discuss the behavior of internal merge with respect to the product structure of ${\mathcal{H}}_{ling}$. In this case, arguing in a similar way as for the coproduct above, there is a modification $\star_{\mathcal{I}}$ of the original product of $({\mathcal{H}}_{LR},\star)$ that remains the same outside of ${\rm Dom}({\mathcal{I}})$ and takes into account the additional data in ${\rm Dom}({\mathcal{I}})$ and that has the effect of making ${\rm Dom}({\mathcal{I}})$ into a right ideal with respect to the algebra $({\mathcal{H}}_{ling},\star_{\mathcal{I}})$. However, ${\rm Dom}({\mathcal{I}})$ is not a left ideal.

We define the modified product $\star_{\mathcal{I}}$ on ${\mathcal{H}}_{ling}$ in the following way. Let $h(T)$ denote the head of $T$. Given trees $T,T^{\prime}$ where $T^{\prime}$ has $n+1$ leaves, consider the set ${\mathcal{P}}_{\mathcal{I}}(T,T^{\prime})$ given by decompositions $(T_{0},\ldots,T_{n})$ of $T$ as above with

(2.17)

$${\mathcal{P}}_{\mathcal{I}}(T,T^{\prime}):=\{(T_{0},\ldots,T_{n})\,|\,h(T)\text{ and }h(\pi_{C}(T))\in T_{h(T^{\prime})}\}\,$$

Namely those decompositions $(T_{0},\ldots,T_{n})$ with the property that the head of $T$ (and the head of $\pi_{C}(T)$ in the case where $T\in{\rm Dom}({\mathcal{I}})$) lies in the component $T_{h(T^{\prime})}$ that is grafted to the head of $T^{\prime}$. In the case of $T\notin{\rm Dom}({\mathcal{I}})$ the condition reduces to just $h(T)\in T_{h(T^{\prime})}$. Note that it is always possible to have such decompositions, as some of the components $T_{i}$ can always be taken to be copies of just the path from a leaf to the root, so that the relevant piece of the decomposition can be placed at the $h(T^{\prime})$-position.

We then take the product $\star_{\mathcal{I}}$ on ${\mathcal{H}}_{ling}$ of the form

(2.18)

$$T\star_{\mathcal{I}}T^{\prime}=\sum_{(T_{0},\ldots,T_{n})\in{\mathcal{P}}_{\mathcal{I}}(T,T^{\prime})}\gamma(T_{0},\ldots,T_{n};T^{\prime})\,.$$

The head of each $\gamma(T_{0},\ldots,T_{n};T^{\prime})$ is then the same as the head of $T$, which we write in shorthand as $h(T\star_{\mathcal{I}}T^{\prime})=h(T)$. Moreover, by construction the component $T_{h(T^{\prime})}$ is in ${\rm Dom}({\mathcal{I}})$ when $T\in{\rm Dom}({\mathcal{I}})$, so that $T\star_{\mathcal{I}}T^{\prime}$ is itself in ${\rm Dom}({\mathcal{I}})$. This shows that ${\rm Dom}({\mathcal{I}})$ is a right ideal with respect to the algebra $({\mathcal{H}}_{ling},\star_{\mathcal{I}})$,

$${\rm Dom}({\mathcal{I}})\,\star_{\mathcal{I}}\,{\mathcal{H}}_{ling}\subset{\rm Dom}({\mathcal{I}})\,.$$

It is, however, not a left ideal.

For $T\in{\rm Dom}({\mathcal{I}})$ we then have

(2.19)

$${\mathcal{I}}(T\star_{\mathcal{I}}T^{\prime})=\sum_{(T_{0},\ldots,T_{n})\in{\mathcal{P}}_{\mathcal{I}}(T,T^{\prime})}\pi_{C}(T_{h(T^{\prime})})\wedge_{>}\gamma(T_{0},\ldots,\rho_{C}(T_{h(T^{\prime})}),\ldots,T_{n};T^{\prime})\,.$$

Combining the behavior with respect to the product with the previous observation about the coproduct we conclude that the internal merge ${\mathcal{I}}$ defines a right $({\mathcal{H}}_{ling},\star_{\mathcal{I}})$-module given by the cosets

$${\mathcal{M}}_{\mathcal{I}}:={\rm Dom}({\mathcal{I}})\backslash{\mathcal{H}}_{ling}$$

where ${\mathcal{M}}_{\mathcal{I}}$ is also a coalgebra with the coproduct induced by $({\mathcal{H}}_{ling},\Delta_{\mathcal{I}})$.

In fact, the construction above can be extended to a nested family of right-ideal coideals, given by the domains of the iterations of the internal merge, ${\mathcal{D}}_{N+1}\subset{\mathcal{D}}_{N}$ with

$${\mathcal{D}}_{N}:={\rm Dom}({\mathcal{I}}^{N})\,.$$

When we consider repeated application of $N$ internal merge operations, starting from a given tree $T[\alpha]$, where $\alpha$ is a finite list of features each of which can be either $X_{i}$ or $\omega X_{i}$ of $\bar{\omega}X_{i}$ as above, we need to assume the following conditions

1. (1)

   There are $N$ subtrees $T_{1},\ldots,T_{N}$ in $T$, each of which is a complete subtree, in the sense specified above.

2. (2)

   Let $T_{1}^{M},\ldots,T_{N}^{M}$ be the maximal projections of the subtrees, in the sense recalled above. These are also complete subtrees of $T$.

3. (3)

   The subtrees $T_{i}^{M}$ are disjoint.

In addition to these combinatorial conditions, we have a matching labels condition that specifies the domain of the composite operation. Let $T[\alpha]$ be the given tree as a labelled tree, and let $T_{1}[\beta^{(1)}],\ldots,T_{N}[\beta^{(N)}]$ be the labelled subtrees, with the conditions listed above. The domain of the composite internal merge is then given by

(2.20)

$${\rm Dom}({\mathcal{I}}^{N})=\left\{T[\alpha]\,\big{|}\,\exists T_{1}[\beta^{(1)}],\ldots,T_{N}[\beta^{(N)}]\,\text{ with }\left\{\begin{array}[]{l}\text{(1), (2), (3) are satisfied}\\ \beta^{(1)}_{0}=\bar{\omega}X_{0},\ldots,\beta^{(N)}_{0}=\bar{\omega}X_{N-1}\\ \alpha=\omega X_{0}\omega X_{1}\cdots\omega X_{N-1}\cdots\end{array}\right\}\right\}.$$

For a forest $F=T_{1}\cdots T_{\ell}$, we define a grafting operation $\wedge^{\ell}$ that consists of the repeated application of the grafting $\wedge$ to the trees in $F$,

(2.21)

$$\bigwedge^{\ell}F=T_{1}\wedge T_{2}\wedge\cdots\wedge T_{\ell}.$$

The conditions (1), (2), and (3) above ensure that the choice of the subtrees $T_{1}^{M},\ldots,T_{N}^{M}$ corresponds to an admissible cut $C$ of the tree $T$, with the number of cut branches $\#C=N$ The planar binary rooted tree obtained by this operation is then

(2.22)

$${\mathcal{I}}^{\#C}(T[X])=\bigwedge^{1+\#C}\left(\pi_{C}(T)[\hat{\mathbb{Y}}]\,\,\rho_{C}(T)[\hat{X}^{N}]\right),$$

where we use the notation $\pi_{C}(T)[\hat{\mathbb{Y}}]$ for the forest $\pi_{C}(T)=T_{N}^{M}\cdots T_{1}^{M}$, where the label $[\hat{\mathbb{Y}}]$ means

$$\pi_{C}(T)[\hat{\mathbb{Y}}]=T_{N}^{M}[\hat{\beta}^{(N)}]\cdots T_{1}^{M}[\hat{\beta}^{(1)}]$$

and the label $[\hat{\alpha}^{N}]$ of the tree $\rho_{C}(T)$ stands for what remains of the original label $X$ after the initial terms $\omega X_{0}\omega X_{1}\cdots\omega X_{N-1}$ are removed.

Each ${\mathcal{D}}_{N+1}\backslash{\mathcal{D}}_{N}$ determines a coideal in the coalgebra ${\mathcal{D}}_{N+1}\backslash{\mathcal{H}}_{ling}$ and this gives a projective system of right-module coalgebras

$${\mathcal{M}}_{{\mathcal{I}}^{N}}:={\rm Dom}({\mathcal{I}}^{N})\backslash{\mathcal{H}}_{ling}\,.$$

In the Minimalist Model of syntax, the Merge operator is the main mechanism for the construction of recursive and hierarchical structures. So indeed it is not surprising that the Hopf-algebraic formalism occurs naturally in this context, as it is known to describe similar hierarchical structures (such as Feynman graphs) in fundamental physics. In the applications of Hopf algebras to physics, especially to renormalization in perturbative quantum field theories, Hopf ideals are closely related to the recursive implementation of symmetries (Ward identities) and the recursive construction of solutions to equations of motion (Dyson-Schwinger equations), [19], [45].

We have discussed in our previous paper [37] how the algebraic formulation of the new Minimalism closely resembles the mathematical structure of Dyson-Schwinger equations in physics. However, the analogous mathematical structure describing Merge in the old forms of Minimalism differs significantly from that basic fundamental formulation we have in the case of the new Minimalism.

The main difference, as shown above, lies in the intrinsic asymmetry of the old form of the Merge operation, which only gives rise to a weaker structure than Hopf ideals, namely the right-ideal coideals discussed in §2.10. Thus, instead of a quotient Hopf algebra as in the case of implementation of symmetries in quantum field theory, one only obtains a quotient right-module coalgebra.

Such objects, quotient right-module coalgebras, sometimes referred to as “generalized quotients” of Hopf algebras, do provide a suitable notion of quotients in the case of noncommutative Hopf algebras, [38], [43]. They are also studied in the context of the theory of Hopf–Galois extensions, designed to provide good geometric analogs in noncommutative geometry of principal bundles and torsors in ordinary geometry, see for instance [41]. However, the type of structure involved, in order to accommodate the requirement of working with planar trees, becomes significantly more complicated than in the case of free symmetric Merge of the new Minimalism.

We can think of the right-module coalgebras ${\mathcal{M}}_{{\mathcal{I}}^{N}}$ as a family of geometric spaces (in a noncommutative sense) that implement the recursive structures of syntax generated by the Merge operation, in a sense similar to how quotients by Hopf ideals in physics recursively implement the gauge symmetries or the recursively constructed solutions to the equations of motion. This, however, is a significantly weaker (and at the same time significantly more complicated) algebraic structure than the one we see occurring in the newer version of Minimalism, as shown in [37] and discussed in §3 below.

We now discuss more in detail the mathematical structure of the old formulation of External Merge, and we show how it creates an independent structure of a very different nature from Internal Merge discussed in §2.10. These very different mathematical formulations of Internal and External Merge are another significant drawback of the older Minimalism in comparison with the newer.

We can consider the data $({\mathcal{H}}_{ling},\star_{\mathcal{I}},{\rm Dom}({\mathcal{I}}),{\mathcal{I}})$ discussed above as a generalization of the notion of operated algebra (see [24], [46]) where one considers data $({\mathcal{A}},\star,F)$ of an algebra together with a linear operator $F:{\mathcal{A}}\to{\mathcal{A}}$. Here we allow for the case where the linear operator $F:{\rm Dom}(F)\to{\mathcal{A}}$ is only defined on a smaller domain ${\rm Dom}(F)\subset{\mathcal{A}}$ which is a right ideal of ${\mathcal{A}}$. We can refer to this structure $({\mathcal{H}}_{ling},\star_{\mathcal{I}},{\rm Dom}({\mathcal{I}}),{\mathcal{I}})$ as a partial operated algebra.

The setting of operated algebras was introduced by Rota [40] as a way of formalizing various instances of linear operators $F:{\mathcal{A}}\to{\mathcal{A}}$ on an algebra that satisfy polynomial constraints. The simplest example of such polynomial constraints is the identity $F(a\star b)=F(a)\star F(b)$ that makes $F$ an actual algebra homomorphism. Another example is the Leibniz rule constraint $F(a\star b)=a\star F(b)+F(a)\star b$ that makes $F$ a derivation. Other interesting polynomial constraints are Rota–Baxter relations, $F(a)\star F(b)=F(a\star F(b))+F(F(a)\star b)+\lambda F(a\star b)$, which depending on the value of the parameter $\lambda$ can represent various types of operations such as integration by parts, or extraction of the polar part of a Laurent series, and play an important role in the Hopf algebra formulation of renormalization in physics.

In the case of the internal merge we considered above, not only the linear operator is only partially defined as ${\mathcal{I}}:{\rm Dom}({\mathcal{I}})\to{\mathcal{H}}_{ling}$, but the identity (2.19) that expresses the internal merge of a product is not directly of a simple poynomial form as in Rota’s operated algebra program. However, it appears to be an interesting question whether the type of relation (2.19) can be accommodated in terms of the approach to Rota’s program via term rewriting systems (in the sense of [2]) developed in [22], [24].

We now focus on the binary operation ${\mathcal{E}}$ of External Merge, defined on the subdomain ${\rm Dom}({\mathcal{E}})\subset{\mathcal{H}}_{ling}\otimes{\mathcal{H}}_{ling}$ described in (2.11). The structure of external merge is simpler than the internal merge discussed above, and closely related to the usual Hochschild cocycle that defines the grafting operations in the Hopf-algebraic construction of Dyson-Schwinger equations in physics.

The “operated algebra” viewpoint we discussed briefly above is especially useful in analyzing the external merge, along the lines of extending the notion of operated algebra from unitary to binary operations discussed in [46].

We recall from [46] the notion of operated algebra based on binary operations. These structure is called a $\vee_{\Omega}$-algebra in [46]. In our notation we use $\wedge$ instead of $\vee$ for the grafting of binary trees used in the merge operation, following the convention of writing syntactic parsing trees with the root at the top and the leaves at the bottom. So we are going to refer to this structure as $\wedge_{\Omega}$-algebra.

A $\wedge_{\Omega}$-algebra is an algebra $({\mathcal{A}},\star)$ together with a family of binary operations $\{\wedge_{\alpha}\}_{\alpha\in\Omega}$ satisfying the identity

(2.23)

$$a\star b=a_{1}\wedge_{\alpha}(a_{2}\star b)+(a\star b_{1})\wedge_{\alpha}b_{2}\,,$$

for $a=a_{1}\wedge_{\alpha}a_{2}$ and $b=b_{1}\wedge_{\alpha}b_{2}$. A $\wedge_{\Omega}$-bialgebra (or Hopf algebra) $({\mathcal{H}},\Delta,\star,\wedge_{\Omega})$ is a bialgebra (or Hopf algebra) that is also a $\wedge_{\Omega}$-algebra. It is a cocycle $\wedge_{\Omega}$-Hopf algebra if the binary operations $\wedge_{\Omega}$ also satisfy the cocycle identity

(2.24)

$$\Delta(a\wedge_{\alpha}b)=(a\wedge_{\alpha}b)\otimes 1+(\star\otimes\wedge_{\alpha})\circ\tau(\Delta(a)\otimes\Delta(b))\,,$$

where $\tau:{\mathcal{H}}\otimes{\mathcal{H}}\otimes{\mathcal{H}}\otimes{\mathcal{H}}\to{\mathcal{H}}\otimes{\mathcal{H}}\otimes{\mathcal{H}}\otimes{\mathcal{H}}$ is the permutation that exchanges the two middle factors.

It is shown in [46] that the Loday-Ronco Hopf algebra ${\mathcal{H}}_{LR}$ of planar binary rooted trees with the binary operations $\wedge_{\alpha}$ that graft two trees $T_{1},T_{2}$ as the left and right subtrees at a new binary root with label $\alpha$ is a cocyle $\wedge_{\Omega}$-Hopf algebra. The range of $\wedge_{\alpha}$ is a coideal in ${\mathcal{H}}_{LR}$. It is also shown in [46] that the $\wedge_{\Omega}$-Hopf algebra ${\mathcal{H}}_{LR}$ is the free cocycle $\wedge_{\Omega}$-Hopf algebra, that is, the initial object in the category of cocycle $\wedge_{\Omega}$-Hopf algebras.

The external merge operation is modelled on the grafting operations $\wedge_{\alpha}$ of the Loday-Ronco Hopf algebra, with labels $\alpha\in\{<,>\}$. The main differences are that the external merge inverts the order when the first tree is nontrivial,

$${\mathcal{E}}(T_{1},T_{2})=T_{2}\wedge_{>}T_{1}\ \ \ \text{ for }T_{1}\neq\bullet$$

$${\mathcal{E}}(\bullet,T_{2})=\bullet\wedge_{<}T_{2}$$

and the fact that the operation is only defined on a domain ${\rm Dom}({\mathcal{E}})\subset{\mathcal{H}}_{ling}\otimes{\mathcal{H}}_{ling}$ of pairs of trees $(T_{1}[\beta],T_{2}[\alpha])$ with matching labels $\beta=\sigma\alpha$.

Both the $\wedge_{\alpha}$-algebra identity (2.23) and the cocycle identity (2.24) are still satisfied, whenever all the terms involved are in the domain of the merge operator. This leads naturally to consider external merge as a structure of partially defined cocycle $\wedge_{\Omega}$-Hopf algebra.

Namely, a partially defined cocycle $\wedge_{\Omega}$-bialgebra (or Hopf algebra) is a bialgebra (or Hopf algebra) $({\mathcal{H}},\Delta,\star)$ together with a family $\{\wedge_{\alpha}\}_{\alpha\in\Omega}$ of binary operations defined on linear subspaces ${\rm Dom}(\wedge_{\alpha})\subset{\mathcal{H}}\otimes{\mathcal{H}}$,

$$\wedge_{\alpha}:{\rm Dom}(\wedge_{\alpha})\hookrightarrow{\mathcal{H}}\otimes{\mathcal{H}}\to{\mathcal{H}}$$

that satisfy (2.23) and (2.24), whenever all the terms are in ${\rm Dom}(\wedge_{\alpha})$.

The Hopf algebra ${\mathcal{H}}_{ling}$ with the external merge operator ${\mathcal{E}}$ is then a partially defined cocycle $\wedge_{\Omega}$-Hopf algebra.

In the new version of Minimalism, one starts with a core computational structure, which is the recursive construction of binary rooted trees, where trees are now just abstract trees, not endowed with planar structure. This structure is described mathematically in the following way.

The set ${\mathfrak{T}}$ of finite binary rooted trees without planar structure is obtained as the free non-associative commutative magma whose elements are the balanced bracketed expressions in a single variable $x$, with the binary operation (binary set formation)

(3.1)

$$(\alpha,\beta)\mapsto{\mathfrak{M}}(\alpha,\beta)=\{\alpha,\beta\}\,$$

where $\alpha,\beta$ are two such balanced bracketed expressions.

This description of the generative process of binary rooted trees is immediate from the identification of these trees with balanced bracketed expressions in a single variable $x$, such as

$$\{\{x\{xx\}\}x\}\longleftrightarrow\Tree[[x[xx]]x]\ \ \,.$$

Under this identification, the binary operation of the magma takes two rooted binary trees and attaches the roots to a new common root

(3.2)

$$(T,T^{\prime})\mapsto{\mathfrak{M}}(T,T^{\prime})=\Tree[TT^{\prime}]\,\,\,.$$

If one takes the ${\mathbb{Q}}$-vector space ${\mathcal{V}}({\mathfrak{T}})$ spanned by the set ${\mathfrak{T}}$, the magma operation ${\mathfrak{M}}$ on ${\mathfrak{T}}$ induces on ${\mathcal{V}}({\mathfrak{T}})$ the structure of an algebra. More precisely, ${\mathcal{V}}({\mathfrak{T}})$ is the free commutative non-associative algebra generated by a single variable $x$, or equivalently the free algebra over the quadratic operad freely generated by the single commutative binary operation ${\mathfrak{M}}$ (see [27]).

One can assign a grading (a weight, measuring the size) to the binary rooted trees by the number of leaves, $\ell=\#L(T)$, so that one can decompose the vector space ${\mathcal{V}}({\mathfrak{T}})=\oplus_{\ell}{\mathcal{V}}({\mathfrak{T}})_{\ell}$ into its graded components (the sub-vector-spaces spanned by the trees of weight $\ell$).

As discussed in [37], this is a very natural and simple mathematical object, and the generative process for the binary rooted trees can then be seen as the simplest and most fundamental possible case of recursive solution of a fixed point problem, of the kind that is known in physics as Dyson–Schwinger equation.

Indeed, one can view the recursive construction of binary rooted trees through repeated application of the Merge operation (3.1) as the recursive construction of a solution to the fixed point equation

(3.3)

$$X={\mathfrak{M}}(X,X)\,,$$

where $X=\sum_{\ell}X_{\ell}$ is a formal infinite sum of variables $X_{\ell}$ in ${\mathcal{V}}({\mathfrak{T}})_{\ell}$, with $\ell$ the grading by number of leaves. The problem (3.3) can be solved recursively by degrees, with

$$X_{n}={\mathfrak{M}}(X,X)_{n}=\sum_{j=1}^{n-1}{\mathfrak{M}}(X_{j},X_{n-j})\,,$$

with solution $X_{1}=x$, $X_{2}=\{xx\}$, $X_{3}=\{x\{xx\}\}+\{\{xx\}x\}=2\{x\{xx\}\}$, $X_{4}=2\{x\{x\{xx\}\}\}+\{\{xx\}\{xx\}\}$, and so on. The coefficients with which the trees occur in these solutions count the different possible choices of planar embeddings.