2.1.1 Terms

An is a finite set $\mathfrak{G}$ . Its elements are called or . Any element of the set $\mathbb{X} := \bigcup_{n \geqslant 1}\mathbb{X}_n$ , where $\mathbb{X}_n := \left\{\mathsf{x}_1, \dots, \mathsf{x}_n\right\}$ , is a . The set $\mathfrak{T}(\mathfrak{G})$ of (or simply when the context is clear) is so that any variable of $\mathbb{X}$ is a $\mathfrak{G}$ -term, any constant of $\mathfrak{G}$ is a $\mathfrak{G}$ -term, and if $\mathfrak{t}_1$ and $\mathfrak{t}_2$ are two $\mathfrak{G}$ -terms, then $\left(\mathfrak{t}_1 {\star}\mathfrak{t}_2\right)$ is a $\mathfrak{G}$ -term. For any $n \geqslant 0$ , we denote by $\mathfrak{T}_n(\mathfrak{G})$ the set of $\mathfrak{G}$ -terms $\mathfrak{t}$ having all variables belonging to $\mathbb{X}_n$ .

From this definition, any term is a rooted planar binary tree where leaves are decorated by variables or by constants. We shall express terms concisely by removing superfluous parentheses by considering that ${\star}$ associates to the left and also by removing the symbols ${\star}$ (see the example given in (2.1.1), (2.1.2), and (2.1.3)).

Let $\mathfrak{t}$ be a $\mathfrak{G}$ -term. The $\mathrm{deg}(\mathfrak{t})$ of $\mathfrak{t}$ is the number of internal nodes (the nodes decorated by ${\star}$ ) of $\mathfrak{t}$ seen as a binary tree. For any $a \in \mathbb{X} \cup \mathfrak{G}$ , $\mathrm{deg}_a(\mathfrak{t})$ is the number of nodes labeled by a in $\mathfrak{t}$ . The of a node u of $\mathfrak{t}$ is the number of internal nodes in the path connecting the root of $\mathfrak{t}$ and u. The $\mathrm{ht}(\mathfrak{t})$ of $\mathfrak{t}$ is the maximal depth among all the nodes of $\mathfrak{t}$ . The of $\mathfrak{t}$ is the sequence of all the variables appearing in $\mathfrak{t}$ from the left to the right. The term $\mathfrak{t}$ is if its frontier is of the form $\mathsf{x}_1 \mathsf{x}_2 \dots \mathsf{x}_n$ where $n \geqslant 0$ . The term $\mathfrak{t}$ is if there are no multiple occurrences of the same variable in its frontier. A or is a term of $\mathfrak{T}_0(\mathfrak{G})$ having thus no occurrence of any variable.

For instance, by setting $\mathfrak{G} := \left\{{\mathbf{A}}, {\mathbf{B}}\right\}$ , the $\mathfrak{G}$ -term

(2.1.1) \begin{equation} \mathfrak{t} := \left(\left(\left({\mathbf{A}} {\star} \mathsf{x}_3\right) {\star} \left({\mathbf{B}} {\star} \left(\left(\mathsf{x}_1 {\star} \mathsf{x}_3\right) {\star} \mathsf{x}_1\right)\right)\right) {\star} \left({\mathbf{A}} {\star} {\mathbf{A}}\right)\right)\end{equation}

draws as the binary tree

(2.1.2)

and expresses concisely as

(2.1.3) \begin{equation} \mathfrak{t} = \left({\mathbf{A}} \mathsf{x}_3\right) \left({\mathbf{B}} \left(\mathsf{x}_1 \mathsf{x}_3 \mathsf{x}_1\right)\right) \left({\mathbf{A}} {\mathbf{A}}\right).\end{equation}

Its degree is 7, its height is 5, its frontier is $\mathsf{x}_3 \mathsf{x}_1 \mathsf{x}_3 \mathsf{x}_1$ and is an element $\mathfrak{T}_n(\mathfrak{G})$ for any $n \geqslant 3$ .

2.1.2 Compositions of terms and clones

Let $\mathfrak{t}$ and $\mathfrak{t}'_1$ , …, $\mathfrak{t}'_n$ , $n \geqslant 0$ be $\mathfrak{G}$ -terms. The of $\mathfrak{t}$ with $\mathfrak{t}'_1$ , …, $\mathfrak{t}'_n$ is the $\mathfrak{G}$ -term $\mathfrak{t} \left[\mathfrak{t}'_1, \dots, \mathfrak{t}'_n\right]$ obtained by simultaneously replacing for all $i \in [n]$ all occurrences of the variables $\mathsf{x}_i$ in $\mathfrak{t}$ by $\mathfrak{t}'_i$ . For instance,

(2.1.4) \begin{equation} {\mathbf{A}} \left(\mathsf{x}_3 \mathsf{x}_1\right) \mathsf{x}_3 \left[\mathsf{x}_1 \mathsf{x}_4, \mathsf{x}_1 \mathsf{x}_1 \mathsf{x}_2, {\mathbf{A}} \left({\mathbf{A}} \mathsf{x}_1\right)\right] = {\mathbf{A}} \left({\mathbf{A}} \left({\mathbf{A}} \mathsf{x}_1\right) \left(\mathsf{x}_1 \mathsf{x}_4\right)\right) \left({\mathbf{A}} \left({\mathbf{A}} \mathsf{x}_1\right)\right).\end{equation}

Given two $\mathfrak{G}$ -terms $\mathfrak{t}$ and $\mathfrak{s}$ , $\mathfrak{s}$ is a of $\mathfrak{t}$ if

(2.1.5) \begin{equation} \mathfrak{t} = \mathfrak{t}' \left[\mathfrak{s}_1, \dots, \mathfrak{s}_{i - 1}, \mathfrak{s}, \mathfrak{s}_{i + 1}, \dots, \mathfrak{s}_n\right] \left[\mathfrak{r}_1, \dots, \mathfrak{r}_m\right]\end{equation}

for some integers $n, m \geqslant 0$ and $\mathfrak{G}$ -terms $\mathfrak{t}'$ , $\mathfrak{s}_1$ , …, $\mathfrak{s}_{i - 1}$ , $\mathfrak{s}_{i + 1}$ , …, $\mathfrak{s}_n$ , $\mathfrak{r}_1$ , …, $\mathfrak{r}_m$ , where $\mathsf{x}_i$ appears in $\mathfrak{t}'$ . When this property does not hold, $\mathfrak{t}$ $\mathfrak{s}$ . When in (2.1.5), for all $i \in [m]$ the $\mathfrak{r}_i$ are variables, $\mathfrak{s}$ is a of $\mathfrak{t}$ . When this property does not hold, $\mathfrak{t}$ $\mathfrak{s}$ . For instance, the term defined in (2.1.3) admits ${\mathbf{B}} \left(\mathsf{x}_1 \mathsf{x}_2\right)$ as factor, $\mathsf{x}_1 \mathsf{x}_2 \mathsf{x}_3$ as suffix, but suffix-avoids $\mathsf{x}_1 \mathsf{x}_1 \mathsf{x}_1$ .

Observe that we have, for any $n, m \geqslant 0$ , $i \in [n]$ , and $\mathfrak{t}, \mathfrak{s}_1, \dots,\mathfrak{s}_n, \mathfrak{r}_1, \dots, \mathfrak{r}_m \in \mathfrak{T}(\mathfrak{G})$ ,

(2.1.6a) \begin{equation} \mathsf{x}_i \left[\mathfrak{t}_1, \dots, \mathfrak{t}_n\right] = \mathfrak{t}_i,\end{equation}

(2.1.6b) \begin{equation} \mathfrak{t} \left[\mathsf{x}_1, \dots \mathsf{x}_n\right] = \mathfrak{t},\end{equation}

(2.1.6c) \begin{equation} \mathfrak{t} \left[\mathfrak{s}_1, \dots, \mathfrak{s}_n\right] \left[\mathfrak{r}_1, \dots, \mathfrak{r}_m\right] = \mathfrak{t} \left[\mathfrak{s}_1 \left[\mathfrak{r}_1, \dots, \mathfrak{r}_m\right], \dots, \mathfrak{s}_n \left[\mathfrak{r}_1, \dots, \mathfrak{r}_m\right]\right].\end{equation}

These three relations imply that the set $\mathfrak{T}(\mathfrak{G})$ together with the composition operation is an abstract clone (Taylor Reference Taylor1993). This is in fact the free abstract clone generated by $\mathfrak{G} \sqcup \textit{\{}{\star}\textit{\}}$ where ${\star}$ is a binary generator.

2.1.3 Rewrite relations

A on $\mathfrak{T}(\mathfrak{G})$ is a binary relation $\to$ on $\mathfrak{T}(\mathfrak{G})$ . The of $\to$ is the binary relation $\Rightarrow$ on $\mathfrak{T}(\mathfrak{G})$ satisfying

(2.1.7) \begin{equation} \mathfrak{t} \left[\mathfrak{s}_1, \dots, \mathfrak{s}_i, \dots, \mathfrak{s}_n\right] \left[\mathfrak{r}_1, \dots, \mathfrak{r}_m\right] \Rightarrow \mathfrak{t} \left[\mathfrak{s}_1, \dots, \mathfrak{s}_i', \dots, \mathfrak{s}_n\right] \left[\mathfrak{r}_1, \dots, \mathfrak{r}_m\right]\end{equation}

where $\mathfrak{t}$ is a planar $\mathfrak{G}$ -term, $\mathsf{x}_i$ appears in $\mathfrak{t}$ , and $\mathfrak{s}_1$ , …, $\mathfrak{s}_i$ , $\mathfrak{s}_i'$ , …, $\mathfrak{s}_n$ , $n \geqslant 1$ , $i \in [n]$ , and $\mathfrak{r}_1$ , …, $\mathfrak{r}_m$ , $m \geqslant 0$ , are $\mathfrak{G}$ -terms, and $\mathfrak{s}_i \to\mathfrak{s}_i'$ . Intuitively, $\mathfrak{t} \Rightarrow \mathfrak{t}'$ if $\mathfrak{t}'$ can be obtained from $\mathfrak{t}$ by replacing a factor $\mathfrak{s}$ of $\mathfrak{t}$ by $\mathfrak{s}'$ and by identifying variables with terms in a coherent way, whenever $\mathfrak{s} \to \mathfrak{s}'$ . For instance, for $\mathfrak{G} := \left\{{\mathbf{A}}, {\mathbf{B}}, {\mathbf{C}}\right\}$ and the rewrite relation $\to$ satisfying $ \mathsf{x}_1 \left({\mathbf{A}} \mathsf{x}_1\right) \to \mathsf{x}_1 \mathsf{x}_2,$ we have

(2.1.8) \begin{equation} \mathsf{x}_3 {\mathbf{B}} \left({\mathbf{A}} \left(\mathsf{x}_3 {\mathbf{B}}\right)\right) \left(\mathsf{x}_4 {\mathbf{A}}\right) \Rightarrow \mathsf{x}_3 {\mathbf{B}} {\mathbf{C}} \left(\mathsf{x}_4 {\mathbf{A}}\right)\end{equation}

because

(2.1.9) \begin{equation} \mathsf{x}_3 {\mathbf{B}} \left({\mathbf{A}} \left(\mathsf{x}_3 {\mathbf{B}}\right)\right) \left(\mathsf{x}_4 {\mathbf{A}}\right) = \mathsf{x}_1 \left(\mathsf{x}_2 {\mathbf{A}}\right) \ \left[\mathsf{x}_1 \left({\mathbf{A}} \mathsf{x}_1\right), \mathsf{x}_4\right] \ \left[\mathsf{x}_3 {\mathbf{B}}, {\mathbf{C}}, \mathsf{x}_3, \mathsf{x}_4\right]\end{equation}

and

(2.1.10) \begin{equation} \mathsf{x}_3 {\mathbf{B}} {\mathbf{C}} \left(\mathsf{x}_4 {\mathbf{A}}\right) = \mathsf{x}_1 \left(\mathsf{x}_2 {\mathbf{A}}\right) \ \left[\mathsf{x}_1 \mathsf{x}_2, \mathsf{x}_4\right] \ \left[\mathsf{x}_3 {\mathbf{B}}, {\mathbf{C}}, \mathsf{x}_3, \mathsf{x}_4\right].\end{equation}

Observe in this example that the variable $\mathsf{x}_2$ occurs in the right member of $\to$ and not in the left member. For this reason, this variable can be replaced by any term in the context closure of $\to$ (it is replaced by ${\mathbf{C}}$ in the example).

2.1.4 Applicative term rewrite systems

An (or for short) is a pair $(\mathfrak{G}, \to)$ such that $\mathfrak{G}$ is an alphabet and $\to$ is a rewrite relation on $\mathfrak{T}(\mathfrak{G})$ . Let $\mathcal{T} := (\mathfrak{G}, \to)$ be an ATRS. We denote by $\preccurlyeq$ the reflexive and transitive closure of $\Rightarrow$ . This relation $\preccurlyeq$ is by construction a preorder. We denote by $\equiv$ the reflexive, symmetric, and transitive closure of $\Rightarrow$ and by $\left[\mathfrak{t}\right]_\equiv$ the $\equiv$ -equivalence class of $\mathfrak{t} \in \mathfrak{T}(\mathfrak{G})$ . This relation $\equiv$ is by construction an equivalence relation. The $\mathrm{G}_\mathcal{T}$ of $\mathcal{T}$ is the digraph on the set $\mathfrak{T}(\mathfrak{G})$ of vertices where there is an arc from $\mathfrak{t} \in\mathfrak{T}(\mathfrak{G})$ to $\mathfrak{t}' \in \mathfrak{T}(\mathfrak{G})$ if $\mathfrak{t} \Rightarrow\mathfrak{t}'$ . For any $\mathfrak{t} \in \mathfrak{T}(\mathfrak{G})$ , we also denote by $\mathrm{G}_\mathcal{T}(\mathfrak{t})$ the subgraph of $\mathrm{G}_\mathcal{T}$ restrained on the set $ \left\{\mathfrak{t}' \in \mathfrak{T}(\mathfrak{G}) : \mathfrak{t} \preccurlyeq \mathfrak{t}'\right\}$ of vertices. The ATRS $\mathcal{T}$ is if for any term $\mathfrak{t}$ , $\left[\mathfrak{t}\right]_{\equiv}$ is finite. This is equivalent to the fact that all the connected components of $\mathrm{G}_\mathcal{T}$ are finite. A $\mathfrak{G}$ -term $\mathfrak{t}$ is a of $\mathcal{T}$ if there is no arc of source $\mathfrak{t}$ in $\mathrm{G}_\mathcal{T}$ . We say that $\mathfrak{t}$ is if there is at least one normal form in $\mathrm{G}_\mathcal{T}(\mathfrak{t})$ and that $\mathfrak{t}$ is if $\mathrm{G}_\mathcal{T}(\mathfrak{t})$ is finite and acyclic. When all the $\mathfrak{G}$ -terms are strongly normalizing, $\mathcal{T}$ is . Besides, if for any $\mathfrak{t}, \mathfrak{s}_1,\mathfrak{s}_2 \in \mathfrak{T}(\mathfrak{G})$ , $\mathfrak{t} \preccurlyeq \mathfrak{s}_1$ and $\mathfrak{t} \preccurlyeq \mathfrak{s}_2$ implies the existence of $\mathfrak{t}' \in \mathfrak{T}(\mathfrak{G})$ such that $\mathfrak{s}_1 \preccurlyeq\mathfrak{t}'$ and $\mathfrak{s}_2 \preccurlyeq \mathfrak{t}'$ , then $\mathcal{T}$ is .

2.1.5 Partial orders

When $\mathcal{T} := (\mathfrak{G}, \to)$ is an ATRS such that $\preccurlyeq$ is antisymmetric, $\preccurlyeq$ is a partial order relation. In this case, $\mathcal{T}$ has the and we shall denote by $\mathcal{P}_\mathcal{T}$ the poset $\left(\mathfrak{T}(\mathfrak{G}), \preccurlyeq\right)$ . For any $\mathfrak{t}\in \mathfrak{T}(\mathfrak{G})$ , let $\mathcal{P}_\mathcal{T}(\mathfrak{t})$ be the subposet of $\mathcal{P}_\mathcal{T}$ having $\mathfrak{t}$ as least element. Again in this case, a $\mathfrak{G}$ -term $\mathfrak{t}$ is (resp. ) if $\mathfrak{t}$ is a minimal (resp. maximal) element of $\mathcal{P}_\mathcal{T}$ . Observe that any normal form is maximal but the converse is false because a maximal element $\mathfrak{t}$ could satisfy $\mathfrak{t} \Rightarrow \mathfrak{t}$ . A $\mathfrak{G}$ -term $\mathfrak{t}$ is if $\mathfrak{t}$ is both minimal and maximal. When $\mathcal{T}$ has the poset property, $\mathcal{T}$ is if for any term $\mathfrak{t}$ , the subposet $\left[\mathfrak{t}\right]_{\equiv}$ of $\mathcal{P}_\mathcal{T}$ has a unique minimal element. Finally, $\mathcal{T}$ has the if $\mathcal{T}$ has the poset property and for all $\mathfrak{t} \in\mathfrak{T}(\mathfrak{G})$ , all posets $\mathcal{P}_\mathcal{T}(\mathfrak{t})$ are lattices.

2.2.1 Main definitions

A (or for short) is an ATRS $\mathcal{C} :=(\mathfrak{G}, \to)$ such that for each constant ${\mathbf{X}}$ of $\mathfrak{G}$ , there is exactly one rewrite rule where ${\mathbf{X}}$ appears, and this rule is of the form

(2.2.1) \begin{equation} {\mathbf{X}} \mathsf{x}_1 \dots \mathsf{x}_n \to \mathfrak{t}_{{\mathbf{X}}}\end{equation}

where $n \geqslant 1$ and $\mathfrak{t}_{{\mathbf{X}}}$ is a term having no constants and having all variables in $\mathbb{X}_n$ . Moreover, all rewrite rules of $\mathcal{C}$ must be of the form (2.2.1). The integer n is the of ${\mathbf{X}}$ in $\mathcal{C}$ . Some well-known terms $\mathfrak{t}_{{\mathbf{X}}}$ appearing among others in Smullyan (Reference Smullyan1985) are,

• • with order 1, $\mathfrak{t}_{{\mathbf{I}}} := \mathsf{x}_1$ , $\mathfrak{t}_{{\mathbf{M}}} := \mathsf{x}_1 \mathsf{x}_1$ ;

• • with order 2, $\mathfrak{t}_{{\mathbf{K}}} := \mathsf{x}_1$ , $\mathfrak{t}_{{\mathbf{T}}} := \mathsf{x}_2 \mathsf{x}_1$ , $\mathfrak{t}_{{\mathbf{M_1}}} := \mathsf{x}_1 \mathsf{x}_1 \mathsf{x}_2$ , $\mathfrak{t}_{{\mathbf{W}}} := \mathsf{x}_1 \mathsf{x}_1 \mathsf{x}_2$ , $\mathfrak{t}_{{\mathbf{L}}} := \mathsf{x}_1 \left(\mathsf{x}_2 \mathsf{x}_2\right)$ , $\mathfrak{t}_{{\mathbf{O}}} := \mathsf{x}_2 \left(\mathsf{x}_1 \mathsf{x}_2\right)$ , $\mathfrak{t}_{{\mathbf{U}}} := \mathsf{x}_2 \left(\mathsf{x}_1 \mathsf{x}_1 \mathsf{x}_2\right)$ ( );

• • with order 3, $\mathfrak{t}_{{\mathbf{C}}} := \mathsf{x}_1 \mathsf{x}_3 \mathsf{x}_2$ , $\mathfrak{t}_{{\mathbf{V}}} := \mathsf{x}_3 \mathsf{x}_1 \mathsf{x}_2$ , $\mathfrak{t}_{{\mathbf{B}}} := \mathsf{x}_1 \left(\mathsf{x}_2 \mathsf{x}_3\right)$ , $\mathfrak{t}_{{\mathbf{S}}} := \mathsf{x}_1 \mathsf{x}_3 \left(\mathsf{x}_2 \mathsf{x}_3\right)$ ;

• • with order 4, $\mathfrak{t}_{{\mathbf{J}}} := \mathsf{x}_1 \mathsf{x}_2 \left(\mathsf{x}_1 \mathsf{x}_4 \mathsf{x}_3\right)$ .

The constant ${\mathbf{X}}$ is if $\mathfrak{t}_{{\mathbf{X}}}$ contains at least one occurrence of each variable $\mathsf{x}_i$ for any $i \in [n]$ . The constant ${\mathbf{X}}$ is if for any $i \in [n]$ , $\mathsf{x}_i$ appears in $\mathfrak{t}_{{\mathbf{X}}}$ at depth $n + 1 - i$ . For instance, the terms $\mathfrak{t}_{{\mathbf{X}}}$ such that ${\mathbf{X}}$ are hierarchical and of order 3 or less are

(2.2.2) \begin{equation} \mathsf{x}_1 \mathsf{x}_1, \enspace \mathsf{x}_1 \mathsf{x}_1 \mathsf{x}_2, \enspace \mathsf{x}_2 \left(\mathsf{x}_1 \mathsf{x}_1\right), \enspace \mathsf{x}_1 \mathsf{x}_1 \mathsf{x}_2 \mathsf{x}_3, \enspace \mathsf{x}_2 \left(\mathsf{x}_1 \mathsf{x}_1\right) \mathsf{x}_3, \enspace \mathsf{x}_3 \left(\mathsf{x}_1 \mathsf{x}_1 \mathsf{x}_2\right), \enspace \mathsf{x}_3 \left(\mathsf{x}_2 \left(\mathsf{x}_1 \mathsf{x}_1\right)\right).\end{equation}

In particular, if ${\mathbf{X}}$ is hierarchical, then ${\mathbf{X}}$ is nonerasing. We say that $\mathcal{C}$ is (resp. ) if all constants of $\mathfrak{G}$ are nonerasing (resp. hierarchical). Other interesting properties of basic combinators are introduced in Bimbo (2011) but they do not intervene directly in this work.

Consider for instance the CLS $\mathcal{C} := (\mathfrak{G}, \to)$ where $\mathfrak{G}$ contains only the constant ${\mathbf{I}}$ where $\mathfrak{t}_{{\mathbf{I}}}$ is defined above. It is straightforward to show that $\mathcal{C}$ has the poset property. Nevertheless, $\mathcal{C}$ has not the lattice property, as suggested by the Hasse diagram shown in Figure 1A. On the other side, the CLS $\mathcal{C} := (\mathfrak{G}, \to)$ where $\mathfrak{G}$ contains only the constants ${\mathbf{K}}$ and ${\mathbf{S}}$ where $\mathfrak{t}_{{\mathbf{K}}}$ and $\mathfrak{t}_{{\mathbf{S}}}$ are defined above does not have the poset property. Indeed, $\preccurlyeq$ is not antisymmetric because by setting $ \mathfrak{t} := \mathbf{S} (\mathbf{S} (\mathbf{K} \mathbf{S}) (\mathbf{K} (\mathbf{S} \mathbf{K} \mathbf{K}))) (\mathbf{K} (\mathbf{S} \mathbf{K} \mathbf{K})),$ we have $\mathfrak{s} \preccurlyeq \mathfrak{s}'$ and $\mathfrak{s}' \preccurlyeq \mathfrak{s}$ where $\mathfrak{s} := \mathfrak{t} \mathfrak{t}(\mathfrak{t} \mathfrak{t} \mathfrak{t})$ and $\mathfrak{s}' := \mathfrak{t} \mathfrak{t} \mathfrak{t} (\mathfrak{t} \mathfrak{t} \mathfrak{t})$ . This can be seen by noticing that $\mathfrak{t} \, \mathsf{x}_1 \mathsf{x}_2 \preccurlyeq \mathsf{x}_2 \mathsf{x}_2$ . Figure 1B shows a part of the rewrite graph of $\mathcal{C}$ .

Figure 1.

Some subgraphs of rewrite graphs of some CLS.

2.2.2 Properties of CLS

Let us state some properties of CLS related to their properties of confluence, termination, and local finiteness.

Proof. Assume that $\mathfrak{t}$ and $\mathfrak{t}'$ are two $\mathfrak{G}$ -terms such that $\mathfrak{t} \Rightarrow \mathfrak{t}'$ . From the definition of $\Rightarrow$ from $\to$ provided by (2.1.7), the fact that all constants of $\mathfrak{G}$ are nonerasing implies that for any $\mathsf{x}_i \in \mathbb{X}$ , $\mathrm{deg}_{\mathsf{x}_i}(\mathfrak{t}) \geqslant 1$ if and only if $\mathrm{deg}_{\mathsf{x}_i}\left(\mathfrak{t}'\right) \geqslant 1$ . Therefore, both $\mathfrak{t}$ and $\mathfrak{t}'$ belong to $\mathfrak{T}_n(\mathfrak{G})$ where n is an integer nonsmaller than the greatest index of the variables appearing in $\mathfrak{t}$ and $\mathfrak{t}'$ . Since $\equiv$ is the reflexive, symmetric, and transitive closure of $\Rightarrow$ , the result follows.

Let us use these results to state some properties of a CLS $\mathcal{C}$ . By Proposition 2.2.1 and Bezem et al. (Reference Bezem, Klop and de Vrijer2003, Theorem 1.2.2), each $\equiv$ -equivalence class of terms of $\mathcal{C}$ admits at most one normal form. If $\mathcal{C}$ is hierarchical and has the poset property, it follows by Proposition 2.2.3 that for each term $\mathfrak{t}$ of $\mathcal{C}$ , the subposet on $\left[\mathfrak{t}\right]_\equiv$ of $\mathcal{P}_\mathcal{C}$ admits exactly one maximal element. If additionally $\mathcal{C}$ is rooted, then for each term of $\mathcal{C}$ , the subposet on $\left[\mathfrak{t}\right]_\equiv$ of $\mathcal{P}_\mathcal{C}$ admits exactly one minimal element. In this case, there is a one-to-one correspondence between the set of the minimal terms and the set of the maximal terms of $\mathcal{C}$ and this correspondence preserves the $\equiv$ -equivalence classes.

2.2.3 Models

Let $\mathcal{C} := (\mathfrak{G}, \to)$ be a CLS. A of $\mathcal{C}$ is an algebra over the abstract clone defined as the quotient of $\mathfrak{T}(\mathfrak{G})$ by the clone congruence $\equiv$ (see for instance Taylor Reference Taylor1993 for a general description of algebras over abstract clones). In more concrete terms, for this particular case of abstract clone, this is the data of a magma $(\mathcal{M}, {\star})$ such that $\mathfrak{G} \subseteq \mathcal{M}$ and, for each rule ${\mathbf{X}} \mathsf{x}_1 \dots \mathsf{x}_n \to \mathfrak{t}_{{\mathbf{X}}}$ , the axiom $ \left(\dots \left(\left({\mathbf{X}} {\star} \mathsf{x}_1\right) {\star} \mathsf{x}_2\right) \dots\right) {\star} \mathsf{x}_n = e_{{\mathbf{X}}}$ holds, where $e_{{\mathbf{X}}}$ is the expression having $\mathfrak{t}_{{\mathbf{X}}}$ as syntax tree. For instance, a model of the CLS on the constants ${\mathbf{K}}$ and ${\mathbf{S}}$ is a set $\mathcal{M}$ containing ${\mathbf{K}}$ and ${\mathbf{S}}$ , and endowed with an operation ${\star} : \mathcal{M}^2 \to \mathcal{M}$ satisfying $\left({\mathbf{K}}{\star} \mathsf{x}_1\right) {\star} \mathsf{x}_2 = \mathsf{x}_1$ and $ \left(\left({\mathbf{S}} {\star} \mathsf{x}_1\right) {\star} \mathsf{x}_2\right) {\star} \mathsf{x}_3 = \left(\mathsf{x}_1 {\star} \mathsf{x}_3\right) {\star} \left(\mathsf{x}_2 {\star} \mathsf{x}_3\right).$ Such structures are known as (Hindley and Seldin Reference Hindley and Seldin2008).

The ) of $\mathcal{C}$ is the magma $(\mathcal{M}, {\star})$ where $\mathcal{M}$ is the set $\mathfrak{T}(\mathfrak{G})/_\equiv$ and, for any $\left[\mathfrak{t}_1\right]_\equiv,\left[\mathfrak{t}_2\right]_\equiv \in \mathcal{M}$ , $\left[\mathfrak{t}_1\right]_\equiv {\star} \left[\mathfrak{t}_2\right]_\equiv$ is the $\equiv$ -equivalence class of $\mathfrak{t}_1 \mathfrak{t}_2$ where $\mathfrak{t}_1$ is any element of $\left[\mathfrak{t}_1\right]_\equiv$ and $\mathfrak{t}_2$ is any element of $\left[\mathfrak{t}_2\right]_\equiv$ . Moreover, when $\mathcal{C}$ is nonerasing, for any $n \geqslant 0$ , the of $\mathcal{C}$ is the trivial model restrained to $\equiv$ -equivalence classes of terms of $\mathfrak{T}_n(\mathfrak{G})$ . Thanks to Lemma 2.2.2, the n-trivial model is well-defined.

When $\mathcal{C}$ is hierarchical and has the poset property, as already noticed, each $\equiv$ -equivalence class contains exactly one maximal element. Therefore, the set $\mathcal{M}^{\mathrm{max}}$ of the maximal terms of $\mathfrak{T}(\mathfrak{G})$ is a set of representatives of the set of the $\equiv$ -equivalence classes and forms a model of $\mathcal{C}$ isomorphic to the trivial model. When additionally $\mathcal{C}$ is rooted, as already noticed, each $\equiv$ -equivalence class contains exactly one minimal element. For this reason, the set $\mathcal{M}^{\mathrm{min}}$ of the minimal terms of $\mathfrak{T}(\mathfrak{G})$ is a set of representatives of the set of the $\equiv$ -equivalence classes and forms a model of $\mathcal{C}$ isomorphic to the previous ones. Here also, for any $n \geqslant 0$ , we define the model $\mathcal{M}^{\mathrm{max}}_n$ (resp. $\mathcal{M}^{\mathrm{min}}_n$ ) as the restriction of $\mathcal{M}^{\mathrm{max}}$ (resp. $\mathcal{M}^{\mathrm{min}}$ ) on $\mathfrak{T}_n(\mathfrak{G})$ . The interest of these two models $\mathcal{M}^{\mathrm{max}}$ and $\mathcal{M}^{\mathrm{min}}$ relies on considerations about algorithmic complexity for the computation of the product $\mathfrak{t}_1 {\star} \mathfrak{t}_2$ where $\mathfrak{t}_1$ and $\mathfrak{t}_2$ are two terms of the models.

3.1.1 First properties

Let us present some first properties of $\mathcal{C}$ . We begin by providing a recursive description of the rewrite relation $\Rightarrow$ .

1. (i) $\mathfrak{t}_1 \Rightarrow \mathfrak{t}_1'$ and $\mathfrak{t}_2 = \mathfrak{t}_2'$ ;

2. (ii) $\mathfrak{t}_2 \Rightarrow \mathfrak{t}_2'$ and $\mathfrak{t}_1 = \mathfrak{t}_1'$ ;

3. (iii) $\mathfrak{t}_1 = {{\mathbf{M}}}$ and $\mathfrak{t}_2 = \mathfrak{t}_1' = \mathfrak{t}_2'$ .

1. (i) is locally finite;

2. (ii) has the poset property;

3. (iii) is rooted.

Let us prove that $\mathcal{C}$ has the poset property. For this, let $\theta : \mathfrak{T}(\mathfrak{G}) \to \mathbb{Z}^2$ be the map defined for any $\mathfrak{t} \in \mathfrak{T}(\mathfrak{G})$ by $ \theta(\mathfrak{t}) := \left(\mathrm{deg}(\mathfrak{t}), - \mathrm{deg}_{{{\mathbf{M}}}}(\mathfrak{t})\right). $ We denote by $\leqslant$ the lexicographic order on $\mathbb{Z}^2$ and by $\dot{+}$ the pointwise addition on $\mathbb{Z}^2$ . Let us prove by structural induction on $\mathfrak{T}(\mathfrak{G})$ that for any $\mathfrak{G}$ -terms $\mathfrak{t}$ and $\mathfrak{t}'$ , $\mathfrak{t} \ne \mathfrak{t}'$ and $\mathfrak{t} \Rightarrow \mathfrak{t}'$ implies $\theta(\mathfrak{t}) < \theta\left(\mathfrak{t}'\right)$ . By Lemma 3.1.1, we have $\mathfrak{t} = \mathfrak{t}_1 \mathfrak{t}_2$ and $\mathfrak{t}' = \mathfrak{t}_1' \mathfrak{t}_2'$ for some $\mathfrak{G}$ -terms $\mathfrak{t}_1$ , $\mathfrak{t}_2$ , $\mathfrak{t}_1'$ , and $\mathfrak{t}_2'$ , and we have the three following cases. First, if $\mathfrak{t}_1 \Rightarrow \mathfrak{t}_1'$ and $\mathfrak{t}_2 = \mathfrak{t}_2'$ , then $ \theta(\mathfrak{t}) = \theta\left(\mathfrak{t}_1\right) \dot{+} \theta\left(\mathfrak{t}_2\right) \dot{+} (1, 0) $ and $ \theta\left(\mathfrak{t}'\right) = \theta\left(\mathfrak{t}_1'\right) \dot{+} \theta\left(\mathfrak{t}_2\right) \dot{+} (1, 0). $ Since, by induction hypothesis, $\theta\left(\mathfrak{t}_1\right) < \theta\left(\mathfrak{t}_1'\right)$ , we have $\theta(\mathfrak{t}) < \theta\left(\mathfrak{t}'\right)$ . Second, if $\mathfrak{t}_2 \Rightarrow \mathfrak{t}_2'$ and $\mathfrak{t}_1 = \mathfrak{t}_1'$ , the same arguments as the previous ones (by interchanging the indices 1 and 2 in the concerned terms) apply. Finally, if $\mathfrak{t}_1 = {{\mathbf{M}}}$ and $\mathfrak{t}_2 = \mathfrak{t}_1' = \mathfrak{t}_2'$ , then $ \theta(\mathfrak{t}) = \theta\left(\mathfrak{t}_2\right) \dot{+} (1, -1) $ and $ \theta\left(\mathfrak{t}'\right) = \theta\left(\mathfrak{t}_2\right) \dot{+} \theta\left(\mathfrak{t}_2\right) \dot{+} (1, 0). $ Since $\mathfrak{t} \ne \mathfrak{t}'$ , we have $\mathfrak{t}_2 \ne {{\mathbf{M}}}$ so that $\theta(\mathfrak{t}) < \theta\left(\mathfrak{t}'\right)$ . This implies that $\preccurlyeq$ is antisymmetric, so that (ii) holds.

To prove that $\mathcal{C}$ is rooted, we consider the rewrite relation $\to'$ obtained by inverting $\to$ . Thus, $\to'$ satisfies $\mathsf{x}_1 \mathsf{x}_1 \to' {{\mathbf{M}}} \mathsf{x}_1$ . This ATRS $\left(\mathfrak{T}(\mathfrak{G}), \to'\right)$ does not admit any overlapping term (see Bezem et al. Reference Bezem, Klop and de Vrijer2003, Chapter 2). Therefore, it is confluent. A consequence of (i), is that this ATRS has only finite $\equiv'$ -equivalence classes. By using additionally Bezem et al. (Reference Bezem, Klop and de Vrijer2003), Theorem 1.2.2, each $\equiv'$ -equivalence class admits exactly one term $\mathfrak{t}$ such that for any $\mathfrak{t}' \in \left[\mathfrak{t}\right]_{\equiv'}$ , $\mathfrak{t}' \preccurlyeq' \mathfrak{t}$ . This implies that in $\mathcal{C}$ , each $\equiv$ -equivalence class admits exactly one minimal term. Therefore, (iii) holds.

By Proposition 3.1.2, $\mathcal{P}_\mathcal{C}$ is a well-defined poset, called . From now, we shall simply write $\mathcal{P}$ instead of $\mathcal{P}_\mathcal{C}$ . We have the following recursive description of $\preccurlyeq$ .

1. (i) $\mathfrak{t} = {{\mathbf{M}}} = \mathfrak{t}'$ ;

2. (ii) $\mathfrak{t} = \mathsf{x}_i = \mathfrak{t}'$ for an $\mathsf{x}_i \in \mathbb{X}$ ;

3. (iii) $\mathfrak{t} = \mathfrak{t}_1 \mathfrak{t}_2$ , $\mathfrak{t}' = \mathfrak{t}_1' \mathfrak{t}_2'$ , $\mathfrak{t}_1 \preccurlyeq \mathfrak{t}_1'$ , and $\mathfrak{t}_2 \preccurlyeq \mathfrak{t}_2'$ where $\mathfrak{t}_1, \mathfrak{t}_1', \mathfrak{t}_2, \mathfrak{t}_2' \in \mathfrak{T}(\mathfrak{G})$ ;

4. (iv) $\mathfrak{t} = {{\mathbf{M}}} \mathfrak{t}_2$ , $\mathfrak{t}' = \mathfrak{t}_1' \mathfrak{t}_2'$ , $\mathfrak{t}_2 \preccurlyeq \mathfrak{t}_1'$ , and $\mathfrak{t}_2 \preccurlyeq \mathfrak{t}_2'$ where $\mathfrak{t}_1', \mathfrak{t}_2, \mathfrak{t}_2' \in \mathfrak{T}(\mathfrak{G})$ .

1. (i) The term $\mathfrak{t}$ is a maximal element of $\mathcal{P}$ if and only if $\mathfrak{t}$ avoids ${{\mathbf{M}}} \left(\mathsf{x}_1 \mathsf{x}_2\right)$ and suffix-avoids ${{\mathbf{M}}} \mathsf{x}_1$ .

2. (ii) The term $\mathfrak{t}$ is a minimal element of $\mathcal{P}$ if and only if $\mathfrak{t}$ avoids $\left(\mathsf{x}_1 \mathsf{x}_2\right) \left(\mathsf{x}_1 \mathsf{x}_2\right)$ and suffix-avoids $\mathsf{x}_1 \mathsf{x}_1$ .

The term $\mathfrak{t}$ is minimal in $\mathcal{P}$ if and only if $\mathfrak{t}' \Rightarrow \mathfrak{t}$ implies that $\mathfrak{t}' = \mathfrak{t}$ . By Lemma 3.1.1, this is equivalent to the fact $\mathfrak{t}$ is minimal in $\mathcal{P}$ if and only if when $\mathfrak{t}$ has an internal node such that its two children are equal, these two children are necessarily equal to ${{\mathbf{M}}}$ . Therefore, (ii) holds.

3.1.2 Some models

We begin this discussion about models of $\mathcal{C}$ by a very simple observation: any idempotent monoid $(\mathcal{M}, \cdot, e)$ is a model of $\mathcal{C}$ . Indeed, by identifying ${{\mathbf{M}}}$ with e (the unit of $\mathcal{M}$ ) and by identifying ${\star}$ with $\cdot$ , we have for any $x \in \mathcal{M}$ , $ {{\mathbf{M}}} {\star} x = e \cdot x = x = x \cdot x = x {\star} x.$

Besides, since $\mathcal{C}$ is hierarchical and has, by Proposition 3.1.2, the poset property, this CLS admits the model $\mathcal{M}^{\mathrm{max}}$ described in Section 2.2.3. More specifically, this model is such that $\mathcal{M}^{\mathrm{max}}$ is the set of the maximal elements of $\mathcal{P}$ , and, by Proposition 3.1.4, for any $\mathfrak{t}_1, \mathfrak{t}_2 \in \mathcal{M}^{\mathrm{max}}$ ,

(3.1.1) \begin{equation} \mathfrak{t}_1 {\star} \mathfrak{t}_2 = \begin{cases} \mathfrak{t}_2 \mathfrak{t}_2 & \mbox{ if }\; \mathfrak{t}_1 = {{\mathbf{M}}}, \\ \mathfrak{t}_1 \mathfrak{t}_2 & \mbox{otherwise}. \end{cases}\end{equation}

Since by Proposition 3.1.2, $\mathcal{C}$ is also rooted, $\mathcal{C}$ admits the model $\mathcal{M}^{\mathrm{min}}$ described in Section 2.2.3. This model is such that $\mathcal{M}^{\mathrm{min}}$ is the set of the minimal elements of $\mathcal{P}$ , and, by Proposition 3.1.4, for any $\mathfrak{t}_1, \mathfrak{t}_2 \in \mathcal{M}^{\mathrm{min}}$ ,

(3.1.2) \begin{equation} \mathfrak{t}_1 {\star} \mathfrak{t}_2 = \begin{cases} {{\mathbf{M}}} \mathfrak{t}_2 & \mbox{ if }\; \mathfrak{t}_1 = \mathfrak{t}_2, \\ \mathfrak{t}_1 \mathfrak{t}_2 & \mbox{otherwise}. \end{cases}\end{equation}

By representing $\mathfrak{G}$ -terms directly has binary trees, the computations in $\mathcal{M}^{\mathrm{max}}$ have a better time complexity than in $\mathcal{M}^{\mathrm{min}}$ because to compute $\mathfrak{t}_1{\star} \mathfrak{t}_2$ in $\mathcal{M}^{\mathrm{min}}$ , we need to decide if $\mathfrak{t}_1$ and $\mathfrak{t}_2$ are equal. Nevertheless, in return, the term $\mathfrak{t}_1 {\star} \mathfrak{t}_2$ produced by a computation in $\mathcal{M}^{\mathrm{min}}$ has a number of internal nodes equal as or smaller than the analogous computation in $\mathcal{M}^{\mathrm{max}}$ .

3.2.1 Duplicative forests

A is a planar rooted tree such that each internal node is either a or a . A is a word $\mathfrak{f} = \mathfrak{f}(1) \dots \mathfrak{f}(\ell)$ , $\ell \geqslant 0$ , of duplicative trees. In particular, the empty word $\epsilon$ is the . We denote by $\mathcal{D}$ (resp. $\mathcal{D}^*$ ) the set of such trees (resp. forests). The $\mathrm{ht}(\mathfrak{f})$ of $\mathfrak{f}$ is the number of internal nodes in a longest path following edges connecting a node to one of its child. In the sequel, we shall write expressions using some occurrences of : each such expression denotes the two expressions obtained by replacing simultaneously all either by or by . The is the unary operation on $\mathcal{D}^*$ such that for any $\mathfrak{f} \in\mathcal{D}^*$ , is the duplicative tree obtained by grafting the roots of the duplicative trees of $\mathfrak{f}$ on a common root node . The is the binary operation ${\centerdot}$ on $\mathcal{D}^*$ such that for any $\mathfrak{f}_1, \mathfrak{f}_2 \in\mathcal{D}^*$ , $\mathfrak{f}_1 {\centerdot} \mathfrak{f}_2$ is the duplicative forest made of the trees of $\mathfrak{f}_1$ and then of the trees of $\mathfrak{f}_2$ .

3.2.2 A poset on duplicative forests

Let be the binary relation on $\mathcal{D}^*$ defined recursively as follows. For any $\mathfrak{f}, \mathfrak{f}' \in \mathcal{D}^*$ , we have if $\mathfrak{f}$ and $\mathfrak{f}'$ have the same length $\ell \geqslant 1$ and

• • either $\ell = 1$ , and where $\mathfrak{g} \in \mathcal{D}^*$ ;

• • or $\ell = 1$ , , where $\mathfrak{g}, \mathfrak{g}' \in \mathcal{D}^*$ and ;

• • or $\ell \geqslant 2$ and there is a $j \in [\ell]$ such that , and for all $i \in [\ell] \setminus \{\,j\}$ , $\mathfrak{f}(i) = \mathfrak{f}'(i)$ .

We observe that if and only if $\mathfrak{f}'$ can be obtained from $\mathfrak{f}$ by selecting a white node of $\mathfrak{f}$ , by turning it into black, and by duplicating its sequence of descendants. For instance, we have

(3.2.1)

Observe also that in this case, there are more black nodes in $\mathfrak{f}'$ than in $\mathfrak{f}$ . Hence, the reflexive and transitive closure $\ll$ of is antisymmetric so that $(\mathcal{D}^*, \ll)$ is a poset. We call this poset the . For any $\mathfrak{f} \in\mathcal{D}^*$ , we denote by $\mathcal{D}^*(\mathfrak{f})$ the subposet of the duplicative forest poset on the set $\left\{\mathfrak{f}' \in \mathcal{D}^* : \mathfrak{f}\ll \mathfrak{f}'\right\}$ . Figure 3 shows the Hasse diagram of the poset $\mathcal{D}^*(\mathfrak{f})$ where $\mathfrak{f}$ is a certain duplicative forest. According to this Hasse diagram, the duplicative forest poset is not graded. We have the following recursive description of $\ll$ .

Figure 3.

The Hasse diagram of a maximal interval of the duplicative forest poset.

1. (i) $\ell = 0$ ;

2. (ii) $\ell = 1$ , and where $\mathfrak{g}, \mathfrak{g}', \mathfrak{g}'' \in \mathcal{D}^*$ , $\mathfrak{g} \ll \mathfrak{g}'$ , and $\mathfrak{g} \ll \mathfrak{g}''$ ;

3. (iii) $\ell = 1$ , , where $\mathfrak{g}, \mathfrak{g}' \in \mathcal{D}^*$ and $\mathfrak{g} \ll \mathfrak{g}'$ ;

4. (iv) $\ell \geqslant 2$ and $\mathfrak{f}(i) \ll \mathfrak{f}'(i)$ for all $i \in [\ell]$ .

A first consequence of Lemma 3.2.1 is that for any $\mathfrak{f}, \mathfrak{f}' \in \mathcal{D}^*$ , $\mathfrak{f} \ll \mathfrak{f}'$ implies $\mathrm{ht}(\mathfrak{f}) = \mathrm{ht}\left(\mathfrak{f}'\right)$ .

3.2.3 Lattices on duplicative forests

We use in the sequel the usual notions and notations about lattices (see for instance Stanley Reference Stanley2011). Let $\wedge$ and $\vee$ be the two binary, commutative, and associative partial operations on $\mathcal{D}^*$ defined recursively, for any $\ell \geqslant 0$ , $\mathfrak{f}_1, \dots, \mathfrak{f}_\ell \in \mathcal{D}$ , $\mathfrak{f}_1',\dots, \mathfrak{f}_\ell' \in \mathcal{D}$ , and $\mathfrak{f}, \mathfrak{f}', \mathfrak{f}'' \in\mathcal{D}^*$ , by

(3.2.2a) \begin{equation} \mathfrak{f}_1 {\centerdot} \dots {\centerdot} \mathfrak{f}_\ell \wedge \mathfrak{f}_1' {\centerdot} \dots {\centerdot} \mathfrak{f}_\ell' := \left(\mathfrak{f}_1 \wedge \mathfrak{f}_1'\right) {\centerdot} \dots {\centerdot} \left(\mathfrak{f}_\ell \wedge \mathfrak{f}_\ell'\right),\end{equation}

(3.2.2b)

(3.2.2c)

and

(3.2.3a) \begin{equation} \mathfrak{f}_1 {\centerdot} \dots {\centerdot} \mathfrak{f}_\ell \vee \mathfrak{f}_1' {\centerdot} \dots {\centerdot} \mathfrak{f}_\ell' := \left(\mathfrak{f}_1 \vee \mathfrak{f}_1'\right) {\centerdot} \dots {\centerdot} \left(\mathfrak{f}_\ell \vee \mathfrak{f}_\ell'\right),\end{equation}

(3.2.3b)

(3.2.3c)

By Proposition 3.2.2, for any $\mathfrak{f} \in\mathcal{D}^*$ , each poset $\mathcal{D}^*(\mathfrak{f})$ is a lattice. We call it the of $\mathfrak{f}$ .

Let $\texttt{pr} : \mathcal{D}^* \to \mathcal{D}^*$ be the map defined recursively, for any $\ell \geqslant 0$ , $\mathfrak{f}_1, \dots, \mathfrak{f}_\ell \in\mathcal{D}^*$ , and $\mathfrak{f} \in \mathcal{D}^*$ , by

(3.2.4a) \begin{equation} \texttt{pr}\left(\mathfrak{f}_1 {\centerdot} \dots {\centerdot} \mathfrak{f}_\ell\right) := \texttt{pr}\left(\mathfrak{f}_1\right) {\centerdot} \dots {\centerdot} \texttt{pr}\left(\mathfrak{f}_\ell\right),\end{equation}

(3.2.4b)

(3.2.4c)

The duplicative forest $\texttt{pr}(\mathfrak{f})$ is the of $\mathfrak{f}$ . This forest has by construction no occurrence of any . For instance,

(3.2.5)

For any $d \geqslant 0$ , the is the duplicative forest $\mathfrak{l}_d$ defined recursively by $\mathfrak{l}_0 := \epsilon$ and, for any $d \geqslant 1$ , by . Let also

(3.2.6) \begin{equation} \mathcal{L} := \bigcup_{d \geqslant 0} \mathcal{D}^*\left(\mathfrak{l}_d\right).\end{equation}

By definition, $\mathcal{L}$ is the set of the duplicative forests that are equal as or greater than a d-ladder for a $d \geqslant 0$ .

An important consequence of Lemmas 3.2.3 and 3.2.4 is that for any $\mathfrak{f} \in \mathcal{D}^*$ , there exists $d \geqslant 0$ such that $\mathcal{D}^*(\mathfrak{f})$ is isomorphic as a poset to a maximal interval of $\mathcal{D}^* \left(\mathfrak{l}_d\right)$ .

3.3.1 From terms to duplicative forests

Let $\texttt{fr} : \mathfrak{T}(\mathfrak{G}) \to \mathcal{D}^*$ be the map defined recursively, for any $\mathsf{x}_i \in \mathbb{X}$ and $\mathfrak{t}, \mathfrak{t}' \in\mathfrak{T}(\mathfrak{G})$ , by

(3.3.1a) \begin{equation} \texttt{fr}\left(\mathsf{x}_i\right) := \epsilon,\end{equation}

(3.3.1b) \begin{equation} \texttt{fr}({{\mathbf{M}}}) := \epsilon,\end{equation}

(3.3.1c)

For instance,

(3.3.2)

Intuitively, $\texttt{fr}(\mathfrak{t})$ is the duplicative forest obtained from $\mathfrak{t}$ by the following process: replace each internal node of $\mathfrak{t}$ having ${{\mathbf{M}}}$ as left child and having a right child different from ${{\mathbf{M}}}$ by a , replace each other internal node of $\mathfrak{t}$ by a , and remove all the leaves. Immediately from the definition, we observe that this map is not injective. Moreover, again directly from the definition, any duplicative forest $\mathfrak{f}$ in the image of $\texttt{fr}$ is such that each white node of $\mathfrak{f}$ has no more than one child.

Figure 4 shows the poset $\mathcal{P}(\mathfrak{t})$ for a $\mathfrak{G}$ -term $\mathfrak{t}$ and the isomorphic poset $\mathcal{D}^*(\texttt{fr}(\mathfrak{t}))$ .

Figure 4.

A maximal interval of the Mockingbird poset from the term $\mathfrak{t} := {{\mathbf{M}}} \left(\mathsf{x}_1 \left({{\mathbf{M}}} \mathsf{x}_2\right)\right) \left({{\mathbf{M}}} {{\mathbf{M}}}\right)$ and its realization as a maximal interval in the duplicative forest poset.

The of order $d \geqslant 0$ is the lattice $\mathrm{M}(d) :=\mathcal{P}\left(\mathfrak{r}_d\right)$ where $\mathfrak{r}_d$ is the term recursively defined by $\mathfrak{r}_0 := {{\mathbf{M}}}$ and, for any $d \geqslant 1$ , by $\mathfrak{r}_d := {{\mathbf{M}}} \mathfrak{r}_{d - 1}$ . Figure 5 shows the Hasse diagrams of the first Mockingbird lattices.

Figure 5.

The Hasse diagrams of the Mockingbird lattices $\mathrm{M}(d)$ for .

3.3.5 justifies the fact that the study of the Mockingbird lattices is universal enough because these lattices contain as maximal interval all duplicative forest lattices.

The Mockingbird lattices are not graded and not self-dual. Since they are not graded, they are not distributive neither. Moreover, they are not semi-distributive. For instance, in $\mathrm{M}(3)$ , by setting $\mathfrak{t}_1 := {{\mathbf{M}}}({{\mathbf{M}}}{{\mathbf{M}}}({{\mathbf{M}}}{{\mathbf{M}}}))$ , $\mathfrak{t}_2 :={{\mathbf{M}}}{{\mathbf{M}}}({{\mathbf{M}}}{{\mathbf{M}}})({{\mathbf{M}}}({{\mathbf{M}}}{{\mathbf{M}}}))$ , and $\mathfrak{t}_3 := {{\mathbf{M}}}({{\mathbf{M}}}{{\mathbf{M}}})({{\mathbf{M}}}{{\mathbf{M}}}({{\mathbf{M}}}{{\mathbf{M}}}))$ , we have $\mathfrak{t}_1 \wedge\mathfrak{t}_2 = \mathfrak{t}_1 \wedge \mathfrak{t}_3$ but $\mathfrak{t}_1 \wedge \left(\mathfrak{t}_2 \vee \mathfrak{t}_3\right) \ne\mathfrak{t}_1 \wedge \mathfrak{t}_2$ , contradicting one of the required relations to have this property.

4.1.1 Formal power series over sets

For any set X, let $\mathbb{K} \left\langle X\right\rangle$ be the linear span of X. The dual space of $\mathbb{K}\left\langle X\right\rangle$ is denoted by $\mathbb{K} \left\langle\left\langle X\right\rangle\right\rangle$ and is by definition the space of the maps $\mathbf{F} : X \to \mathbb{K}$ , called . The coefficient $\mathbf{F}(x)$ of any $x \in X$ is denoted by $\left\langle x, \mathbf{F}\right\rangle$ . The of $\mathbf{F}$ is the set $\mathrm{Supp}(\mathbf{F}) := \left\{x \in X : \left\langle x, \mathbf{F}\right\rangle \ne 0\right\}$ . The of any subset X’ of X is the series $\mathbf{c}\left(X'\right)$ having X’ as support and such that the coefficient of each $x \in X'$ is 1. For any $k \geqslant 0$ , ${{\mathrm T}^{k}} \mathbb{K} \left\langle\left\langle X\right\rangle\right\rangle$ is the k-th tensor power of $\mathbb{K} \left\langle\left\langle X\right\rangle\right\rangle$ . Elements of this space are possibly infinite linear combinations of tensors $x_1 \otimes \dots \otimes x_k$ , where for any $i \in [k]$ , $x_i \in X$ . The of $\mathbb{K} \left\langle\left\langle X\right\rangle\right\rangle$ is the space

(4.1.1) \begin{equation} {{\mathrm T}^{*}} \mathbb{K} \left\langle\left\langle X\right\rangle\right\rangle := \bigoplus_{k \geqslant 0} {{\mathrm T}^{k}} \mathbb{K} \left\langle\left\langle X\right\rangle\right\rangle.\end{equation}

This space is endowed with the tensor product $\otimes$ so that $\left({{\mathrm T}^{*}} \mathbb{K} \left\langle\left\langle X\right\rangle\right\rangle,\otimes\right)$ is a unital associative algebra, admitting $1 \in \mathbb{K}$ as unit.

A linear map $\phi : {{\mathrm T}^{k_1}} \mathbb{K} \left\langle\left\langle X\right\rangle\right\rangle \to {{\mathrm T}^{k_2}} \mathbb{K} \left\langle\left\langle X\right\rangle\right\rangle$ , $k_1, k_2 \geqslant 0$ , is a on $\mathbb{K} \left\langle\left\langle X\right\rangle\right\rangle$ . To lighten the notation, when $\phi$ is a (2, 1)-operation on $\mathbb{K} \left\langle\left\langle X\right\rangle\right\rangle$ , we shall sometimes use $\phi$ as an infix operation by writing $\mathbf{F}_1 \, \phi \, \mathbf{F}_2$ instead of $\phi\left(\mathbf{F}_1\otimes \mathbf{F}_2\right)$ for any $\mathbf{F}_1, \mathbf{F}_2 \in \mathbb{K} \left\langle\left\langle X\right\rangle\right\rangle$ . The is the (1, 2)-operation $\Delta$ on $\mathbb{K} \left\langle\left\langle X\right\rangle\right\rangle$ satisfying $\Delta(x) = x\otimes x$ for any $x \in X$ . When X is endowed with an n-ary operation ${\bullet} : X^n\to X$ , $n \geqslant 0$ , for any $k \geqslant 0$ , the of ${\bullet}$ is the $(nk, k)$ -operation ${{{\bullet}}^{\otimes_{k}}}$ on $\mathbb{K} \left\langle\left\langle X\right\rangle\right\rangle$ satisfying

(4.1.2) \begin{equation} {{{\bullet}}^{\otimes_{k}}} \left( x_{1, 1} \otimes \dots \otimes x_{1, k} \otimes \dots \otimes x_{n, 1} \otimes \dots \otimes x_{n, k}\right) = {\bullet}\left(x_{1, 1}, \dots, x_{n, 1}\right) \otimes \dots \otimes {\bullet}\left(x_{k, 1}, \dots, x_{n, k}\right)\end{equation}

for any $x_{i, j} \in X$ , $i \in [n]$ , and $j \in [k]$ . To lighten the notation, we shall write ${{{\bullet}}^{\otimes_{}}}$ for ${{{\bullet}}^{\otimes_{1}}}$ .

4.1.2 Generating series

The space of the usual power series on the formal parameter $\mathsf{z}$ is denoted by $\mathbb{K}\left\langle\left\langle\mathsf{z}\right\rangle\right\rangle$ . For any $F, F' \in \mathbb{K} \left\langle\left\langle\mathsf{z}\right\rangle\right\rangle$ , $F\left[\mathsf{z} := F'\right]$ is the series of $\mathbb{K} \left\langle\left\langle\mathsf{z}\right\rangle\right\rangle$ obtained by substituting F’ for $\mathsf{z}$ in F. The is the binary operation ${\boxtimes}$ on $\mathbb{K} \left\langle\left\langle\mathsf{z}\right\rangle\right\rangle$ defined linearly for any $n_1, n_2 \geqslant 0$ by

(4.1.3) \begin{equation} \mathsf{z}^{n_1} {\boxtimes} \mathsf{z}^{n_2} := \pmb{\left[\right.}n_1 = n_2\pmb{\left.\right]} \, z^{n_1}.\end{equation}

The is the binary operation ${\uparrow}$ on $\mathbb{K} \left\langle\left\langle\mathsf{z}\right\rangle\right\rangle$ defined linearly for any $n_1, n_2 \geqslant 0$ by $\mathsf{z}^{n_1} {\uparrow} \mathsf{z}^{n_2} := \mathsf{z}^{\max\left\{n_1, n_2\right\}}$ . Observe that for any $F \in \mathbb{K} \left\langle\left\langle\mathsf{z}\right\rangle\right\rangle$ and $n \geqslant 0$ ,

(4.1.4) \begin{equation} \left\langle\mathsf{z}^n, F {\uparrow} F\right\rangle = \left\langle\mathsf{z}^n, F\right\rangle^2 + 2 \left\langle\mathsf{z}^n, F\right\rangle \sum_{i \in [n]} \left\langle\mathsf{z}^{i - 1}, F\right\rangle.\end{equation}

4.1.3 Formal power series and enumeration

If X is endowed with a map $\omega : X \to \mathbb{N}$ , the is the partial map $\mathrm{en}_\omega : {{\mathrm T}^{*}} \mathbb{K} \left\langle\left\langle X\right\rangle\right\rangle \to \mathbb{K} \left\langle\left\langle\mathsf{z}\right\rangle\right\rangle$ defined linearly for any $k \geqslant 1$ and $x_1, \dots, x_k \in X$ by

(4.1.5) \begin{equation} \mathrm{en}_\omega\left(x_1 \otimes \dots \otimes x_k\right) := \mathsf{z}^{\omega\left(x_1\right)} {\uparrow} \dots {\uparrow} \mathsf{z}^{\omega\left(x_k\right)}.\end{equation}

For any $\mathbf{F} \in {{\mathrm T}^{*}} \mathbb{K} \left\langle\left\langle X\right\rangle\right\rangle$ , the generating series $\mathrm{en}_\omega(\mathbf{F})$ is the of $\mathbf{F}$ .

In the sequel, we shall use the following strategy to enumerate a set X w.r.t. such a map $\omega$ : we shall provide a description of $\mathbf{c}(X)$ , then deduce a description of $\mathrm{en}_\omega(\mathbf{c}(X))$ , and finally deduce from this a formula to compute the coefficients $\left\langle\mathsf{z}^n,\mathrm{en}_\omega(\mathbf{c}(X))\right\rangle$ , $n \geqslant 0$ .

4.2.1 Series of terms and operations

Recall that ${\star}$ is the binary operation on $\mathfrak{T}(\mathfrak{G})$ such that for any $\mathfrak{t}_1, \mathfrak{t}_2 \in \mathfrak{T}(\mathfrak{G})$ , $\mathfrak{t}_1 {\star} \mathfrak{t}_2$ is the $\mathfrak{G}$ -term $\mathfrak{t}_1 \mathfrak{t}_2$ having $\mathfrak{t}_1$ as left subtree and $\mathfrak{t}_2$ as right subtree. Observe that for any $\mathbf{F}_1, \mathbf{F}_2 \in \mathbb{K}\left\langle\left\langle\mathfrak{T}(\mathfrak{G})\right\rangle\right\rangle$ ,

(4.2.1) \begin{equation} \mathrm{en}_\mathrm{deg} \left(\mathbf{F}_1 {{{\star}}^{\otimes_{}}} \mathbf{F}_2\right) = \mathsf{z} \, \mathrm{en}_\mathrm{deg}\left(\mathbf{F}_1\right) \, \mathrm{en}_\mathrm{deg}\left(\mathbf{F}_2\right)\end{equation}

and

(4.2.2) \begin{equation} \mathrm{en}_\mathrm{ht} \left(\mathbf{F}_1 {{{\star}}^{\otimes_{}}} \mathbf{F}_2\right) = \mathsf{z} \, \left( \mathrm{en}_\mathrm{ht} \left(\mathbf{F}_1\right) {\uparrow} \mathrm{en}_\mathrm{ht} \left(\mathbf{F}_2\right)\right).\end{equation}

Observe also that for any $\mathbf{F} \in \mathbb{K} \left\langle\left\langle\mathfrak{T}(\mathfrak{G})\right\rangle\right\rangle$ ,

(4.2.3) \begin{equation} \mathrm{en}_\mathrm{deg} \left({{{\star}}^{\otimes_{}}}(\Delta(\mathbf{F}))\right) = \mathsf{z} \, \left(\mathrm{en}_\mathrm{deg}(\mathbf{F})\left[\mathsf{z} := \mathsf{z}^2\right]\right)\end{equation}

and

(4.2.4) \begin{equation} \mathrm{en}_{\mathrm{ht}} \left({{{\star}}^{\otimes_{}}}(\Delta(\mathbf{F}))\right) = \mathsf{z} \, \mathrm{en}_{\mathrm{ht}}(\mathbf{F}).\end{equation}

4.2.2 Three series of terms

In order to achieve the objectives described above, we begin by providing equations satisfied by the characteristic series $\mathbf{F}_{\max}$ of the closed maximal terms of $\mathcal{P}$ , the characteristic series $\mathbf{F}_{\min}$ of the closed minimal terms of $\mathcal{P}$ , and the characteristic series $\mathbf{F}_{\mathrm{iso}}$ of the closed isolated terms of $\mathcal{P}$ .

Proposition 4.2.1. The characteristic series $\mathbf{F}_{\max}$ satisfies

(4.2.5) \begin{equation} \mathbf{F}_{\max} = {{\mathbf{M}}} + {{\mathbf{M}}} {{\mathbf{M}}} + \mathbf{F}_{\max} {{{\star}}^{\otimes_{}}} \mathbf{F}_{\max} - {{\mathbf{M}}} {{{\star}}^{\otimes_{}}} \mathbf{F}_{\max}. \end{equation}

Proof. By using the description of Proposition 3.1.4 for the set S of closed maximal elements of $\mathcal{P}$ , we have

(4.2.6) \begin{equation} \mathbf{F}_{\max} = {{\mathbf{M}}} + \sum_{\mathfrak{s}_1, \mathfrak{s}_2 \in S} \mathfrak{s}_1 \mathfrak{s}_2 - \sum_{\mathfrak{s}_3 \in S \setminus \{{{\mathbf{M}}}\}} {{\mathbf{M}}} \mathfrak{s}_3 = {{\mathbf{M}}} + \mathbf{F}_{\max} {{{\star}}^{\otimes_{}}} \mathbf{F}_{\max} - {{\mathbf{M}}} {{{\star}}^{\otimes_{}}} \left(\mathbf{F}_{\max} - {{\mathbf{M}}}\right). \end{equation}

This leads to (4.2.5).

Proposition 4.2.2. The characteristic series $\mathbf{F}_{\min}$ satisfies

(4.2.7) \begin{equation} \mathbf{F}_{\min} = {{\mathbf{M}}} + {{\mathbf{M}}} {{\mathbf{M}}} + \mathbf{F}_{\min} {{{\star}}^{\otimes_{}}} \mathbf{F}_{\min} - {{{\star}}^{\otimes_{}}}\left(\Delta(\mathbf{F}_{\min})\right). \end{equation}

Proof. By using the description of Proposition 3.1.4 for the set S of closed minimal elements of $\mathcal{P}$ , we have

(4.2.8) \begin{equation} \mathbf{F}_{\min} = {{\mathbf{M}}} + \sum_{\mathfrak{s}_1, \mathfrak{s}_2 \in S} \mathfrak{s}_1 \mathfrak{s}_2 - \sum_{\mathfrak{s}_3 \in S \setminus \{{{\mathbf{M}}}\}} \mathfrak{s}_3 \mathfrak{s}_3 = {{\mathbf{M}}} + \mathbf{F}_{\min} {{{\star}}^{\otimes_{}}} \mathbf{F}_{\min} - {{{\star}}^{\otimes_{}}}\left(\Delta\left(\mathbf{F}_{\min} - {{\mathbf{M}}}\right)\right). \end{equation}

This leads to (4.2.7).

Proposition 4.2.3. The characteristic series $\mathbf{F}_{\mathrm{iso}}$ satisfies

(4.2.9) \begin{equation} \mathbf{F}_{\mathrm{iso}} = {{\mathbf{M}}} + 2 {{\mathbf{M}}} {{\mathbf{M}}} + \mathbf{F}_{\mathrm{iso}} {{{\star}}^{\otimes_{}}} \mathbf{F}_{\mathrm{iso}} - {{\mathbf{M}}} {{{\star}}^{\otimes_{}}} \mathbf{F}_{\mathrm{iso}} - {{{\star}}^{\otimes_{}}}\left(\Delta\left(\mathbf{F}_{\mathrm{iso}}\right)\right). \end{equation}

Proof. By using the description of Proposition 3.1.4 for the set $S_1$ (resp. $S_2$ ) of the closed maximal (resp. minimal) elements of $\mathcal{P}$ , the set of the closed isolated elements of $\mathcal{P}$ is the set $S = S_1 \cap S_2$ and we have

(4.2.10) \begin{equation} \begin{split} \mathbf{F}_{\mathrm{iso}} & = {{\mathbf{M}}} + \sum_{\mathfrak{s}_1, \mathfrak{s}_2 \in S} \mathfrak{s}_1 \mathfrak{s}_2 - \sum_{\mathfrak{s}_3 \in S \setminus \{{{\mathbf{M}}}\}} {{\mathbf{M}}} \mathfrak{s}_3 - \sum_{\mathfrak{s}_4 \in S \setminus \{{{\mathbf{M}}}\}} \mathfrak{s}_4 \mathfrak{s}_4 \\ & = {{\mathbf{M}}} + \mathbf{F}_{\mathrm{iso}} {{{\star}}^{\otimes_{}}} \mathbf{F}_{\mathrm{iso}} - {{\mathbf{M}}} {{{\star}}^{\otimes_{}}} \left(\mathbf{F}_{\mathrm{iso}} - {{\mathbf{M}}}\right) - {{{\star}}^{\otimes_{}}}\left(\Delta\left(\mathbf{F}_{\mathrm{iso}} - {{\mathbf{M}}}\right)\right). \end{split} \end{equation}

This leads to (4.2.9).

4.2.3 deg-enumerations

A consequence of Proposition 4.2.1 and of (4.2.1) is that the deg-enumeration $\mathsf{D}_{\max}$ of $\mathbf{F}_{\max}$ , enumerating the closed maximal elements of $\mathcal{P}$ w.r.t. their degrees, satisfies

(4.2.11) \begin{equation} \mathsf{D}_{\max} = 1 + \mathsf{z} + \mathsf{z} \mathsf{D}_{\max}^2 - \mathsf{z} \mathsf{D}_{\max}.\end{equation}

We deduce from this that the number of these terms of degree $d \geqslant 0$ is $\mathbf{d}_{\max}(d)$ where $\mathbf{d}_{\max}$ is the integer sequence satisfying $\mathbf{d}_{\max}(0) = \mathbf{d}_{\max}(1) = 1$ and, for any $d \geqslant 2$ ,

(4.2.12)

The first numbers are

(4.2.13) \begin{equation} 1, 1, 1, 2, 4, 9, 21, 51,\end{equation}

form Sequence of Sloane (https://oeis.org/), and are Motzkin numbers. A is a planar rooted tree made of nodes of arity 0, 1, or 2. It is well-known that the sets of these trees having exactly $d \geqslant 1$ nodes are enumerated by Motzkin numbers (see Dulucq and Penaud Reference Dulucq and Penaud2002 for instance). Given a closed maximal term $\mathfrak{t}$ , it is easy to see that $\texttt{fr}(\mathfrak{t})$ contains only black nodes and that it is a Motzkin tree. It is also easy to check that $\texttt{fr}$ is a bijection between the set of the closed maximal terms of degree $d \geqslant 1$ and the set of the Motzkin trees with d nodes.

Besides, a consequence of Proposition 4.2.2, (4.2.1), and (4.2.3) is that the deg-enumeration $\mathsf{D}_{\min}$ of $\mathbf{F}_{\min}$ , enumerating the closed minimal elements of $\mathcal{P}$ w.r.t. their degrees, satisfies

(4.2.14) \begin{equation} \mathsf{D}_{\min} = 1 + \mathsf{z} + \mathsf{z} \mathsf{D}_{\min}^2 - \mathsf{z} \left(\mathsf{D}_{\min}\left[\mathsf{z} := \mathsf{z}^2\right]\right).\end{equation}

We deduce from this that the number of these terms of degree $d \geqslant 0$ is $\mathbf{d}_{\min}(d)$ where $\mathbf{d}_{\min}$ is the integer sequence satisfying $\mathbf{d}_{\min}(0) = \mathbf{d}_{\min}(1) = 1$ and, for any $d \geqslant 2$ ,

(4.2.15)

The first numbers are

(4.2.16) \begin{equation} 1, 1, 2, 4, 12, 34, 108, 344\end{equation}

and form Sequence of Sloane (https://oeis.org/). A is a binary tree having no subtrees that are brother and equal, unless they are leaves. It is known that the sets of these trees having exactly $d \geqslant 0$ internal nodes are enumerated by the previous sequence. It is immediate to see that the identity map is a bijection between the set of the closed minimal terms of degree $d \geqslant 0$ and the set of the semi-identity trees with exactly d internal nodes.

Besides, a consequence of Proposition 4.2.2, (4.2.1), and (4.2.3) is that the deg-enumeration $\mathsf{D}_{\mathrm{iso}}$ of $\mathbf{F}_{\mathrm{iso}}$ , enumerating the closed isolated elements of $\mathcal{P}$ w.r.t. their degrees, satisfies

(4.2.17) \begin{equation} \mathsf{D}_{\mathrm{iso}} = 1 + 2\mathsf{z} + \mathsf{z} \mathsf{D}_{\mathrm{iso}}^2 - \mathsf{z} \mathsf{D}_{\mathrm{iso}} - \mathsf{z} \left(\mathsf{D}_{\mathrm{iso}}\left[\mathsf{z} := \mathsf{z}^2\right]\right).\end{equation}

We deduce from this that the number of these terms of degree $d \geqslant 0$ is $\mathbf{d}_{\mathrm{iso}}(d)$ where $\mathbf{d}_{\mathrm{iso}}$ is the integer sequence satisfying $\mathbf{d}_{\mathrm{iso}}(0) = \mathbf{d}_{\mathrm{iso}}(1) = 1$ and, for any $d \geqslant 2$ ,

(4.2.18)

The first numbers are

(4.2.19) \begin{equation} 1, 1, 1, 1, 3, 5, 13, 29, 71, 171, 427, 1067, 2709.\end{equation}

This sequence does not appear in Sloane (https://oeis.org/) for the time being.

4.2.4 ht-enumerations

Due to the fact that $\mathcal{C}$ is hierarchical and, by Proposition 3.1.2, $\mathcal{P}$ is rooted, Proposition 2.2.3 implies that $\mathcal{P}$ satisfies the properties exposed at the very end of Section 2.2.2. In particular, in each $\equiv$ -equivalence class of closed terms, there is exactly one closed maximal term, exactly one closed minimal term, and these terms have the same height. For this reason, the ht-enumerations of $\mathbf{F}_{\max}$ and $\mathbf{F}_{\min}$ are equal and enumerate also the $\equiv$ -equivalence classes of closed terms w.r.t. the heights of their elements. By denoting by $\mathsf{H}_{\mathrm{mm}}$ this generating series, by Propositions 4.2.1 and 4.2.2, $\mathsf{H}_{\mathrm{mm}}$ satisfies

(4.2.20) \begin{equation} \mathsf{H}_{\mathrm{mm}} = 1 + \mathsf{z} + \mathsf{z} \left(\mathsf{H}_{\mathrm{mm}} {\uparrow} \mathsf{H}_{\mathrm{mm}}\right) - \mathsf{z} \mathsf{H}_{\mathrm{mm}}.\end{equation}

We deduce from this and (4.1.4) that the number of these $\equiv$ -equivalence classes of terms of height $h \geqslant 0$ is $\mathbf{h}_{\mathrm{mm}}(h)$ where $\mathbf{h}_{\mathrm{mm}}$ is the integer sequence satisfying $\mathbf{h}_{\mathrm{mm}}(0) =\mathbf{h}_{\mathrm{mm}}(1) = 1$ and, for any $h \geqslant 2$ ,

(4.2.21) \begin{equation} \mathbf{h}_{\mathrm{mm}}(h) = \mathbf{h}_{\mathrm{mm}}(h - 1)^2 - \mathbf{h}_{\mathrm{mm}}(h - 1) + 2 \mathbf{h}_{\mathrm{mm}}(h - 1) \sum_{i \in [h - 1]} \mathbf{h}_{\mathrm{mm}}(i - 1).\end{equation}

The first numbers are

(4.2.22) \begin{equation} 1, 1, 2, 10, 170, 33490, 1133870930, 1285739648704587610\end{equation}

and form Sequence of Sloane (https://oeis.org/).

Besides, a consequence of Proposition 4.2.3, (4.2.2), and (4.2.4) is that the ht-enumeration $\mathsf{H}_{\mathrm{iso}}$ of $\mathbf{F}_{\mathrm{iso}}$ , enumerating the closed isolated elements of $\mathcal{P}$ w.r.t. their heights, satisfies

(4.2.23) \begin{equation} \mathsf{H}_{\mathrm{iso}} = 1 + 2 z + z \left(\mathsf{H}_{\mathrm{iso}} {\uparrow} \mathsf{H}_{\mathrm{iso}}\right) - 2z \mathsf{H}_{\mathrm{iso}}.\end{equation}

We deduce from this and (4.1.4) that the number of these terms of height $h \geqslant 0$ is $\mathbf{h}_{\mathrm{iso}}(h)$ where $\mathbf{h}_{\mathrm{iso}}$ is the integer sequence satisfying $\mathbf{h}_{\mathrm{iso}}(0) = \mathbf{h}_{\mathrm{iso}}(1) = 1$ and, for any $h\geqslant 2$ ,

(4.2.24) \begin{equation} \mathbf{h}_{\mathrm{iso}}(h) = \mathbf{h}_{\mathrm{iso}}(h - 1)^2 - 2 \mathbf{h}_{\mathrm{iso}}(h - 1) + 2 \mathbf{h}_{\mathrm{iso}}(h - 1) \sum_{i \in [h - 1]} \mathbf{h}_{\mathrm{iso}}(i - 1).\end{equation}

The first numbers are

(4.2.25) \begin{equation} 1, 1, 1, 3, 21, 651, 457653, 210065930571\end{equation}

and form Sequence of Sloane (https://oeis.org/), which enumerates binary trees w.r.t. the height (but with a shift). Therefore, there is a one-to-one correspondence between the set of the closed isolated elements of $\mathcal{P}$ of height $h \geqslant 1$ and the set of the binary trees of height $h - 1$ .

4.4.1 Series of duplicative forests and operations

We shall consider in the sequel the k-linearization ${{{\centerdot}}^{\otimes_{k}}}$ , $k \geqslant0$ , of the concatenation product ${\centerdot}$ of duplicative forests. Observe that for any $\mathbf{F}_1, \mathbf{F}_2 \in \mathbb{K}\left\langle\left\langle\mathcal{D}^*\right\rangle\right\rangle$ , we have in particular

(4.4.1) \begin{equation} \mathrm{en}_{\mathrm{ht}}\left(\mathbf{F}_1 {{{\centerdot}}^{\otimes_{}}} \mathbf{F}_2\right) = \mathrm{en}_{\mathrm{ht}} \left(\mathbf{F}_1\right) {\uparrow} \mathrm{en}_{\mathrm{ht}} \left(\mathbf{F}_2\right).\end{equation}

We shall also consider the k-linearization , $k \geqslant 0$ of the grafting product . Observe that for any $\mathbf{F} \in\mathbb{K} \left\langle\left\langle\mathcal{D}^*\right\rangle\right\rangle$ , we have in particular

(4.4.2)

For any $k \geqslant 1$ and , the is the -operation $\mathrm{mg}_u$ on $\mathbb{K}\left\langle\left\langle\mathcal{D}^*\right\rangle\right\rangle$ satisfying, for any ,

(4.4.3a)

(4.4.3b)

(4.4.3c)

(4.4.3d)

where . For instance, with $k = 3$ ,

(4.4.4)

Intuitively, this product consists in grafting a onto one forest or a onto a forest and its right neighbor following the letters of u. Observe that for any and , we have

(4.4.5) \begin{equation} \mathrm{en}_{\mathrm{ht}}\left(\mathrm{mg}_u(\mathbf{F})\right) = \mathsf{z} \, \mathrm{en}_{\mathrm{ht}}(\mathbf{F}).\end{equation}

Let us finally define the as the $\mathcal{D}^*$ -series

(4.4.6)

Observe that

(4.4.7)

4.4.2 Number of elements

Let $\mathbf{gr}$ be the (1, 1)-operation on $\mathbb{K} \left\langle\left\langle\mathcal{D}^*\right\rangle\right\rangle$ satisfying, for any $\mathfrak{f} \in \mathcal{D}^*$ ,

(4.4.8) \begin{equation} \mathbf{gr}(\mathfrak{f}) = \sum_{\mathfrak{f}' \in \mathcal{D}^*(\mathfrak{f})} \mathfrak{f}'.\end{equation}

By definition, $\mathbf{gr}(\mathfrak{f})$ is the characteristic series of $\mathcal{D}^*(\mathfrak{f})$ and is therefore also the formal sum of all duplicative forests $\mathfrak{f}'$ such that $\mathfrak{f} \ll \mathfrak{f}'$ . For instance,

(4.4.9)

Proposition 4.4.1. For any $\ell \geqslant 0$ , $\mathfrak{f}_1, \dots, \mathfrak{f}_\ell \in \mathcal{D}^*$ , and $\mathfrak{f} \in \mathcal{D}^*$ ,

(4.4.10a) \begin{equation} \mathbf{gr} \left( \mathfrak{f}_1 {\centerdot} \dots {\centerdot} \mathfrak{f}_\ell\right) = \mathbf{gr} \left(\mathfrak{f}_1\right) {{{\centerdot}}^{\otimes_{}}} \dots {{{\centerdot}}^{\otimes_{}}} \mathbf{gr}\left(\mathfrak{f}_\ell\right), \end{equation}

(4.4.10b)

(4.4.10c)

Observe that $\mathbf{gr}(\mathbf{ld})$ is the characteristic series of the set $\mathcal{L}$ (defined in Section 3.2.3). Moreover, since for any $h \geqslant 0$ , all elements of $\mathcal{D}^*\left(\mathfrak{l}_h\right)$ have h as height, we have

(4.4.11) \begin{equation} \mathrm{en}_\mathrm{ht}(\mathbf{gr}(\mathbf{ld})) = \sum_{h \geqslant 0} \# \mathcal{D}^*\left(\mathfrak{l}_h\right) \mathsf{z}^h,\end{equation}

so that $\mathrm{en}_\mathrm{ht}(\mathbf{gr}(\mathbf{ld}))$ is the generating series of the cardinalities of the lattices $\mathcal{D}^*\left(\mathfrak{l}_h\right)$ , enumerated w.r.t. $h \geqslant 0$ .

Theorem 4.4.2. The series $\mathbf{gr}(\mathbf{ld})$ satisfies

(4.4.12)

Proof. By (4.4.7) and by Relation (4.4.10c) of Proposition 4.4.1, we have

(4.4.13)

and the relation of the statement follows.

Proposition 4.4.3. The ht-enumeration $\mathsf{H}_{\mathrm{gr}}$ of $\mathbf{gr}(\mathbf{ld})$ satisfies

(4.4.14) \begin{equation} \mathsf{H}_{\mathrm{gr}} = 1 + \mathsf{z} \mathsf{H}_{\mathrm{gr}} + \mathsf{z} \left( \mathsf{H}_{\mathrm{gr}} {\boxtimes} \mathsf{H}_{\mathrm{gr}}\right). \end{equation}

Proof. By (4.4.1) and by Relation (4.4.10a) of Proposition 4.4.1, we have

(4.4.15) \begin{equation} \begin{split} \mathrm{en}_{\mathrm{ht}}(\mathbf{gr}({{{\centerdot}}^{\otimes_{}}} (\Delta(\mathbf{ld})))) & = \sum_{h \geqslant 0} \mathrm{en}_{\mathrm{ht}}\left( \mathbf{gr}\left(\mathfrak{l}_h {\centerdot} \mathfrak{l}_h\right)\right) \\ & = \sum_{h \geqslant 0} \mathrm{en}_{\mathrm{ht}}\left( \mathbf{gr}\left(\mathfrak{l}_h\right) {{{\centerdot}}^{\otimes_{}}} \mathbf{gr}\left(\mathfrak{l}_h\right)\right) \\ & = \sum_{h \geqslant 0} \left( \mathrm{en}_{\mathrm{ht}}\left(\mathbf{gr}\left(\mathfrak{l}_h\right)\right) {\uparrow} \mathrm{en}_{\mathrm{ht}}\left(\mathbf{gr}\left(\mathfrak{l}_h\right)\right)\right). \end{split} \end{equation}

Since for any $h \geqslant 0$ , all the duplicative forests appearing in $\mathbf{gr}\left(\mathfrak{l}_h\right)$ have h as height, the last member of (4.4.15) is equal to $\mathsf{H}_{\mathrm{gr}} {\boxtimes} \mathsf{H}_{\mathrm{gr}}$ . Now, by using this identity together with (4.4.2) and Theorem 4.4.2, we obtain the stated expression for $\mathsf{H}_{\mathrm{gr}}$ .

By Proposition 3.3.3, for any $d \geqslant 1$ , the cardinality of $\mathrm{M}(d)$ is $ \mathbf{h}_{\mathrm{gr}}(h) := \left\langle\mathsf{z}^h, \mathsf{H}_{\mathrm{gr}})\right\rangle$ where $h = d - 1$ . By Proposition 4.4.3, $\mathbf{h}_{\mathrm{gr}}$ is the integer sequence satisfying $\mathbf{h}_{\mathrm{gr}}(0) = 1$ and, for any $h \geqslant 1$ ,

(4.4.16) \begin{equation} \mathbf{h}_{\mathrm{gr}}(h) = \mathbf{h}_{\mathrm{gr}}(h - 1) + \mathbf{h}_{\mathrm{gr}}(h - 1)^2.\end{equation}

The sequence of the cardinalities of $\mathrm{M}(d)$ , $d \geqslant 0$ , starts by

(4.4.17) \begin{equation} 1, 1, 2, 6, 42, 1806, 3263442, 10650056950806\end{equation}

and forms Sequence of Sloane (https://oeis.org/). It is known that the sets of the planar rooted trees $\mathfrak{s}$ made of nodes of arity 0, 1, or 2 and such that any path connecting the root of $\mathfrak{s}$ to any leaf of $\mathfrak{s}$ consists in $d \geqslant 1$ nodes are enumerated by the previous sequence. Let $\phi$ be the map sending any such planar rooted tree $\mathfrak{s}$ to the duplicative tree obtained by replacing each node of $\mathfrak{s}$ having a single child (resp. two children) by a white (resp. black) node and by removing all nodes which have no children. It is easy to see that $\phi$ is a bijection between the set of the planar rooted trees described above and $\mathcal{D}^*\left(\mathfrak{l}_h\right)$ where $h = d- 1$ .

4.4.3 Number of covering pairs

Let $\mathbf{cv}$ be the (1, 1)-operation on $\mathbb{K} \left\langle\left\langle\mathcal{D}^*\right\rangle\right\rangle$ satisfying, for any $\mathfrak{f} \in \mathcal{D}^*$ ,

(4.4.18)

Immediately from the definition of the covering relation of $\ll$ , it follows that for any $\ell \geqslant 0$ , $\mathfrak{f}_1, \dots, \mathfrak{f}_\ell\in \mathcal{D}^*$ , and $\mathfrak{f} \in \mathcal{D}^*$ ,

(4.4.19a) \begin{equation} \mathbf{cv}\left(\mathfrak{f}_1 {\centerdot} \dots {\centerdot} \mathfrak{f}_\ell\right) = \sum_{i \in [\ell]} \mathfrak{f}_1 {\centerdot} \dots {\centerdot} \mathfrak{f}_{i - 1} {{{\centerdot}}^{\otimes_{}}} \mathbf{cv}\left(\mathfrak{f}_i\right) {{{\centerdot}}^{\otimes_{}}} \mathfrak{f}_{i + 1} {\centerdot} \dots {\centerdot} \mathfrak{f}_\ell,\end{equation}

(4.4.19b)

(4.4.19c)

Let $\mathbf{ni}$ be the (1, 1)-operation on $\mathbb{K} \left\langle\left\langle\mathcal{D}^*\right\rangle\right\rangle$ satisfying, for any $\mathfrak{f} \in \mathcal{D}^*$ ,

(4.4.20) \begin{equation} \mathbf{ni}(\mathfrak{f}) = \mathbf{cv}(\mathbf{gr}(\mathfrak{f})).\end{equation}

By a straightforward computation, we obtain

(4.4.21)

so that the coefficient of each $\mathfrak{f}' \in \mathcal{D}^*(\mathfrak{f})$ in $\mathbf{ni}(\mathfrak{f})$ is the number of duplicative forests admitting $\mathfrak{f}'$ as covering in $\mathcal{D}^*(\mathfrak{f})$ . For instance (see at the same time Figure 3),

(4.4.22)

Proposition 4.4.4. For any $\ell \geqslant 0$ , $\mathfrak{f}_1, \dots, \mathfrak{f}_\ell \in \mathcal{D}^*$ , and $\mathfrak{f} \in \mathcal{D}^*$ ,

(4.4.23a) \begin{equation} \mathbf{ni}\left( \mathfrak{f}_1 {\centerdot} \dots {\centerdot} \mathfrak{f}_\ell\right) = \sum_{i \in [\ell]} \mathbf{gr}\left( \mathfrak{f}_1 {\centerdot} \dots {\centerdot} \mathfrak{f}_{i - 1}\right) {{{\centerdot}}^{\otimes_{}}} \mathbf{ni}\left(\mathfrak{f}_i\right) {{{\centerdot}}^{\otimes_{}}} \mathbf{gr}\left( \mathfrak{f}_{i + 1} {\centerdot} \dots {\centerdot} \mathfrak{f}_\ell\right), \end{equation}

(4.4.23b)

(4.4.23c)

Proof. Relations (4.4.23a) and (4.4.23b) are direct consequences of Relations (4.4.19a) and (4.4.19b), and of Proposition 4.4.1. By Proposition 4.4.1 and Relations (4.4.19b) and (4.4.19c), we have

(4.4.24)

This establishes (4.4.23c).

Observe that

(4.4.25) \begin{equation} \mathrm{Supp}(\mathbf{ni}(\mathbf{ld})) = \mathcal{L} \setminus \left\{\mathfrak{l}_h : h \geqslant 0\right\}\end{equation}

and that the coefficient of each duplicative forest $\mathfrak{f}$ of this set is the number of duplicative forests of this same set covered by $\mathfrak{f}$ . Moreover, since for any $h \geqslant0$ , all elements of $\mathcal{D}^*\left(\mathfrak{l}_h\right)$ have h as height,

(4.4.26)

so that $\mathrm{en}_{\mathrm{ht}}(\mathbf{ni}(\mathbf{ld}))$ is the generating series of the number of edges of the Hasse diagrams of the lattices $\mathcal{D}^*\left(\mathfrak{l}_h\right)$ , enumerated w.r.t. $h \geqslant 0$ .

Theorem 4.4.5. The series $\mathbf{ni}(\mathbf{ld})$ satisfies

(4.4.27)

Proof. By (4.4.7) and by Relation (4.4.23c) of Proposition 4.4.4, we have

(4.4.28)

and the relation of the statement follows.

Proposition 4.4.6. The ht-enumeration $\mathsf{H}_{\mathrm{ni}}$ of $\mathbf{ni}(\mathbf{ld})$ satisfies

(4.4.29) \begin{equation} \mathsf{H}_{\mathrm{ni}} = \mathsf{z} \mathsf{H}_{\mathrm{ni}} + \mathsf{z} \mathsf{H}_{\mathrm{gr}} + 2 \mathsf{z} \left(\mathsf{H}_{\mathrm{ni}} {\boxtimes} \mathsf{H}_{\mathrm{gr}}\right). \end{equation}

Proof. Observe first that we have

(4.4.30) \begin{equation} \begin{split} \mathrm{en}_{\mathrm{ht}}\left({{{\centerdot}}^{\otimes_{}}} (\Delta(\mathbf{gr}(\mathbf{ld})))\right) & = \sum_{h \geqslant 0} \sum_{\mathfrak{f} \in \mathcal{D}^*\left(\mathfrak{l}_h\right)} \mathrm{en}_{\mathrm{ht}}(\mathfrak{f} {\centerdot} \mathfrak{f}) \\ & = \sum_{h \geqslant 0} \sum_{\mathfrak{f} \in \mathcal{D}^*\left(\mathfrak{l}_h\right)} \mathrm{en}_{\mathrm{ht}}(\mathfrak{f}) \\ & = \mathsf{H}_{\mathrm{gr}}. \end{split} \end{equation}

Moreover, by (4.4.1) and by Relation (4.4.23a) of Proposition 4.4.4, we have

(4.4.31) \begin{equation} \begin{split} \mathrm{en}_{\mathrm{ht}}\left(\mathbf{ni}\left({{{\centerdot}}^{\otimes_{}}}\left( \Delta\left(\mathbf{ld}\right)\right)\right)\right) & = \sum_{h \geqslant 0} \mathrm{en}_{\mathrm{ht}}\left(\mathbf{ni}\left( \mathfrak{l}_h {\centerdot} \mathfrak{l}_h\right)\right) \\ & = \sum_{h \geqslant 0} \mathrm{en}_{\mathrm{ht}}\left( \mathbf{gr}\left(\mathfrak{l}_h\right) {{{\centerdot}}^{\otimes_{}}} \mathbf{ni}\left(\mathfrak{l}_h\right) + \mathbf{ni}\left(\mathfrak{l}_h\right) {{{\centerdot}}^{\otimes_{}}} \mathbf{gr}\left(\mathfrak{l}_h\right)\right) \\ & = \sum_{h \geqslant 0} \left( \mathrm{en}_{\mathrm{ht}}\left(\mathbf{gr}\left(\mathfrak{l}_h\right)\right) {\uparrow} \mathrm{en}_{\mathrm{ht}}\left(\mathbf{ni}\left(\mathfrak{l}_h\right)\right) + \mathrm{en}_{\mathrm{ht}}\left(\mathbf{ni}\left(\mathfrak{l}_h\right)\right) {\uparrow} \mathrm{en}_{\mathrm{ht}}\left(\mathbf{gr}\left(\mathfrak{l}_h\right)\right)\right). \end{split} \end{equation}

Since for any $h \geqslant 0$ , all duplicative forests appearing in $\mathbf{gr}\left(\mathfrak{l}_h\right)$ and in $\mathbf{ni}\left(\mathfrak{l}_h\right)$ have h as height, the last member of (4.4.31) is equal to $ \mathsf{H}_{\mathrm{gr}} {\boxtimes} \mathsf{H}_{\mathrm{ni}} + \mathsf{H}_{\mathrm{ni}} {\boxtimes} \mathsf{H}_{\mathrm{gr}}. $ Now by using this identity together with (4.4.30), (4.4.2), and Theorem 4.4.5, we obtain the stated expression for $\mathsf{H}_{\mathrm{ni}}$ .

By Proposition 3.3.3, for any $d \geqslant 1$ , the number of edges in the Hasse diagram of $\mathrm{M}(d)$ is $ \mathbf{h}_{\mathrm{ni}}(h) := \left\langle\mathsf{z}^h, \mathsf{H}_{\mathrm{ni}}\right\rangle$ where $h = d - 1$ . By Proposition 4.4.6, $\mathbf{h}_{\mathrm{ni}}$ is the integer sequence satisfying $\mathbf{h}_{\mathrm{ni}}(0) = 0$ and, for any $h \geqslant 1$ ,

(4.4.32) \begin{equation} \mathbf{h}_{\mathrm{ni}}(h) = \mathbf{h}_{\mathrm{ni}}(h - 1) + \mathbf{h}_{\mathrm{gr}}(h - 1) + 2 \mathbf{h}_{\mathrm{ni}}(h - 1) \, \mathbf{h}_{\mathrm{gr}}(h - 1),\end{equation}

where $\mathbf{h}_{\mathrm{gr}}$ is the integer sequence defined in Section 4.4.2. The sequence of the number of edges of the Hasse diagram of $\mathrm{M}(d)$ , $d \geqslant 0$ , starts by

(4.4.33) \begin{equation} 0, 0, 1, 7, 97, 8287, 29942737, 195432804247687.\end{equation}

This sequence does not appear in Sloane (https://oeis.org/) for the time being.

4.4.4 Number of intervals

Let $\mathbf{ns}$ be the (1, 1)-operation on $\mathbb{K} \left\langle\left\langle\mathcal{D}^*\right\rangle\right\rangle$ satisfying, for any $\mathfrak{f} \in \mathcal{D}^*$ ,

(4.4.34) \begin{equation} \mathbf{ns}(\mathfrak{f}) = \mathbf{gr}(\mathbf{gr}(\mathfrak{f})).\end{equation}

By a straightforward computation, we obtain

(4.4.35) \begin{equation} \mathbf{ns}(\mathfrak{f}) = \sum_{\mathfrak{f}' \in \mathcal{D}^*(\mathfrak{f})} \# \left[\mathfrak{f}, \mathfrak{f}'\right] \mathfrak{f}',\end{equation}

so that the coefficient of each $\mathfrak{f}' \in \mathcal{D}^*(\mathfrak{f})$ in $\mathbf{ns}(\mathfrak{f})$ is the number of duplicative forests smaller than or equal as $\mathfrak{f}'$ in $\mathcal{D}^*(\mathfrak{f})$ . For instance (see at the same time Figure 3),

(4.4.36)

Contrary to what we have undertaken in Sections 4.4.2 and 4.4.3 where we have provided direct recursive expressions to compute $\mathbf{gr}(\mathfrak{f})$ and $\mathbf{ni}(\mathfrak{f})$ , we fail to provide similar expressions for $\mathbf{ns}(\mathfrak{f})$ . The trick here consists in considering first a slightly different series depending on a parameter $k \geqslant 1$ which can be seen as a catalytic parameter. With this in mind, let for any $k \geqslant 1$ , $\mathbf{md}_k$ be the (1, k)-operation on $\mathbb{K} \left\langle\left\langle \mathcal{D}^*\right\rangle\right\rangle$ satisfying, for any $\mathfrak{f} \in \mathcal{D}^*$ ,

(4.4.37) \begin{equation} \mathbf{md}_k(\mathfrak{f}) = \sum_{\substack{ \mathfrak{g}_1, \dots, \mathfrak{g}_k \in \mathcal{D}^*(\mathfrak{f}) \\ \mathfrak{g}_1 \wedge \dots \wedge \mathfrak{g}_k = \mathfrak{f} }} \mathfrak{g}_1 \otimes \dots \otimes \mathfrak{g}_k,\end{equation}

where $\wedge$ is the meet operation of the duplicative forest lattices introduced in Section 3.2.3. We call $\mathbf{md}_k(\mathfrak{f})$ the of $\mathfrak{f}$ . Observe that $\mathbf{md}_1$ is the identity map.

Lemma 4.4.7. For any $k \geqslant 1$ and $\mathfrak{f} \in \mathcal{D}^*$ ,

(4.4.38) \begin{equation} \mathbf{md}_k \left(\mathbf{ns}(\mathfrak{f})\right) = \sum_{\substack{ \mathfrak{f}' \in \mathcal{D}^*(\mathfrak{f}) \\ \mathfrak{g}_1, \dots, \mathfrak{g}_k \in \mathcal{D}^*\left(\mathfrak{f}'\right) }} \mathfrak{g}_1 \otimes \dots \otimes \mathfrak{g}_k. \end{equation}

Proof. We have

(4.4.39) \begin{equation} \begin{split} \mathbf{md}_k \left(\mathbf{ns}(\mathfrak{f})\right) & = \sum_{\substack{ \mathfrak{f}' \in \mathcal{D}^*(\mathfrak{f}) \\ \mathfrak{f}'' \in \mathcal{D}^* \left(\mathfrak{f}'\right) }} \sum_{\substack{ \mathfrak{g}_1, \dots, \mathfrak{g}_k \in \mathcal{D}^*\left(\mathfrak{f}\right) \\ \mathfrak{g}_1 \wedge \dots \wedge \mathfrak{g}_k = \mathfrak{f}'' }} \mathfrak{g}_1 \otimes \dots \otimes \mathfrak{g}_k \\ & = \sum_{\mathfrak{f}' \in \mathcal{D}^*(\mathfrak{f})} \sum_{\substack{ \mathfrak{g}_1, \dots, \mathfrak{g}_k \in \mathcal{D}^*\left(\mathfrak{f}\right) \\ \mathfrak{g}_1 \wedge \dots \wedge \mathfrak{g}_k = \mathfrak{f}' }} \# \left[\mathfrak{f}, \mathfrak{f}'\right] \mathfrak{g}_1 \otimes \dots \otimes \mathfrak{g}_k \\ & = \sum_{\mathfrak{g}_1, \dots, \mathfrak{g}_k \in \mathcal{D}^*(\mathfrak{f})} \# \left[\mathfrak{f}, \mathfrak{g}_1 \wedge \dots \wedge \mathfrak{g}_k\right] \mathfrak{g}_1 \otimes \dots \otimes \mathfrak{g}_k \\ & = \sum_{\mathfrak{g}_1, \dots, \mathfrak{g}_k \in \mathcal{D}^*(\mathfrak{f})} \sum_{\substack{ \mathfrak{f}' \in \mathcal{D}^*(\mathfrak{f}) \\ \mathfrak{f}' \ll \mathfrak{g}_1, \dots, \mathfrak{f}' \ll \mathfrak{g}_k }} \mathfrak{g}_1 \otimes \dots \otimes \mathfrak{g}_k, \end{split} \end{equation}

showing the stated identity.

Proposition 4.4.8. For any $k \geqslant 1$ , $\ell \geqslant 0$ , $\mathfrak{f}_1, \dots, \mathfrak{f}_\ell \in \mathcal{D}^*$ , and $\mathfrak{f} \in \mathcal{D}^*$ ,

(4.4.40a) \begin{equation} \mathbf{md}_k\left(\mathbf{ns}\left( \mathfrak{f}_1 {\centerdot} \dots {\centerdot} \mathfrak{f}_\ell\right)\right) = \mathbf{md}_k\left(\mathbf{ns}\left(\mathfrak{f}_1\right)\right) {{{\centerdot}}^{\otimes_{k}}} \dots {{{\centerdot}}^{\otimes_{k}}} \mathbf{md}_k\left(\mathbf{ns}\left(\mathfrak{f}_\ell\right)\right), \end{equation}

(4.4.40b)

(4.4.40c)

Proof. Relations (4.4.40a) and (4.4.40b) are direct consequences of Lemmas 3.2.1 and 4.4.7. By Lemmas 3.2.1 and 4.4.7,

(4.4.41)

where for any duplicative forest $\mathfrak{f}$ , $\mathrm{rts}(\mathfrak{f})$ is the word on containing from left to right the roots of the trees forming $\mathfrak{f}$ . This shows (4.4.40c).

Observe that $\mathrm{Supp}\left(\mathbf{ns}(\mathbf{ld})\right) = \mathcal{L}$ and that the coefficient of each duplicative forest $\mathfrak{f}$ of this set is the number of duplicative forests of this same set smaller than or equal as $\mathfrak{f}$ . Moreover, since for any $h\geqslant 0$ , all elements of $\mathcal{D}^*\left(\mathfrak{l}_h\right)$ have h as height,

(4.4.42) \begin{equation} \mathrm{en}_{\mathrm{ht}}(\mathbf{ns}(\mathbf{ld})) = \sum_{h \geqslant 0} \sum_{\mathfrak{f} \in \mathcal{D}^*\left(\mathfrak{l}_h\right)} \# \left[\mathfrak{l}_h, \mathfrak{f}\right] \, \mathsf{z}^h,\end{equation}

so that $\mathrm{en}_{\mathrm{ht}}(\mathbf{ns}(\mathbf{ld}))$ is the generating series of the number of intervals of the lattices $\mathcal{D}^*\left(\mathfrak{l}_h\right)$ , enumerated w.r.t. $h \geqslant 0$ .

Theorem 4.4.9. The series $\mathbf{ns}(\mathbf{ld})$ satisfies $\mathbf{ns}(\mathbf{ld}) = \mathbf{md}_1(\mathbf{ns}(\mathbf{ld}))$ where, for any $k \geqslant 1$ , the series $\mathbf{md}_k(\mathbf{ns}(\mathbf{ld}))$ satisfies

(4.4.43)

Proof. First, the relation $\mathbf{ns}(\mathbf{ld}) = \mathbf{md}_1(\mathbf{ns}(\mathbf{ld}))$ holds since $\mathbf{md}_1$ is the identity map. By (4.4.7) and by Proposition 4.4.8, we have

(4.4.44)

and the relation of the statement follows.

Proposition 4.4.10. The ht-enumeration $\mathsf{H}_{\mathrm{ns}}$ of $\mathbf{ns}(\mathbf{ld})$ satisfies $\mathsf{H}_{\mathrm{ns}} = \mathsf{H}_{\mathrm{ns}}^{(1)}$ where, for any $k \geqslant 1$ , $\mathsf{H}_{\mathrm{ns}}^{(k)}$ is the ht-enumeration of $\mathbf{md}_k(\mathbf{ns}(\mathbf{ld}))$ which satisfies

(4.4.45)

Proof. By Relation (4.4.40a) of Proposition 4.4.8, we have

(4.4.46) \begin{equation} \begin{split} \mathrm{en}_{\mathrm{ht}} \left(\mathbf{md}_k\left(\mathbf{ns}\left({{{\centerdot}}^{\otimes_{}}} \left(\Delta\left(\mathbf{ld}\right)\right)\right)\right)\right) & = \sum_{h \geqslant 0} \mathrm{en}_{\mathrm{ht}}\left( \mathbf{md}_k\left(\mathbf{ns}\left( \mathfrak{l}_h {\centerdot} \mathfrak{l}_h\right)\right)\right) \\ & = \sum_{h \geqslant 0} \mathrm{en}_{\mathrm{ht}}\left( \mathbf{md}_k\left(\mathbf{ns}\left(\mathfrak{l}_h\right)\right) {{{\centerdot}}^{\otimes_{k}}} \mathbf{md}_k\left(\mathbf{ns}\left(\mathfrak{l}_h\right)\right) \right) \\ & = \sum_{h \geqslant 0} \left(\mathrm{en}_{\mathrm{ht}}\left( \mathbf{md}_k\left(\mathbf{ns}\left(\mathfrak{l}_h\right)\right)\right) {\uparrow} \mathrm{en}_{\mathrm{ht}}\left( \mathbf{md}_k\left(\mathbf{ns}\left(\mathfrak{l}_h\right)\right)\right)\right). \end{split} \end{equation}

Since for any $h \geqslant 0$ , all the duplicative forests of the tensors $\mathfrak{f}_1 \otimes \dots \otimes \mathfrak{f}_k$ appearing in $\mathbf{md}_k\left(\mathbf{ns}\left(\mathfrak{l}_h\right)\right)$ have h as height, the last member of (4.4.46) is equal to $\mathsf{H}_{\mathrm{ns}}^{(k)} {\boxtimes} \mathsf{H}_{\mathrm{ns}}^{(k)}$ . Moreover, by (4.4.5), for any ,

(4.4.47)

Now, by using these two identities together with Theorem 4.4.9, and by the fact that the number of words of length k on having exactly occurrences of is $\binom{k}{i}$ , we obtain the stated expression for $\mathsf{H}_{\mathrm{ns}}^{(k)}$ . Finally, we have $\mathsf{H}_{\mathrm{ns}} = \mathsf{H}_{\mathrm{ns}}^{(1)}$ since $\mathbf{ns}(\mathbf{ld}) = \mathbf{md}_1(\mathbf{ns}(\mathbf{ld}))$ .

By Proposition 3.3.3, for any $d \geqslant 1$ , the number of intervals in $\mathrm{M}(d)$ is $ \mathbf{h}_{\mathrm{ns}}^{(1)}(h) := \left\langle\mathsf{z}^h, \mathsf{H}_{\mathrm{ns}}\right\rangle$ where $h = d - 1$ . By Proposition 4.4.10, for any $k \geqslant 1$ , $\mathbf{h}_{\mathrm{ns}}^{(k)}$ is the integer sequence satisfying $\mathbf{h}_{\mathrm{ns}}^{(k)}(0) =1$ and, for any $h \geqslant 1$ ,