where $y$ is the representative of the previous P-component within that S-component.

The last two cases are depicted in Figure 9. This case distinction can be encoded in MSO.

The root of $T$ is $(x, 1)$, where $x \in X$ is the unique element such that $G[x]$ is maximal in the subgraph relation among all $y \in X$. The proof of the fact that $\text{val}_{SP}(T) = G$ is routine, by induction on the decomposition of $G$ given by Lemma 8.

To prove that the class $DSP$ is parsable, we define the copyless transduction $\delta_{rev}$ having parameter $X$, assigned to a set of edges of the input graph that will be reversed in the output graph $G'$, i.e., for each edge $x \in X$ we have $\lambda_{G'}(x) \stackrel{\text{def}}{=} \lambda_G(x)^r$, where $b^r$ is a unique edge label corresponding to $b \in \mathbb{B}$ and $v_{G'}(x, i) \stackrel{\text{def}}{=} v_G(x, 3-i)$, for $i = 1, 2$. Then, $\pi_{DSP}$ is the composition of $\delta_{rev}$ with the modified version of $\pi_{SP}$, where the edges with labels $b^r$ are encoded by unary $\bar{b}_{2,1}$ edges in the output parse tree. $\square$

**Theorem 12:** The class $G_2$ is parsable.

[Proof of Theorem 12] To prove that $G_2$ is parsable, we build a definable transduction $\pi_2$ that produces, from any connected graph $G$ of tree-width $\le 2$ a parse tree $T \in P_{G_2}$ such that $\text{val}_{G_2}(T) = G$. We define $\pi_2 \stackrel{\text{def}}{=} \delta_2 \circ \delta_1$, where the definable transductions $\delta_1$ and $\delta_2$ are described below. We refer to the definitions introduced in the proof of Theorem 11.

First, $\delta_1$ checks whether the input graph $G$ has tree-width at most 2, by checking the absence of a $K_4$ minor, and assigns its parameter $X$ to a set of edges from $G$. The output $G'$ of $\delta_1$ is the same as $G$, except for the edges from $X_1$ that are reversed. The reversed edges have the labels $b^r$, where the original labels are $b \in \mathbb{B}$.

Second, $\delta_2$ produces a parse tree $T$ of its input graph $G$ in a similar way as the $\pi_{SP}$ transduction from the proof of Theorem 11. Note that each block of $G$ is a P-component of $G$ and, moreover, the condition that $G[x]$ does not contain a cutvertex can be encoded in MSO. The block tree of $G$ can be represented by the MSO-definable "descendent-of" relation between the representatives of its blocks, which in fact, describes a forest. We assume w.l.o.g. that the root of the block tree of $G$ is a cutvertex of $G$, or the 1-source of $G$, in case $G$ consists of a single block, i.e., $G$ is 2-connected.

The transduction $\delta_2$ uses $k = 7$ layers and assigns its parameter $X$ to a set of vertices and edges from its input $G$ (i.e., the output of $\delta_1$) that are the unique representatives of the P-components of $G$. In addition $X$ contains the 1-source of $G$, which can be identified by an MSO formula.

The output parse tree $T$ is defined as follows. The nodes of $T$ are $V_T \stackrel{\text{def}}{=} \{(x, 1), (x, 2), (x, 3) \mid x \in X\}$. We use the layer $j \in \{1, 2, 3\}$ to represent the nodes attached to the $\bar{\sigma}$-labeled edges on the $(j+1)^{\text{th}}$ position of an edge. The layer $j \in \{4, 5, 6, 7\}$ distinguishes the four types of edges, as follows:

- unary $\bar{\sigma}_{\{1\}}$-labeled edges of the form $(x, 4)$, for some $x \in X$, attached to a single vertex $v_T((x, 4), 1) = (x, j)$, which is attached to the $j^{\text{th}}$ position of another edge, for $j \in \{2, 3\}$.

- unary $\bar{b}_{i,3-i}$-labeled edges $(x, 5)$ correspond to the edges $x \in X \cap \bar{E}_G$, where $i = 1$ if $\lambda_G(x) = b$ and $i = 2$ if

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

<figure><img src="image_11.png" /><figcaption>Fig. 10. A graph from $G_2$ (a) and its corresponding parse tree (b). The braces indicate the representatives of P-components $G[v_2]$ and $G[e_1]$. All other P-components are single edges $G_{e_i}$ having $e_i$ as representative, for $i = 1, \dots, 7$. The nodes of the parse tree are shown in red and the edges in black.</figcaption></figure>

$\lambda_G(x) = b^r$, i.e., the orientation of the edge depends on its label, $b^r$-labeled edges being exactly the ones reversed by $\delta_1$. These edges are attached to a single vertex $v_T((x, 6), 1) \stackrel{\text{def}}{=} (x, j)$, where the vertex $(x, j)$ is attached to some other edge on the $j^{\text{th}}$ position, for $j \in \{2, 3, 4\}$.

- ternary $\bar{\triangleright}$-labeled edges $(x, 6)$, where $x \in X$ is the representative of a block of $G$. Each $\bar{\triangleright}$-labeled edge is attached to the following vertices:

$$v_T((x, 6), 1) \stackrel{\text{def}}{=} \left\{ \begin{array}{l} (y, 3), \text{ where } y \text{ is the representative of the P-component to which } x \text{ is attached in some S-component} \\ (y, 1), \text{ where } y \text{ is the 1-source of } G \end{array} \right.$$

Note that the relation that finds the representative of the P-component to which the block $x$ is attached in an S-component (as the 3rd argument of a serial composition) can be encoded in MSO, similar to the left-neighbour relation in an S-component (see proof of Theorem 11).

- $\bar{\sigma}$-labeled edges of parity 4 are defined similar to the ternary $\bar{\sigma}$-labeled edges from the proof of Theorem 11. In particular, each S-component of a P-component $G[x]$ of $G$ is of the form $\circ^{G_2}(G[x_1], \circ^{G_2}(G[x_2], \dots, \circ^{G_2}(G[x_{n-1}], G[x_n], H_{n-1}) \dots, H_2), H_1)$, where $G[x_1], \dots, G[x_n]$ are P-components of $G[x]$ and $H_1, \dots, H_{n-1}$ are (possibly empty) parallel compositions of blocks of sort $\{1\}$. Then, for each $i \in [1, n]$, $T$ has a $\bar{\sigma}$-labeled edge $(x_i, 7)$ attached to the following vertices:

$$v_T((x_i, 7), 1) \stackrel{\text{def}}{=} \begin{cases} (x, 1), & \text{if } i = 1 \\ (x_{i-1}, 2), & \text{if } i \ge 2 \end{cases} \\ v_T((x_i, 7), j) \stackrel{\text{def}}{=} (x_i, j-1), \text{ for } j \in \{2, 3, 4\}$$

Note that the subtree corresponding to each non-empty parallel composition of blocks $H_i$ is a parallel composition of $\bar{\triangleright}$-labeled edges whose 1st vertex is $(x_i, 1)$, by the
definition of $\overline{\triangleright}$-labeled edges. The relation between $x_i$ and the representative of each block from $H_i$ can be defined using MSO.

We refer to Figure 10 for an illustration of this definition. We note that the case distinctions above are definable using MSO. The root of $T$ is $(r, 1)$, where $r \in Y$ exists and is unique. The proof that $\mathrm{val}_{G_2}(T) = G$ goes by induction on the decomposition of $G$ given by Lemmas 8 and 10. $\square$

## APPENDIX B
### ADDITIONAL MATERIAL ON RECOGNIZABILITY

**Lemma 21:** Let $\mathcal{A}$ be an algebra and $\mathcal{B}$ be an algebra derived from $\mathcal{A}$. Then, $\mathcal{L} \subseteq \mathcal{B}$ is recognizable in $\mathcal{B}$, if it is recognizable in $\mathcal{A}$.

*Proof.* Let $\mathcal{F}_\mathcal{A}$ and $\mathcal{F}_\mathcal{B}$ be the signatures of $\mathcal{A}$ and $\mathcal{B}$, respectively. By assumption we have that for every $f \in \mathcal{F}_\mathcal{B}$ there is some first-order $\mathcal{F}_\mathcal{A}$-term $t_f$ such that $f^\mathcal{B} = t_f^\mathcal{A}$. Let $(\mathcal{D}, E)$ be a $\mathcal{F}_\mathcal{A}$-recognizer, such that $\mathcal{L} = h_{A,\mathcal{D}}^{-1}(E)$. We define the $\mathcal{F}_\mathcal{B}$-recognizer $(\mathcal{I}, J)$, where $\mathcal{I} \stackrel{\mathrm{def}}{=} (\{\mathbf{1}^\sigma\}_{\sigma \in \Sigma_\mathcal{B}}, \{f^\mathcal{I}\}_{f \in \mathcal{F}_\mathcal{B}})$ and

$$ \mathbf{1}^{\sigma} \stackrel{\mathrm{def}}{=} \{t^{\mathcal{D}} \mid \text{t ground } \mathcal{F}_{\mathcal{B}}\text{-term, } \sigma(t) = \sigma\} $$

$$ f^{\mathcal{I}} \stackrel{\mathrm{def}}{=} t_f^{\mathcal{D}} $$

for all $\sigma \in \Sigma_\mathcal{B}$, where

$$ \Sigma_\mathcal{B} = \{\sigma_1, \dots, \sigma_n, \sigma(f) \mid f \in \mathcal{F}_\mathcal{B}, \alpha(f) = \langle\sigma_1, \dots, \sigma_n\rangle\} $$

and $J \stackrel{\mathrm{def}}{=} \mathbf{1} \cap E$. We prove that $\mathcal{L} = h_{B,\mathcal{I}}^{-1}(J)$. We consider some $x \in \mathcal{B}$. By assumption that we consider only representable algebras, there exists a ground $\mathcal{F}_\mathcal{B}$-term $t$ such that $x = t^\mathcal{B}$. Let $u$ be the $\mathcal{F}_\mathcal{A}$-term obtained by expanding the terms from $\mathcal{F}_\mathcal{B}$, i.e., $x = u^\mathcal{A}$. Then, $h_{B,\mathcal{I}}(x) = h_{B,\mathcal{I}}(t^\mathcal{B}) = t^\mathcal{I} = u^\mathcal{D} = h_{A,\mathcal{D}}(u^\mathcal{A}) = h_{A,\mathcal{D}}(x)$. Hence, $x \in h_{B,\mathcal{I}}^{-1}(J)$ iff $x \in h_{A,\mathcal{D}}^{-1}(E)$. With $\mathcal{L} \subseteq \mathcal{B}$, we obtain that $\mathcal{L} = h_{A,\mathcal{D}}^{-1}(E) = h_{B,\mathcal{I}}^{-1}(J)$. $\square$

An equivalent definition of recognizability in a $(\mathcal{F}_\mathcal{A}, \Sigma_\mathcal{A})$-algebra $\mathcal{A}$ uses congruences. For a given set $\mathcal{L} \subseteq \mathcal{A}$, we denote by $\simeq_\mathcal{L} \subseteq \mathcal{A} \times \mathcal{A}$ the equivalence relation $a_1 \simeq_\mathcal{L} a_2$ if and only if $\sigma(a_1) = \sigma(a_2)$ and $t^\mathcal{A}[a_1] \in \mathcal{L} \Leftrightarrow t^\mathcal{A}[a_2] \in \mathcal{L}$, for each $\mathcal{F}_\mathcal{A}$-context $t[x]$. We say that $\simeq_\mathcal{L}$ is (locally) finite if it has finitely many equivalence classes (of each sort). It is routine to show that $\simeq_\mathcal{L}$ is a congruence for each set $\mathcal{L}$, i.e., for each function symbol $f \in \mathcal{F}$ and all elements $a_1, b_1, \dots, a_{\#f}, b_{\#f} \in \mathcal{A}$, if $a_i \simeq_\mathcal{L} b_i$, for all $i \in [1, \#f]$ then $f^\mathcal{A}(a_1, \dots, a_{\#f}) \simeq_\mathcal{L} f^\mathcal{A}(b_1, \dots, b_{\#f})$. Thus, $\simeq_\mathcal{L}$ is called the syntactic congruence of $\mathcal{L}$. For each element $a \in \mathcal{A}$, we denote by $[a]_{\simeq_\mathcal{L}}$ the equivalence class of $a$ and by $\mathcal{A}_{\simeq_\mathcal{L}}$ the $(\mathcal{F}_\mathcal{A}, \Sigma_\mathcal{A})$-algebra whose elements are the equivalence classes, of sorts $\sigma([a]_{\simeq_\mathcal{L}}) = \sigma(a)$. The function symbols $f \in \mathcal{F}_\mathcal{A}$ are interpreted in $\mathcal{A}_{\simeq_\mathcal{L}}$ as follows<fnref n="13" />:

$$ f^{\mathcal{A}_{\simeq_\mathcal{L}}}([a_1]_{\simeq_\mathcal{L}}, \dots, [a_{\#f}]_{\simeq_\mathcal{L}}) \stackrel{\mathrm{def}}{=} [f^\mathcal{A}(a_1, \dots, a_{\#f})]_{\simeq_\mathcal{L}} $$

Let $h_{\simeq_\mathcal{L}} : \mathcal{A} \to \mathcal{A}_{\simeq_\mathcal{L}}$ the function that maps each element $a \in \mathcal{A}$ to its equivalence class $h_{\simeq_\mathcal{L}} \stackrel{\mathrm{def}}{=} [a]_{\simeq_\mathcal{L}}$. Then, $h_{\simeq_\mathcal{L}}$ is a homomorphism, by the definition of $\mathcal{A}_{\simeq_\mathcal{L}}$. If $\simeq_\mathcal{L}$ is locally finite, it is routine to show that $(\mathcal{A}_{\simeq_\mathcal{L}}, \{[a]_{\simeq_\mathcal{L}} \mid a \in \mathcal{L}\})$ is

a recognizer for $\mathcal{L}$, called the syntactic recognizer of $\mathcal{L}$. For self-containment reasons, we prove a well-known fact, namely that the syntactic recognizer is the minimal recognizer of that set, which can be stated as follows:

**Lemma 22:** Let $\mathcal{L} \subseteq \mathcal{A}$ be a recognizable set in a representable $(\mathcal{F}, \Sigma)$-algebra $\mathcal{A}$ and $(\mathcal{I}, J)$ be a recognizer for $\mathcal{L}$, for a representable $(\mathcal{F}, \Sigma)$-algebra $\mathcal{I}$, witnessed by the homomorphism $h_{A,\mathcal{I}}$. Then, $h_{\simeq_\mathcal{L}}$ factors through $h_{A,\mathcal{I}}$ via some homomorphism $g$ between $\mathcal{I}$ and $\mathcal{A}_{\simeq_\mathcal{L}}$, i.e., $h_{\simeq_\mathcal{L}} = g \circ h_{A,\mathcal{I}}$. *Proof.* Because the algebras $\mathcal{A}$ and $\mathcal{I}$ are representable, the homomorphism $h_{A,\mathcal{I}} : \mathcal{A} \to \mathcal{I}$ is surjective: for each element $i \in \mathcal{I}$ there exists a $\mathcal{F}_\mathcal{A}$-term $t$ such that $t^\mathcal{I} = i$, hence $h_{A,\mathcal{I}}(t^\mathcal{A}) = t^\mathcal{I} = i$ and $t^\mathcal{A} \in \mathcal{A}$. Let $\kappa \subseteq h_{A,\mathcal{I}}^{-1}$ be a function (such a function exists because $h_{A,\mathcal{I}}$ is surjective) and define $g \stackrel{\mathrm{def}}{=} h_{\simeq_\mathcal{L}} \circ \kappa$. First, we prove the following fact:

*Fact 3:* $h_{A,\mathcal{I}}(a_1) = h_{A,\mathcal{I}}(a_2)$ only if $a_1 \simeq_\mathcal{L} a_2$, for all $a_1, a_2 \in \mathcal{A}$.

*Proof.* Assume that $h_{A,\mathcal{I}}(a_1) = h_{A,\mathcal{I}}(a_2)$. Because $\mathcal{L} = h_{A,\mathcal{I}}^{-1}(J)$, then either $a_1, a_2 \in \mathcal{L}$ or $a_1, a_2 \notin \mathcal{L}$, thus $a_1 \simeq_\mathcal{L} a_2$. $\square$

We prove first that $h_{\simeq_\mathcal{L}} = g \circ h_{A,\mathcal{I}}$. Let $a \in \mathcal{A}$ be an element. Then, $g(h_{A,\mathcal{I}}(a)) = h_{\simeq_\mathcal{L}}(\kappa(h_{A,\mathcal{I}}(a)))$, by the definition of $g$. Since $\kappa \subseteq h_{A,\mathcal{I}}^{-1}$, we obtain $h_{A,\mathcal{I}}(\kappa(h_{A,\mathcal{I}}(a))) = h_{A,\mathcal{I}}(a)$, hence $\kappa(h_{A,\mathcal{I}}(a)) \simeq_\mathcal{L} a$, by Fact 3. Thus, we obtain $g(h_{A,\mathcal{I}}(a)) = h_{\simeq_\mathcal{L}}(\kappa(h_{A,\mathcal{I}}(a))) = h_{\simeq_\mathcal{L}}(a)$. Since the choice of $a \in \mathcal{A}$ was arbitrary, this proves $h_{\simeq_\mathcal{L}} = g \circ h_{A,\mathcal{I}}$.

Second, we prove that $g$ is a homomorphism between $\mathcal{I}$ and $\mathcal{A}_{\simeq_\mathcal{L}}$. To this end, let $i \stackrel{\mathrm{def}}{=} f^\mathcal{I}(i_1, \dots, i_{\#f}) \in \mathcal{I}$ be an element, for some $i_1, \dots, i_{\#f}$. Because $\mathcal{I}$ is a representable algebra, there exists an $\mathcal{F}$-term $t = f(t_1, \dots, t_{\#f})$ such that $i = t^\mathcal{I}$ and $t^\mathcal{I}_j = i_j$, for all $j \in [1, \#f]$. Let $\sim_{h_{A,\mathcal{I}}}$ be the kernel of $h_{A,\mathcal{I}}$, i.e., the equivalence relation $a_1 \sim_{h_{A,\mathcal{I}}} a_2 \Leftrightarrow h_{A,\mathcal{I}}(a_1) = h_{A,\mathcal{I}}(a_2)$, for all $a_1, a_2 \in \mathcal{A}$.

*Fact 4:* There exist elements $a, a_1, \dots, a_{\#f} \in \mathcal{A}$ such that $a = f^\mathcal{A}(a_1, \dots, a_{\#f})$, $a \sim_{h_{A,\mathcal{I}}} \kappa(i)$ and $a_j \sim_{h_{A,\mathcal{I}}} \kappa(i_j)$, for all $j \in [1, \#f]$.

*Proof.* By induction on the structure of $t = f(t_1, \dots, t_{\#f})$. By the inductive hypothesis, there exist $a_j \sim_{h_{A,\mathcal{I}}} \kappa(i_j)$, for all $j \in [1, \#f]$, and let $a \stackrel{\mathrm{def}}{=} f^\mathcal{A}(a_1, \dots, a_{\#f})$. We prove $a \sim_{h_{A,\mathcal{I}}} \kappa(i)$:

$$ \begin{aligned} h_{A,\mathcal{I}}(a) &= h_{A,\mathcal{I}}(f^\mathcal{A}(a_1, \dots, a_{\#f})) \\ &= f^\mathcal{I}(h_{A,\mathcal{I}}(a_1), \dots, h_{A,\mathcal{I}}(a_{\#f})) \\ &\qquad \text{because } h_{A,\mathcal{I}} \text{ is a homomorphism} \\ &= f^\mathcal{I}(h_{A,\mathcal{I}}(\kappa(i_1)), \dots, h_{A,\mathcal{I}}(\kappa(i_{\#f}))) \\ &\qquad \text{because } a_j \sim_{h_{A,\mathcal{I}}} \kappa(i_j), \text{ for all } j \in [1, \#f] \\ &= f^\mathcal{I}(i_1, \dots, i_{\#f}), \text{ because } \kappa \subseteq h_{A,\mathcal{I}}^{-1} \\ &= i = h_{A,\mathcal{I}}(\kappa(i)) \end{aligned} $$

<footnote n="13">¹³The function $f^\mathcal{A}_{\simeq_\mathcal{L}}$ is well defined because $\simeq_\mathcal{L}$ is a congruence relation. $\square$</footnote>
Back to the proof, we compute:

$$
\begin{align*}
g(f^I(i_1, \dots, i_{\#f})) &= h_{\simeq_L}(\kappa(i)) = h_{\simeq_L}(a), \text{ by Fact 4} \\
&= f^{A \simeq_L} (h_{\simeq_L}(a_1), \dots, h_{\simeq_L}(a_{\#f})) \\
&\text{because } a_j \sim_{h_{A,I}} \kappa(i_j) \\
&\text{by Fact 3 and } \sim_{h_{A,I}} \subseteq_{\simeq_L}, \text{ by Fact 4} \\
&= f^{A \simeq_L} (h_{\simeq_L}(\kappa(i_1)), \dots, h_{\simeq_L}(\kappa(i_{\#f}))) \\
&= f^{A \simeq_L} (g(i_1), \dots, g(i_{\#f}))
\end{align*}
$$

Since the choice of $f \in \mathcal{F}$ and $i_1, \dots, i_{\#f} \in \mathcal{I}$ was arbitrary,
we obtain that $g$ is a homomorphism between $\mathcal{I}$ and $\mathcal{A}_{\simeq_L}$. $\square$

We further prove the following factorization property of the
$h_{\simeq_L}$ homomorphism:

Lemma 23: Let $\mathcal{A}$ and $\mathcal{B}$ be two representable $(\mathcal{F}, \Sigma)$-algebras such that the homomorphism $h_{\mathcal{A},\mathcal{B}}$ exists. Let $\mathcal{L}_B \subseteq \mathcal{B}$ be a set and $\mathcal{L}_A \stackrel{\text{def}}{=} h_{\mathcal{A},\mathcal{B}}^{-1}(\mathcal{L}_B)$. Then, the algebras $\mathcal{A} \simeq_{\mathcal{L}_A}$ and $\mathcal{B} \simeq_{\mathcal{L}_B}$ are related by an isomorphism $g$ and $h_{\mathcal{L}_A} \simeq h_{\mathcal{L}_B}$ factors through $h_{\mathcal{A},\mathcal{B}}$ via $h_{\mathcal{L}_A} \simeq h_{\mathcal{L}_B}$ up to the isomorphism of the domains, i.e., $g \circ h_{\mathcal{L}_A} \simeq h_{\mathcal{L}_B} \circ h_{\mathcal{A},\mathcal{B}}$.

*Proof.* We show first that:

$$
a_1 \simeq_{\mathcal{L}_A} a_2 \iff h_{A,B}(a_1) \simeq_{\mathcal{L}_B} h_{A,B}(a_2) (\dagger)
$$

“⇒” Let $a_1, a_2 \in \mathcal{A}$ such that $a_1 \simeq_{\mathcal{L}_A} a_2$. Then, $\sigma(h_{A,B}(a_1)) = \sigma(a_1) = \sigma(a_2) = \sigma(h_{A,B}(a_2))$. Let $t[x]$ be an $\mathcal{F}$-context. We establish the equivalence:

$$
\begin{align*}
t^{\mathcal{B}}[h_{A,B}(a_1)] &= h_{A,B}(t^A[a_1]) \in \mathcal{L}_B \\
&\iff \text{because } \mathcal{L}_A = h_{A,B}^{-1}(\mathcal{L}_B) \\
t^A[a_1] \in \mathcal{L}_A \\
&\iff \text{because } a_1 \simeq_{\mathcal{L}_A} a_2 \\
t^A[a_2] \in \mathcal{L}_A \\
&\iff \text{because } \mathcal{L}_A = h_{A,B}^{-1}(\mathcal{L}_B) \\
t^{\mathcal{B}}[h_{A,B}(a_2)] &= h_{A,B}(t^A[a_2]) \in \mathcal{L}_B
\end{align*}
$$

“<” Let $a_1, a_2 \in \mathcal{A}$ such that $h_{A,B}(a_1) \simeq_{\mathcal{L}_B} h_{A,B}(a_2)$. Then, $\sigma(a_1) = \sigma(h_{A,B}(a_1)) = \sigma(h_{A,B}(a_2)) = \sigma(a_2)$. Let $t[x]$ be an $\mathcal{F}$-context. We establish the equivalence:

$$
\begin{align*}
t^A[a_1] &\in \mathcal{L}_A \\
&\iff \text{because } \mathcal{L}_A = h_{A,B}^{-1}(\mathcal{L}_B) \\
h_{A,B}(t^A[a_1]) &\in \mathcal{L}_B \\
&\iff \text{because } h_{A,B}(a_1) \simeq_{\mathcal{L}_B} h_{A,B}(a_2) \\
h_{A,B}(t^A[a_2]) &\in \mathcal{L}_B \\
&\iff \text{because } \mathcal{L}_A = h_{A,B}^{-1}(\mathcal{L}_B) \\
t^A[a_2] &\in \mathcal{L}_A
\end{align*}
$$

We define the function $g : A \simeq_{\mathcal{L}_A} \rightarrow B \simeq_{\mathcal{L}_B}$ as $g([a]_{\simeq_{\mathcal{L}_A}}) \stackrel{\text{def}}{=} [h_{A,B}(a)]_{\simeq_{\mathcal{L}_B}}$, for each $a \in \mathcal{A}$. By (†), $g$ is bijective. To

prove that $g$ is an isomorphism between $\mathcal{A} \simeq_{\mathcal{L}_A}$ and $\mathcal{B} \simeq_{\mathcal{L}_A}$,
we observe that, for each function symbol $f \in \mathcal{F}$:

$$
\begin{align*}
g(f^{A \simeq_{\mathcal{L}_A}} ([a_1]_{\simeq_{\mathcal{L}_A}}, \dots, [a_{\#f}]_{\simeq_{\mathcal{L}_A}})) \\
&= g([f^A(a_1, \dots, a_{\#f})]_{\simeq_{\mathcal{L}_A}}) \\
&= [h_{A,B}(f^A(a_1, \dots, a_{\#f}))]_{\simeq_{\mathcal{L}_B}} \\
&= f^{B \simeq_{\mathcal{L}_B}} ([h_{A,B}(a_1)]_{\simeq_{\mathcal{L}_B}}, \dots, [h_{A,B}(a_{\#f})]_{\simeq_{\mathcal{L}_B}}) \\
&= f^{B \simeq_{\mathcal{L}_B}} (g([a_1]_{\simeq_{\mathcal{L}_A}}), \dots, g([a_{\#f}]_{\simeq_{\mathcal{L}_A}}))
\end{align*}
$$

The equality $g \circ h_{\simeq_{\mathcal{L}_A}} = h_{\simeq_{\mathcal{L}_B}} \circ h_{A,B}$ follows from the definition of $g$. $\square$

APPENDIX C
SERIES PARALLEL GRAPHS

We define regular series-parallel grammars in terms of disjoint sets of nonterminals $\mathcal{P}$ and $\mathcal{S}$, with the intuition that P-graphs (resp. S-graphs) are parsed starting with a nonterminal from $\mathcal{P}$ (resp. $\mathcal{S}$). In the rest of this section, we write $P, S, \mathcal{P}$ and $\mathcal{S}$ instead of $X, Y, \mathcal{X}$ and $\mathcal{Y}$, respectively. Since $\{1, 2\}$ is the only sort from $\mathcal{F}_{\mathcal{S}P}$ (resp. $\mathcal{F}_{\mathcal{D}SP}$), we write $P$ and $\mathcal{S}$ instead of $X_{\{1,2\}}$ and $Y_{\{1,2\}}$, respectively, in the footprint of a regular grammar:

Definition 20: A regular series-parallel grammar is a strat-
ified $\mathcal{F}_{SP}$-grammar $\Gamma = (\mathcal{P} \uplus \mathcal{S}, \mathcal{R})$ such that $\mathrm{FP}(\Gamma) \subseteq \mathrm{FP}_{SP}$, where:

$$
\mathrm{FP}_{\mathrm{SP}} \stackrel{\mathrm{def}}{=} \{ \mathbf{P} \to \mathbf{S}^{\ge 2}, \mathbf{S} \to \mathbf{P} \circ \mathbf{S}, \mathbf{S} \to \mathbf{P} \circ \mathbf{P}, \to \mathbf{P}, \to \mathbf{S} \} \cup \\
\{ \mathbf{P} \to b_{1,2}, \mathbf{S} \to b_{1,2} \mid b \in \mathbb{B} \}
$$

The definition of regular grammars for the DSP class has,
in addition, the footprint constraints $P \to b_{2,1}$ and $S \to b_{2,1}$,
for all $b \in \mathbb{B}$. Note that the use of the series composition is
restricted to rules of the form $S_1 \to P \circ S_2$ and $S \to P_1 \circ P_2$.
This ensures that the P-components of an S-graph are parsed
left-to-right, thus avoiding the nondeterminism introduced by
the associativity of the series composition. By way of analogy,
a right-recursive regular word grammar reads words left to
right, just as a finite automaton. Fixing a parsing order for
S-components is an ingredient that allows us to build, from
the rules of the grammar, a recognizer for its language.

We establish first the existence of a universal aperiodic
regular series-parallel grammar, in order to prove the “only
if” direction of Theorem 3 for the SP class (Corollary 1). As
before, we annotate the rules of the grammar with their type
(Definition 8).

Lemma 24: Let $\Gamma_{SP} \stackrel{\text{def}}{=} (\{S, P\}, \mathcal{R})$ be the regular series-parallel grammar having the following rules, for all $b \in \mathbb{B}$:

- $\rightarrow$ P (E) $S \rightarrow b_{1,2}$ (C) $S \rightarrow P \circ S$ (C) $P \rightarrow P \parallel S$ (A)
- $\rightarrow$ S (E) $P \rightarrow b_{1,2}$ (D) $S \rightarrow P \circ P$ (C) $P \rightarrow S \parallel S$ (B)

Then, we have $\mathcal{L}^{SP}(\Gamma_{SP}) = SP$.

Proof. “⊆” Each graph $G \in \mathcal{L}^{SP}(\Gamma)$ is series-parallel, because the definition of $\Gamma_{SP}$ uses only operations from $\mathcal{F}_{SP}$.

"$\supseteq$" Let $G \in \mathcal{SP}$ be a series-parallel graph. By $X$-derivation of $G$ we mean a complete derivation $X \Rightarrow_{\Gamma}^{*} t$ such that $t^{\mathcal{SP}} = G$. We prove the following facts simultaneously:
- If $G$ is an $S$-graph then there exists a $S$-derivation of $G$,

- If $G$ is a $P$-graph then there exists a $P$-derivation of $G$.

Consider the following cases for the induction:

$G = b_{1,2}^{SP}$, for some $b \in \mathbb{B}$: The $P$-derivation applies the rule $P \to b_{1,2}$ of $\Gamma_{SP}$.

$G$ is a $P$-graph and not a single edge: in this case, we have $G = G_1 \parallel^{SP} \dots \parallel^{SP} G_k$, for some $k \ge 2$, where $G_1, \dots, G_k$ are either single edges or $S$-graphs, by Lemma 8. Let $i \in [1, k]$ be an index. If $G_i = b_{1,2}^{SP}$ is a single edge, there exists an $S$-derivation of $G_i$ using the rule $S \to b_{1,2}$ of $\Gamma_{SP}$. Otherwise, there is a $S$-derivation of $G_i$, by the inductive hypothesis. We obtain a $P$-derivation of $G$ by applying the rule $P \to S \parallel S$ once and $k-2$ times the rule $P \to P \parallel S$.

$G$ is an $S$-graph: in this case, we have $G = G_1 \circled{SP} \dots \circled{SP} G_k$, for some $k \ge 2$, where $G_1, \dots, G_k$ are $P$-graphs, by Lemma 8. Then, there exist a $P$-derivation of each $G_i$, for $i \in [1, k]$, by the inductive hypothesis. We obtain an $S$-derivation of $G$ by applying once the rule $S \to P \circ P$ and $k-2$ times the rule $S \to P \circ S$. $\square$ Note that $\mathrm{FP}(\Gamma_{SP}) \subseteq \mathrm{FP}_{SP}$ (Definition 20) and the only rule of the form (A) in $\Gamma_{SP}$ has exponent 1, hence $\Gamma_{SP}$ is an aperiodic regular series-parallel grammar.

To prove the “if” direction of Theorem 3 for the $SP$ class, let us fix a normalized regular series-parallel grammar $\Gamma = (S \uplus P, \mathcal{R})$. Since each stratified grammar can be normalized, this assumption loses no generality, by Lemma 1). In the rest of this section, we give the definition of a $\mathcal{F}_{SP}$-recognizer $(\mathcal{A}_{\Gamma}, B_{\Gamma})$ for the language $\mathcal{L}^{SP}(\Gamma)$, together with upper bounds on the size of the algebra $\mathcal{A}_{\Gamma}$ and the time required to compute the interpretation of a function symbol from $\mathcal{F}_{SP}$.

For two $\mathcal{F}_{SP}$-terms $u$ and $w$, we denote by $u \stackrel{\text{a}}{\sim} w$ the fact that $w$ can be obtained from $u$ by zero or more applications of the associativity axiom for serial composition:

$$ (x \circ y) \circ z = x \circ (y \circ z) \quad (3) $$

In the following, we write $u \stackrel{\text{a}}{\Rightarrow}_{\Gamma}^{*} w$ iff $u \stackrel{\text{a}}{\Rightarrow}_{\Gamma}^{*} v$ and $v \stackrel{\text{a}}{\sim} w$, for some $\mathcal{F}_{SP}$-term $v$. The following lemmata are used to (de-)compose partial derivations modulo associativity of the serial composition:

**Lemma 25:** Let $S \in \mathcal{S}$ and $Q \in P \uplus S$ be nonterminals. Then, for every derivation $S \stackrel{\text{a}}{\Rightarrow}_{\Gamma}^{*} u \circ Q$, there are nonterminals $P_1, \dots, P_n$, derivations $P_i \stackrel{\text{a}}{\Rightarrow}_{\Gamma}^{*} v_i$ and rules $S_i \to P_i \circ S_{i+1}$, for $1 \le i < n-1$, with $S = S_1$, and a rule $S_{n-1} \to P_n \circ Q$ such that $v_1 \circ (v_2 \circ \dots (v_n)) \stackrel{\text{a}}{\sim} u$.

**Proof.** We consider the derivation $S \stackrel{\text{a}}{\Rightarrow}_{\Gamma}^{*} t[Q]$, where $t[Q]$ is a term such that $t[Q] \stackrel{\text{a}}{\sim} u \circ Q$. We note that the only rules of a regular SP-grammar that generate series compositions are the rules of shape $S_1 \to P \circ S_2$ and $S \to P_1 \circ P_2$. Further, because $Q$ occurs at the right-most position of a series-composition of terms, we must have (up to a reordering

of the rule applications) that the derivation $S \stackrel{\text{a}}{\Rightarrow}_{\Gamma}^{*} t[Q]$ has the form

$$ \begin{align*} S_1 &\Rightarrow_{\Gamma} P_1 \circ S_2 \Rightarrow_{\Gamma} P_1 \circ (P_2 \circ S_3) \\ &\vdots \\ &\Rightarrow_{\Gamma} P_1 \circ (P_2 \circ \dots (P_n \circ Q) \dots) \\ &\Rightarrow_{\Gamma}^{*} v_1 \circ (P_2 \circ \dots (P_n \circ Q) \dots) \\ &\Rightarrow_{\Gamma}^{*} v_1 \circ (v_2 \circ \dots (P_n \circ Q) \dots) \\ &\vdots \\ &\Rightarrow_{\Gamma}^{*} v_1 \circ (v_2 \circ \dots (v_n \circ Q) \dots) \end{align*} $$

where $S = S_1$ and $P_i \Rightarrow_{\Gamma}^{*} v_i$ are complete derivations. Then, $v_1 \circ (v_2 \circ \dots (v_n \circ Q) \dots) \stackrel{\text{a}}{\sim} u \circ Q$, and we get that $v_1 \circ (v_2 \circ \dots (v_n) \dots) \stackrel{\text{a}}{\sim} u$. $\square$

**Lemma 26:** Let $S \in \mathcal{S}$ and $Q \in P \uplus S$ be nonterminals and $G$ be an $S$-graph. For all graphs $G_1, G_2 \in \mathcal{SP}$, such that $G = G_1 \circled{SP} G_2$, the following are equivalent:

1. there exists a derivation $S \stackrel{\text{a}}{\Rightarrow}_{\Gamma}^{*} u \circ Q$, where $u$ is a ground $\mathcal{F}_{SP}$-term such that $u^{SP} = G$,

2. there exist derivations $S \stackrel{\text{a}}{\Rightarrow}_{\Gamma}^{*} u_1 \circ S'$ and $S' \stackrel{\text{a}}{\Rightarrow}_{\Gamma}^{*} u_2 \circ Q$, where $S' \in \mathcal{S}$ and $u_i$ are ground $\mathcal{F}_{SP}$-terms such that $u_i^{SP} = G_i$, for $i = 1, 2$.

**Proof.** “(1) $\Rightarrow$ (2)” We assume that there exists a derivation $S \stackrel{\text{a}}{\Rightarrow}_{\Gamma}^{*} u \circ Q$, where $u$ is a ground $\mathcal{F}_{SP}$-term such that $u^{SP} = G$. By Lemma 25, there are non-terminals $P_1, \dots, P_n$, derivations $P_i \Rightarrow_{\Gamma}^{*} v_i$ and rules $S_i \to P_i \circ S_{i+1}$, for $1 \le i < n-1$, with $S = S_1$, and a rule $S_{n-1} \to P_n \circ Q$ such that $v_1 \circ (v_2 \circ \dots (v_n)) \stackrel{\text{a}}{\sim} u$. Hence, $v_1^{SP} \circ \dots \circ v_n^{SP} = u^{SP} = G_1 \circled{SP} G_2$. Then, there exists $i \in [1, n-1]$ such that $G_1 = v_1^{SP} \circ \dots \circ v_n^{SP}$ and $G_2 = v_{i+1}^{SP} \circ \dots \circ v_n^{SP}$. We choose $S' \stackrel{\text{def}}{=} S_{i+1}$ and check that indeed $S \stackrel{\text{a}}{\Rightarrow}_{\Gamma}^{*} u_1 \circ S'$ and $S' \stackrel{\text{a}}{\Rightarrow}_{\Gamma}^{*} u_2 \circ Q$, where $u_1$ and $u_2$ are ground terms such that $u_1 \stackrel{\text{a}}{\sim} v_1 \circ \dots \circ v_i$ and $u_2 \stackrel{\text{a}}{\sim} v_{i+1} \circ \dots \circ v_n$.

“(2) $\Rightarrow$ (1)” We assume that there exist derivations $S \stackrel{\text{a}}{\Rightarrow}_{\Gamma}^{*} u_1 \circ S'$ and $S' \stackrel{\text{a}}{\Rightarrow}_{\Gamma}^{*} u_2 \circ Q$, where $S' \in \mathcal{S}$ and $u_i$ are ground $\mathcal{F}_{SP}$-terms such that $u_i^{SP} = G_i$, for $i = 1, 2$. By Lemma 25, there are non-terminals $P_1, \dots, P_n$, derivations $P_i \Rightarrow_{\Gamma}^{*} v_i$ and rules $S_i \to P_i \circ S_{i+1}$, for $1 \le i < n-1$, with $S_1 = S$ and $S_{k+1} = S'$ and a rule $S_{n-1} \to P_n \circ Q$ such that $u_1 \stackrel{\text{a}}{\sim} v_1 \circ \dots \circ v_k$ and $u_2 \stackrel{\text{a}}{\sim} v_{k+1} \circ \dots \circ v_n$. By composing the above derivations, we obtain a derivation $S \stackrel{\text{a}}{\Rightarrow}_{\Gamma}^{*} (v_1 \circ \dots \circ v_k) \circ (v_{k+1} \circ \dots \circ v_n) \circ Q$. Moreover, we have $(v_1 \circ \dots \circ v_k)^{SP} \circ \dots \circ (v_{k+1} \circ \dots \circ v_n)^{SP} = u_1^{SP} \circ \dots \circ u_2^{SP} = G_1 \circled{SP} G_2 = G$, hence we can choose $u \stackrel{\text{def}}{=} v_1 \circ \dots v_n$, thus obtaining $S \stackrel{\text{a}}{\Rightarrow}_{\Gamma}^{*} u \circ Q$ and $u^{SP} = G$. $\square$

In order to simplify the development of the recognizer we consider regular series-parallel grammars in alternative form:

**Definition 21:** A regular series-parallel grammar in alternative form is a stratified $\mathcal{F}_{SP}$-grammar $\Gamma = (P \uplus S, \mathcal{R})$ such that $\mathrm{FP}(\Gamma) \subseteq \mathrm{FP}_{SP}$, where

$$ \mathrm{FP}_{SP} \stackrel{\text{def}}{=} \{ \mathbf{P} \to S^{\# \ge 1}, \mathbf{S} \to \mathbf{P} \circ \mathbf{S}, \mathbf{S} \to \mathbf{P} \circ \mathbf{P}, \mathbf{P}, \to \mathbf{S} \} \cup \{ \mathbf{S} \to b_{1,2} | b \in \mathbb{B} \}, $$
<figure><img src="image_12.png" /><figcaption>Fig. 11. A derivation $S \stackrel{*}{\Rightarrow}_{\Gamma} (v_1 \circ (v_2 \circ (\dots Q)) \dots)$ (a) A view of the graph $G = (v_1 \circ \dots \circ v_n)^{SP}$ corresponding to $S \stackrel{\mathbf{a}}{\Rightarrow}_{\Gamma} (v_1 \circ v_2 \dots v_n) \circ Q$ (b)</figcaption></figure>

and we require in addition that for every rule $P \to S \in \mathcal{R}$ there is some rule $S \to b_{1,2} \in \mathcal{R}$ and $S$ does not occur in any other rule of $\mathcal{R}$.

Every regular grammar $\Gamma$ can be transformed into a regular grammar in alternative form $\hat{\Gamma} = (\hat{S} \uplus \mathcal{P}, \hat{\mathcal{R}})$, by setting $\hat{S} \stackrel{\text{def}}{=} S \uplus \{S_b \mid b \in \mathbb{B}\}$, for some fresh nonterminals $S_b \notin \mathcal{S}$, and replacing each rule $P \to b_{1,2} \in \mathcal{R}$ by the rules $P \to S_b, S_b \to b_{1,2} \in \mathcal{R}$. It is straightforward to see that $\mathcal{L}^{SP}(\hat{\Gamma}) = \mathcal{L}^{SP}(\Gamma)$ (in every derivation one can replace the derivation steps $P \to S_b, S_b \to b_{1,2}$ with $P \to b_{1,2}$, and vice verse), and that $\hat{\Gamma}$ is aperiodic iff $\Gamma$ is aperiodic. Clearly, $\text{size}(\Gamma) = \Theta(\text{size}(\hat{\Gamma}))$. Similarly, every regular grammar in alternative form can be turned into a regular grammar. Hence, the regular grammars and the regular grammars in alternative form are in a one-to-one correspondence<fnref n="14" />. We work with regular grammars in alternative form in the following because we can define the views of P-graphs as multisets of nonterminals from $S$:

**Definition 22:** Let $G$ be a series-parallel graph and $\Gamma = (S \uplus \mathcal{P}, \mathcal{R})$ be a normalized regular series-parallel grammar in alternative form. We distinguish the following cases:

1) $G$ is a P-graph: in this case, a view of $G$ for $\Gamma$ is a multiset $\{\{S_1, \dots, S_n\}\} \in \text{mpow}(S)$ for which there exist complete derivations $S_i \Rightarrow_{\Gamma}^* v_i$, for all $i \in [1, n]$, such that $G = (v_1 \parallel \dots \parallel v_n)^{SP}$. A reduced view of $G$ is a multiset $[m]_{\Gamma}$ such that $m$ is a view of $G$, for $\Gamma$.

2) $G$ is an S-graph: in this case, a view of $G$ for $\Gamma$ is a pair $(S, Q) \in S \times (S \uplus \mathcal{P} \uplus \{\perp\})$ for which there exists a derivation, either $S \stackrel{\mathbf{a}}{\Rightarrow}_{\Gamma}^* v \circ Q$, if $Q \neq \perp$, or $S \Rightarrow_{\Gamma}^* v$, if $Q = \perp$, for a ground term $v$, such that $G = v^{SP}$. This view is reduced, by definition.

The *profile* of $G$ for $\Gamma$ is the set $h_{\Gamma}(G)$ of reduced views of $G$ for $\Gamma$. We call $h_{\Gamma}(G)$ a *P-profile* (resp. *S-profile*) if $G$ is a P-graph (resp. an S-graph).

The distinction between P- and S-graphs plays an important role in the definition of (reduced) views. Intuitively, a view $\{\{S_1, \dots, S_n\}\}$ of a P-graph $G$ denotes the precise information of how $G$ can be obtained as a possible (sub-)derivation of some larger derivation; here, the alternative form of the regular grammars allows us to also represent single edges as such a multiset $\{\{S\}\}$. On the other hand, the views of S-graphs are

$$ 
\begin{aligned}
\frac{S \to b_{1,2} \in \mathcal{R}}{\{\{S\}\} \in b_{1,2}^{A_{\Gamma}}} b_{1,2} & \\
\frac{\{m_i \in a_i\}_{i=1,2}}{[m_1 + m_2]_{\Gamma} \in a_1 \parallel^{A_{\Gamma}} a_2} P \parallel P & \\
\frac{m \in a_1, (S, \perp) \in a_2}{[m + \{\{S\}\}]_{\Gamma} \in a_1 \parallel^{A_{\Gamma}} a_2} P \parallel S & \\
\frac{\{(S_i, \perp) \in a_i\}_{i=1,2}}{[\{\{S_1\}\} + \{\{S_2\}\}]_{\Gamma} \in a_1 \parallel^{A_{\Gamma}} a_2} S \parallel S & \\
\frac{\{P_i \rightsquigarrow \Gamma m_i \in a_i\}_{i=1,2}}{(S, Q) \in a_1 \circ^{A_{\Gamma}} a_2} P \to P_1 \circ S_1, S_1 \to P_2 \circ Q \in \mathcal{R} & P \circ_1 P \\
\frac{\{P_i \rightsquigarrow \Gamma m_i \in a_i\}_{i=1,2}}{S \to P_1 \circ P_2 \in \mathcal{R}} (S, Q) \in a_1 \circ^{A_{\Gamma}} a_2 & P \circ_2 P \\
\frac{P \rightsquigarrow \Gamma m \in a_1, (S_1, Q) \in a_2}{(S, Q) \in a_1 \circ^{A_{\Gamma}} a_2} S \to P \circ S_1 \in \mathcal{R} & P \circ S \\
\frac{(S, S_1) \in a_1, (S_1, Q) \in a_2}{(S, Q) \in a_1 \circ^{A_{\Gamma}} a_2} S \circ S & S \circ S \\
\frac{(S, S_1) \in a_1, P \rightsquigarrow \Gamma m \in a_2}{S_1 \to P \circ Q \in \mathcal{R}} (S, Q) \in a_1 \circ^{A_{\Gamma}} a_2 & S \circ_1 P \\
\frac{(S, P) \in a_1, P \rightsquigarrow \Gamma m \in a_2}{(S, \perp) \in a_1 \circ^{A_{\Gamma}} a_2} S \circ_2 P
\end{aligned}
$$

<caption>Fig. 12. The interpretation of the signature $\mathcal{F}_{SP}$ in $\mathcal{A}_{\Gamma}$</caption>

pairs $(S, Q) \in S \times (S \uplus \mathcal{P} \uplus \{\perp\})$ that correspond to all possible (sub-)derivations of some larger derivation. Due to the associativity of the serial composition, the ground subterms in such a derivation can be grouped into a single ground term $v$ with $S \stackrel{\mathbf{a}}{\Rightarrow}_{\Gamma}^* v \circ Q$, see Figure 11.

We define the finite algebra $\mathcal{A}_{\Gamma}$ having domain $A_{\Gamma} \stackrel{\text{def}}{=} \{h_{\Gamma}(G) \mid G \in \text{SP}\}$, where the interpretations of the function symbols from $\mathcal{F}_{SP}$ are the least sets built according to the inference rules from Figure 12. The rules that define $\parallel^{A_{\Gamma}}$ and $\circ^{A_{\Gamma}}$ are named according to the type of their arguments, e.g., $S \circ_1 P$ and $S \circ_2 P$ define the result of $\circ^{A_{\Gamma}}$ when the first argument is an S-profile and the second is a P-profile, etc.

We give upper bounds on the size of the recognizer algebra and the time needed to evaluate the interpretation of the function symbols. The size of an element $a \in A_{\Gamma}$ is defined as follows:

$$ \text{size}(a) \stackrel{\text{def}}{=} \left\{ \begin{array}{ll} \sum_{m \in a} \text{card}(m), & \text{if } a \text{ is a P-profile} \\ 2 \cdot \text{card}(a), & \text{if } a \text{ is an S-profile} \end{array} \right. $$

**Lemma 27:** Let $\Gamma = (S \uplus \mathcal{P}, \mathcal{R})$ be a normalized regular series-parallel grammar in alternative form. Then, $\text{card}(A_{\Gamma}) \in 2^{\text{size}(\Gamma)^{\text{poly}(\text{size}(\Gamma))}}$, $\text{size}(a) \in \text{size}(\Gamma)^{\text{poly}(\text{size}(\Gamma))}$, for

<footnote n="14">¹⁴We note that regular grammars in alternative form are not regular grammars in general because rules $P \to S$ do not satisfy the footprint constraint $P \to S^{\ge 2}$ from Definition 20.</footnote>
each $a \in A_\Gamma$ and $f^{A_\Gamma}(a_1, \dots, a_{\#f})$ is computable in time $size(\Gamma)^{\text{poly}(size(\Gamma))}$, for each function symbol $f \in \mathcal{F}_{SP}$ and all elements $a_1, \dots, a_{\#f} \in A_\Gamma$.

**Proof.** As in the proof of Lemma 4, we obtain that there are at most $size(\Gamma)^{\text{poly}(card(S))}$ different reduced multisets and hence at most $2^{size(\Gamma)^{\text{poly}(card(S))}}$ different sets of reduced multisets. Moreover, there are $card(S) \cdot (card(S) + card(P) + 1) \in \text{poly}(card(S) + card(P))$ many different pairs of the form $(S, Q) \in S \times (S \uplus P \uplus \{\perp\})$. Hence, there are at most different $2^{\text{poly}(card(S)+card(P))}$ sets of such pairs. Thus, we obtain:

$$ \text{card}(A_{\Gamma}) \in 2^{\text{size}(\Gamma)^{\text{poly}(card(S))}} + 2^{\text{poly}(card(S)+card(P))} \\ \in 2^{\text{size}(\Gamma)^{\text{poly}(size(\Gamma))}} $$

We note that an element $a \in A_\Gamma$ is either a set of reduced multisets or a set of pairs $(S, Q) \in S \times (S \uplus P \uplus \{\perp\})$. As in the proof of Lemma 4, there are at most $size(\Gamma)^{\text{poly}(card(S))}$ different reduced multisets $m$, for which we have $card(m) \in size(\Gamma)^{\text{poly}(card(S))}$. Hence, for each $a \in A_\Gamma$, we obtain:

$$ \text{size}(a) \in \max \left( \text{size}(\Gamma)^{\text{poly}(card(S))}, \text{poly}(card(S) + card(P)) \right) \\ \in \text{size}(\Gamma)^{\text{poly}(size(\Gamma))} $$

We compute an upper bound on the time needed to evaluate the function $f^{A_\Gamma}$, for each $f \in \mathcal{F}_{SP}$:

- $b_{1,2}^{A_\Gamma}$: is computed in linear time by going over all the rules of $\Gamma$, where $size(\Gamma) = \mathcal{O}(size(\Gamma))$.

- $a_1 \|^{A} a_2$: We note that for P-profiles $a_1, a_2$, the value of $a_1 \|^{A} a_2$ can be computed in time $size(\Gamma)^{\text{poly}(card(S))} \subseteq size(\Gamma)^{\text{poly}(size(\Gamma))}$, by the same arguments as in the proof of Lemma 4. We note that the cases, where at least one of $a_1$ and $a_2$ is an S-profile are similar.

- $a_1 \circ^{A} a_2$: First, we assume that $a_1$ and $a_2$ are both S-profiles. Then, the computation of $a_1 \circ^{A} a_2$ requires to check for every pair $(S, Q)$ whether there is an $S_1 \in S$ such that $(S, S_1) \in a_1$ and $(S_1, Q) \in a_2$. Clearly, this can be done in $\text{poly}(card(S) + card(P)) \subseteq size(\Gamma)^{\text{poly}(size(\Gamma))}$. In case $a_1$ is a P-profile and $a_2$ is an S-profile, for every pair $(S, Q)$, we need to iterate over all rules $S \to P \circ S_1 \in \mathcal{R}$ and $m \in a_1$ and check whether $(S_1, Q) \in a_2$ and $P \rightsquigarrow \Gamma$ $m$. We note that there are at most $size(\Gamma)^{\text{poly}(card(S))}$ many multisets $m \in a_1$. As in the proof of Lemma 4, the check $P \rightsquigarrow \Gamma$ $m$, for a given nonterminal $P$ and multiset $m$, takes time $size(\Gamma)^{\text{poly}(card(S))}$. As there are at most $\text{poly}(card(S) + card(P))$ many pairs $(S_1, Q) \in a_2$, we overall get that $a_1 \circ^{A} a_2$, in this case, can be computed in $size(\Gamma)^{\text{poly}(card(S))} \subseteq size(\Gamma)^{\text{poly}(size(\Gamma))}$. The other cases are similar and give the same asymptotic complexity bound. $\square$

We establish now the counterparts of Lemmas 5 and 6. First, equality of profiles amounts to indistinguishability of graphs with respect to membership in $\mathcal{L}^{SP}(\Gamma)$:

**Lemma 28:** For all $G_1, G_2 \in SP$, if $h_\Gamma(G_1) = h_\Gamma(G_2)$ then $G_1 \in \mathcal{L}^{SP}(\Gamma) \iff G_2 \in \mathcal{L}^{SP}(\Gamma)$.

**Proof.** If $h_\Gamma(G_1) = h_\Gamma(G_2)$ then $G_1$ and $G_2$ are either both P-graphs or both S-graphs. Assume that $G_1 \in \mathcal{L}^{SP}(\Gamma)$. We prove that $G_2 \in \mathcal{L}^{SP}(\Gamma)$ by considering the following cases:

$G_1, G_2$ are P-graphs: Since $G_1 \in \mathcal{L}^{SP}(\Gamma)$, there exists a complete derivation $P \Rightarrow_{\Gamma}^{*} v$, for some axiom $\to P$ of $\Gamma$ such that $v^{SP} = G_1$. Without loss of generality, the derivation can be reorganized as:

$$ P \Rightarrow_{\Gamma}^{*} \|_{S \in S} S^{\#m_1(S)} \Rightarrow_{\Gamma}^{*} \|_{S \in S, i \in [1, m_1(S)]} v^1(S, i) $$

for a multiset $m_1 \in \text{mpow}(S)$ and ground terms $v_1(S, i)$ such that $G_1 = (\|_{S \in S, i \in [1, m_1(S)]} v_1(S, i))^{SP}$. Then, $m_1$ is a view of $G_1$, hence $[m_1]_\Gamma \in h_\Gamma(G_1)$. Because $h_\Gamma(G_1) = h_\Gamma(G_2)$, there exists a view $m_2$ of $G_2$ such that $[m_2]_\Gamma = [m_1]_\Gamma$. Moreover, $P \rightsquigarrow \Gamma m_1$, hence $P \rightsquigarrow [m_1]_\Gamma = [m_2]_\Gamma$ and $P \rightsquigarrow \Gamma m_2$, by Lemma 18. We obtain a derivation:

$$ P \Rightarrow_{\Gamma}^{*} \|_{S \in S} S^{\#m_2(S)} \Rightarrow_{\Gamma}^{*} \|_{S \in S, i \in [1, m_2(S)]} v_2(S, i) $$

for some ground terms $v_2(S, i)$ such that $G_1 = (\|_{S \in S, i \in [1, m_2(S)]} v_2(S, i))^{SP}$. Since $\to P$ is an axiom of $\Gamma$, we obtain that $G_2 \in \mathcal{L}^{SP}(\Gamma)$.

$G_1, G_2$ are S-graphs: Since $G_1 \in \mathcal{L}^{SP}(\Gamma)$, there exists a complete derivation $S \Rightarrow_{\Gamma}^{*} v_1$, such that $G_1 = v^{SP}$, for some axiom $\to S$ of $\Gamma$. Then, $(S, \perp) \in h_\Gamma(G_1) = h_\Gamma(G_2)$, hence there exists a complete derivation $S \Rightarrow_{\Gamma}^{*} v_2$ such that $v_2^{SP} = G_2$, leading to $G_2 \in \mathcal{L}^{SP}(\Gamma)$.

The direction $G_2 \in \mathcal{L}^{SP}(\Gamma) \Rightarrow G_1 \in \mathcal{L}^{SP}(\Gamma)$ is symmetric. $\square$

**Lemma 29:** $h_\Gamma$ is a homomorphism between the $\mathcal{F}_{SP}$-algebras $SP$ and $A_\Gamma$.

**Proof.** We prove the following points, for all $b \in \mathbb{B}$ and $G_1, G_2 \in SP$:

$h_\Gamma(b_{1,2}^{SP}) = b_{1,2}^{A_\Gamma}$: Since $b_{1,2}^{SP}$ is a P-graph, we have $h_\Gamma(b_{1,2}^{SP}) = \{\{S\} | S \to b_{1,2} \in \mathcal{R}\} = b_{1,2}^{A_\Gamma}$, where $b_{1,2}^{A_\Gamma}$ is obtained by the inference rule $(b_{1,2})$ from Figure 12.

$h_\Gamma(G_1 \|^{SP} G_2) = h_\Gamma(G_1) \|^{A_\Gamma} h_\Gamma(G_2)$: Since $G_1 \|^{SP} G_2$ is a P-graph, each element of $h_\Gamma(G_1 \|^{SP} G_2)$ is a multiset $m \in \text{mpow}(S)$ for which there exists a view $m'$ of $G_1 \|^{SP} G_2$ such that $m = [m']_\Gamma$. We distinguish the following cases, according to the types of $G_1$ and $G_2$:

- $G_1$ and $G_2$ are P-graphs: “$\subseteq$” Let $m \in h_\Gamma(G_1 \|^{SP} G_2)$ and $m'$ be the view of $G_1 \|^{SP} G_2$ such that $m = [m']_\Gamma$. Then, for each $S \in S$ and $i \in [1, m'(S)]$, there exists a complete derivation $S \Rightarrow_{\Gamma}^{*} v(S, i)$, where $v(S, i)$ is a ground term such that $G_1 \|^{SP} G_2 = (\|_{S \in S, i \in [1, m'(S)]} v(S, i))^{SP}$. We split the set of ground terms $v(S, i)$ according to whether $v(S, i)^{SP}$ is a subgraph of $G_1$ or of $G_2$, thus obtaining views $m'_i$ of $G_i$ such that $m' = m'_1 + m'_2$. Since $[m'_i]_\Gamma \in h_\Gamma(G_i)$ and $m = [m'_1 + m'_2]_\Gamma = [m'_1]_\Gamma + [m'_2]_\Gamma$, by Lemma 2, we obtain $m \in h_\Gamma(G_1) \|^{A_\Gamma} h_\Gamma(G_2)$, by applying the inference rule $(P \| P)$ from Figure 12.

“$\supseteq$” Let $m \in h_\Gamma(G_1) \|^{A_\Gamma} h_\Gamma(G_2)$ be a multiset. Since both $h_\Gamma(G_i)$ are P-profiles, for $i = 1, 2$, by the inference rule $(P \| P)$ from Figure 12, there exist $m_i \in h_\Gamma(G_i)$, for
i = 1, 2, such that $m = [m_1 + m_2]_\Gamma$. Then, there exist views $m'_i$ of $G_i$ such that $m_i = [m'_i]_\Gamma$. By Lemma 2, we obtain $m = [m'_1 + m'_2]_\Gamma$, hence $m'_1 + m'_2$ is a view of $G_1 \|^{SP} G_2$ for $\Gamma$, thus $m \in h_\Gamma(G_1) \|^{SP} G_2$.

- $G_i$ is a P-graph and $G_{3-i}$ is an S-graph, for $i = 1, 2$: We assume that $i = 1$, the proof being the same for the case $i = 2$, because of the commutativity of $\|^{SP}$ and $\|^{A_\Gamma}$. “$\subseteq$” Let $m \in h_\Gamma(G_1) \|^{SP} G_2)$ and $m'$ be the view of $G_1 \|^{SP} G_2$ such that $m = [m']_\Gamma$. Then, for each $S \in S$ and $i \in [1, m'(S)]$, there exists a complete derivation $S \Rightarrow^* v(S, i)$, where $v(S, i)$ is a ground term such that $G_1 \|^{SP} G_2 = (\|_{S \in S, i \in [1, m'(S)]} v(S, i))^{SP}$. Since $G_2$ is an S-graph, the only possibility is that $G_2 = v(S, i)^{SP}$, for a single $S \in S$ and $i \in [1, m'(S)]$, such that $S \Rightarrow^* v(S, i)$ is a complete derivation. Then, $(S, \perp) \in h_\Gamma(G_2)$. Moreover, $m'_1 \stackrel{\text{def}}{=} m' - \{\{S\}\}$ (where $-$ here denotes multiset difference) is a view of $G_1$ for $\Gamma$ and $m'_1 \stackrel{\text{def}}{=} [m'_1]_\Gamma \in h_\Gamma(G_1)$. By Lemma 2, we obtain $m = [m_1 + \{\{S\}\}]_\Gamma$, thus $m \in h_\Gamma(G_1) \circ^{A_\Gamma} h_\Gamma(G_2)$, by applying the inference rule (P $\|$ S) from Figure 12.

“$\supseteq$” Let $m \in h_\Gamma(G_1) \|^{A_\Gamma} h_\Gamma(G_2)$ be a multiset. Since $h_\Gamma(G_1)$ is a P-profile and $h_\Gamma(G_2)$ is an S-profile, by the inference rule (P $\|$ S) from Figure 12, there exists $m_1 \in h_\Gamma(G_1)$ and $(S, \perp) \in h_\Gamma(G_2)$ such that $m = [m_1 + \{\{S\}\}]_\Gamma$. Then, there exists a view $m'_1$ of $G_1$ such that $m'_1 = [m'_1]_\Gamma$. Moreover, there exists a complete derivation $S \Rightarrow^* v$ such that $v^{SP} = G_2$. Hence, $m'_1 + \{\{S\}\}$ is a view of $G_1 \|^{SP} G_2$ for $\Gamma$ and $m = [m_1 + \{\{S\}\}]_\Gamma = [[m'_1]_\Gamma + \{\{S\}\}]_\Gamma$, by Lemma 2, thus $m \in h_\Gamma(G_1) \|^{SP} G_2)$.

- $G_1$ and $G_2$ are S-graphs: “$\subseteq$” Let $m \in h_\Gamma(G_1) \|^{SP} G_2)$ and $m'$ be the view of $G_1 \|^{SP} G_2$ such that $m = [m']_\Gamma$. Then, $m' = \{\{S_1, S_2\}\}$ and there are complete derivations $S_i \Rightarrow^* v_i$, for $i = 1, 2$, where $v_i$ is a ground term such that $G_i = v_i^{SP}$. Then, we obtain $(S_i, \perp) \in h_\Gamma(G_i)$, for $i = 1, 2$. Moreover, $m' = \{\{S_1\} + \{\{S_2\}\}$. Thus, $m \in h_\Gamma(G_1) \|^{A_\Gamma} h_\Gamma(G_2)$, by applying the inference rule (S $\|$ S) from Figure 12.

“$\supseteq$” Let $m \in h_\Gamma(G_1) \|^{A_\Gamma} h_\Gamma(G_2)$ be a multiset. Since both $h_\Gamma(G_i)$ are S-profiles, for $i = 1, 2$, by the inference rule (S $\|$ S) from Figure 12, there exist views $(S_i, \perp) \in h_\Gamma(G_i)$, hence complete derivations $S_i \Rightarrow^*_\Gamma v_i$ such that $G_i = v_i^{SP}$, for $i = 1, 2$ and $m = [\{\{S_1\} + \{\{S_2\}\}]_\Gamma$. Then, $\{\{S_1\} + \{\{S_2\}\}$ is a view of $G_1 \|^{SP} G_2$ for $\Gamma$, hence $m \in h_\Gamma(G_1) \|^{SP} G_2)$.

$h_\Gamma(G_1 \circ^{SP} G_2) = h_\Gamma(G_1) \circ^{A_\Gamma} h_\Gamma(G_2)$: Since $G_1 \circ^{SP} G_2$ is an S-graph, any view of it for $\Gamma$ is a pair $(S, Q)$, such that $S \in S$ and $Q \in S \uplus P \uplus \{\perp\}$. We distinguish the following cases, according to the types of $G_1$ and $G_2$:

- $G_1$ and $G_2$ are P-graphs: “$\subseteq$” Let $(S, Q) \in h_\Gamma(G_1 \circ^{SP} G_2)$ and assume $Q \neq \perp$ (the case $Q = \perp$ is similar). By Definition 22 (2), there exists a derivation $S \stackrel{a}{\Rightarrow}^*_\Gamma v \circ Q$, for a ground term $v$ such that $G_1 \circ^{SP} G_2 = v^{SP}$. By Lemma 26, there exist derivations $S \stackrel{a}{\Rightarrow}^*_\Gamma v_1 \circ S'$ and $S' \stackrel{a}{\Rightarrow}^*_\Gamma v_2 \circ Q$, for some nonterminal $S' \in S$ and ground terms $v_i$ such that $G_i = v_i^{SP}$, for $i = 1, 2$. Then, by Lemma 25, and because $G_1$ and $G_2$ are $\circ$-atomic, there are rules $S \to P_1 \circ S'$ and

$S' \to P_2 \circ Q$, and complete derivations $P_i \Rightarrow^*_\Gamma v_i$ for some non-terminals $P_1, P_2 \in P$. By a reordering, we can assume w.l.o.g. that these complete derivations are of the form:

$$P_i \Rightarrow^*_\Gamma \|_{S \in S} S^{\sharp m_i(S)} \Rightarrow^*_\Gamma v_i$$

for some views $m_i$ of $G_i$ for $\Gamma$, for $i = 1, 2$. Then, $P_i \rightsquigarrow \Gamma m_i$, and we obtain $P_i \rightsquigarrow [m_i]_\Gamma$, by Lemma 18, for $i = 1, 2$. Moreover, $[m_i]_\Gamma \in h_\Gamma(G_i)$, for $i = 1, 2$. Thus, we obtain $(S, Q) \in h_\Gamma(G_1) \circ^{A_\Gamma} h_\Gamma(G_2)$, by applying the inference rule (P $\circ$ 1 P) from Figure 12.

“$\supseteq$” Let $(S, Q) \in h_\Gamma(G_1) \circ^{A_\Gamma} h_\Gamma(G_2)$ and assume $Q \neq \perp$ (the case $Q = \perp$ is similar). Since both $h_\Gamma(G_i)$ are P-profiles, by the inference rule (P $\circ$ 1 P) from Figure 12, there exists rules $S \to P_1 \circ S_1$ and $S_1 \to P_2 \circ Q$ in $\Gamma$, such that $P_i \rightsquigarrow \Gamma m_i \in h_\Gamma(G_i)$, for $i = 1, 2$. Then, there are views $m'_i$ of $G_i$, with $[m'_i]_\Gamma = m_i$, for $i = 1, 2$, hence also derivations:

$$P_i \Rightarrow^*_\Gamma \|_{S \in S} S^{\sharp m'_i(S)} \Rightarrow^*_\Gamma v_i,$$

for some ground terms $v_i$, such that $G_i = v_i^{SP}$. Then, we obtain $P_i \rightsquigarrow \Gamma m'_i$, by Lemma 18, for $i = 1, 2$. Thus, we can build a derivation:

$$S \Rightarrow_\Gamma P_1 \circ S_1 \Rightarrow_\Gamma P_1 \circ P_2 \circ Q \stackrel{a}{\Rightarrow}^*_\Gamma v_1 \circ v_2 \circ Q$$

such that $G_1 \circ^{SP} G_2 = (v_1 \circ v_2)^{SP}$ and $(S, Q) \in h_\Gamma(G_1 \circ^{SP} G_2)$, by Definition 22 (2).

- $G_1$ is a P-graph and $G_2$ is an S-graph: “$\subseteq$” Let $(S, Q) \in h_\Gamma(G_1 \circ^{SP} G_2)$ be a view of $G_1 \circ^{SP} G_2$ and assume $Q \neq \perp$ (the case $Q = \perp$ is similar). By Definition 22 (2), there exists a derivation $S \stackrel{a}{\Rightarrow}^*_\Gamma v \circ Q$, for a ground term $v$ such that $G_1 \circ^{SP} G_2 = v^{SP}$. By Lemma 26, there exist derivations $S \stackrel{a}{\Rightarrow}^*_\Gamma v_1 \circ S_1$ and $S_1 \stackrel{a}{\Rightarrow}^*_\Gamma v_2 \circ Q$, for some $S_1 \in S$, such that $v_i^{SP} = G_i$, for $i = 1, 2$. Then, by Lemma 25, and because $G_1$ is $\circ$-atomic, there is a rule $S \to P \circ S_1$ and a complete derivations $P \Rightarrow^*_\Gamma v_1$ for some non-terminal $P \in P$. By a reordering, if necessary, we assume the latter derivation to have the form:

$$P \Rightarrow^*_\Gamma \|_{S \in S} S^{\sharp m(S)} \Rightarrow^*_\Gamma \|_{S \in S, i \in [1, m(S)]} v_1(S, i)$$

for some multiset $m \in mpow(S)$, where $v_1(S, i)$ are ground terms such that $G_1 = (\|_{S \in S, i \in [1, m(S)]} v_1(S, i))^{SP}$. Then, $m$ is a view of $G_1$ for $\Gamma$ such that $P \rightsquigarrow \Gamma m$. By Lemma 18, we obtain $P \rightsquigarrow [m]_\Gamma \in h_\Gamma(G_1)$. Moreover, since $G_2$ is an S-graph, we obtain $(S, Q) \in h_\Gamma(G_2)$, by Definition 22 (2). Thus we obtain $(S, Q) \in h_\Gamma(G_1) \circ^{A_\Gamma} h_\Gamma(G_2)$, by an application of the inference rule (P $\circ$ S) from Figure 12.

“$\supseteq$” Let $(S, Q) \in h_\Gamma(G_1) \circ^{A_\Gamma} h_\Gamma(G_2)$ and assume $Q \neq \perp$ (the case $Q = \perp$ is similar). Since $h_\Gamma(G_1)$ is a P-profile and $h_\Gamma(G_2)$ is an S-profile, by the inference rule (P $\circ$ S), there exists a rule $S \to P \circ S_1$ in $\Gamma$ such that $P \rightsquigarrow \Gamma m$, for some reduced view $m \in h_\Gamma(G_1)$, and $(S_1, Q) \in h_\Gamma(G_2)$. Then, there exists a view $m'$ of $G_1$, such that $[m']_\Gamma = m$. We obtain $P \rightsquigarrow \Gamma m'$, by Lemma 18. Hence, there exists a derivation:

$$P \Rightarrow^*_\Gamma \|_{S \in S} S^{\sharp m'(S)} \Rightarrow^*_\Gamma v_1,$$
for some ground term $v_1$, such that $G_1 = v_1^{SP}$. Moreover, $(S_1, Q) \in h_\Gamma(G_2)$, hence there exists a derivation $S_1 \stackrel{a}{\Rightarrow}_\Gamma v_2 \circ Q$, where $v_2$ is a ground term such that $G_2 = v_2^{SP}$. We can build a derivation:

$$S \Rightarrow_\Gamma P \circ S_1 \Rightarrow_\Gamma^* (\|_{S \in S} S^{\sharp m'(S)} \circ S_1 \stackrel{a}{\Rightarrow}_\Gamma^* v_1 \circ v_2 \circ Q.$$

Then, $(v_1 \circ v_2)^{SP} = G_1 \circ^{SP} G_2$ and $(S, Q) \in h_\Gamma(G_1 \circ^{SP} G_2)$, by Definition 22 (2).

- $G_1$ is an S-graph and $G_2$ is a P-graph: "$\subseteq$" Let $(S, Q) \in h_\Gamma(G_1 \circ^{SP} G_2)$ and assume that $Q \neq \perp$ (the case $Q = \perp$ is similar). By Definition 22 (2), there exists a derivation $S \stackrel{a}{\Rightarrow}_\Gamma v \circ Q$, where $v$ is a ground term such that $G_1 \circ^{SP} G_2 = v^{SP}$. By Lemma 26, there exist derivations $S \stackrel{a}{\Rightarrow}_\Gamma^* v_1 \circ S_1$ and $S_1 \stackrel{a}{\Rightarrow}_\Gamma^* v_2 \circ Q$, for some $S_1 \in S$, such that $v_i^{SP} = G_i$, for $i = 1, 2$. Since $G_1$ is an S-graph, by Definition 22 (2), we obtain $(S, S_1) \in h_\Gamma(G_1)$. Then, by Lemma 25, and because $G_2$ is $\circ$-atomic, there is a rule $S_1 \to P \circ Q$ and a complete derivations $P \Rightarrow_\Gamma^* v_2$ for some non-terminal $P \in P$. By a reordering, if necessary, we assume the latter derivation to have the form:

$$P \Rightarrow_{\Gamma}^{*} \|_{S \in S} S^{\sharp m(S)} \Rightarrow_{\Gamma}^{*} \|_{S \in S, i \in [1, m(S)]} v_2(S, i)$$

for some multiset $m \in \text{mpow}(S)$, where $v_2(S, i)$ are ground terms and $G_2 = (\|_{S \in S, i \in [1, m(S)]} v_2(S, i))^{SP}$. Then, $m$ is a view of $G_2$ for $\Gamma$ such that $P \rightsquigarrow \Gamma m$. By Lemma 18, we obtain $P \rightsquigarrow \Gamma [m]_\Gamma \in h_\Gamma(G_2)$. Thus, we obtain $(S, Q) \in h_\Gamma(G_1) \circ^{A\Gamma} h_\Gamma(G_2)$, by an application of the inference rule $(S \circ^1 P)$ from Figure 12.

"$\supseteq$" Let $(S, Q) \in h_\Gamma(G_1) \circ^{A\Gamma} h_\Gamma(G_2)$ and assume that $Q \neq \perp$ (the case $Q = \perp$ is similar). Since $h_\Gamma(G_1)$ is an S-profile and $h_\Gamma(G_2)$ is a P-profile, by the inference rule $(S \circ^1 P)$ from Figure 12, there exist $(S, S_1) \in h_\Gamma(G_1)$, a rule $S_1 \to P \circ Q$ in $\Gamma$ and a reduced view $m \in h_\Gamma(G_2)$ such that $P \rightsquigarrow \Gamma m$. Then, there exists a view $m'$ of $G_2$, such that $[m']_\Gamma = m$, and a derivation

$$P \Rightarrow_{\Gamma}^{*} \|_{S \in S} S^{\sharp m'(S)} \Rightarrow_{\Gamma}^{*} v_2,$$

for some ground term $v_2$, such that $G_2 = v_2^{SP}$. Then, we obtain $P \rightsquigarrow \Gamma m'$, by Lemma 18. Moreover, there exists a derivation $S \stackrel{a}{\Rightarrow}_\Gamma^* v_1 \circ S_1$, where $v_1$ is a ground term such that $G_1 = v_1^{SP}$. By Lemma 26, there exists a derivation $S \stackrel{a}{\Rightarrow}_\Gamma^* v \circ Q$ such that $v^{SP} = G_1 \circ^{SP} G_2$. Thus, we obtain $(S, Q) \in h_\Gamma(G_1 \circ^{SP} G_2)$, by Definition 22 (2).

- $G_1$ and $G_2$ are S-graphs: "$\subseteq$" Let $(S, Q) \in h_\Gamma(G_1 \circ^{SP} G_2)$ and assume that $Q \neq \perp$ (the case $Q = \perp$ is similar). By Definition 22 (2), there exists a derivation $S \stackrel{a}{\Rightarrow}_\Gamma v \circ Q$, where $v$ is a ground term such that $G_1 \circ^{SP} G_2 = v^{SP}$. By Lemma 26, there exist derivations $S \stackrel{a}{\Rightarrow}_\Gamma^* v_1 \circ S_1$ and $S_1 \stackrel{a}{\Rightarrow}_\Gamma^* v_2 \circ Q$, where $S_1 \in S$ and $v_i$ are ground terms such that $G_i = v_i^{SP}$, for $i = 1, 2$. Hence, we obtain $(S, S_1) \in h_\Gamma(G_1)$ and $(S_1, Q) \in h_\Gamma(G_2)$, by Definition 22 (2). Thus, $(S, Q) \in h_\Gamma(G_1) \circ^{A\Gamma} h_\Gamma(G_2)$, by applying the inference rule $(S \circ S)$ from Figure 12.

"$\supseteq$" Let $(S, Q) \in h_\Gamma(G_1) \circ^{A\Gamma} h_\Gamma(G_2)$ and assume that $Q \neq \perp$ (the case $Q = \perp$ is similar). Since both $h_\Gamma(G_i)$

are S-profiles, by the inference rule $(S \circ S)$ from Figure 12, there exist $(S, S_1) \in h_\Gamma(G_1)$ and $(S_1, Q) \in h_\Gamma(G_2)$. By Definition 22 (2), there exist derivations $S \stackrel{a}{\Rightarrow}_\Gamma^* v_1 \circ S_1$ and $S_1 \stackrel{a}{\Rightarrow}_\Gamma^* v_2 \circ Q$, where $v_i$ are ground terms such that $G_i = v_i^{SP}$, for $i = 1, 2$. By Lemma 26, we obtain a derivation $S \stackrel{a}{\Rightarrow}_\Gamma^* v \circ Q$ such that $v^{SP} = G_1 \circ^{SP} G_2$, hence $(S, Q) \in h_\Gamma(G_1 \circ^{SP} G_2)$, by Definition 22 (2). □

Furthermore, Lemma 7 carries over from the class of trees, because the idempotent power idem$(a)$ of each S-profile $a$ has the aperiodic property idem$(a) \|^{A\Gamma} a = \text{idem}(a)$, by the definition of $\|^{A\Gamma}$ for S-profiles.

The main result of this subsection is the "if" direction of Theorem 3 for the class of series-parallel graphs (note that we do not require the grammar to be normalized). A similar result holds for disoriented series-parallel graphs

**Theorem 13:** The language of each (aperiodic) regular series-parallel grammar $\Gamma$ is recognizable by an (aperiodic) recognizer $(A, B)$. Moreover, $\text{card}(A) \in 2^{2^{\text{poly}(\text{size}(\Gamma))}}$ and $f^A(a_1, \dots, a_{\#f})$ can be computed in time $2^{\text{poly}(\text{size}(\Gamma))}$, for each function symbol $f \in \mathcal{F}^{SP}$ and elements $a_1, \dots, a_n \in A$. *Proof.* Let $\Gamma = (S \uplus P, \mathcal{R})$ be a regular (aperiodic) series-parallel grammar. Using Lemma 1, we obtain a normalized (aperiodic) grammar $\Gamma' = (S \uplus P, \mathcal{R}')$. We point out that $\Gamma$ and $\Gamma'$ have the same set of nonterminals. In particular, we have $\mathcal{L}^{SP}(\Gamma') = \mathcal{L}^{SP}(\Gamma)$ and $\text{size}(\Gamma') \in 2^{\text{poly}(\text{card}(S) + \text{card}(P)) \cdot \log(\text{size}(\Gamma))}$. We then consider the corresponding normalized regular grammar in alternative form $\hat{\Gamma}' = (\hat{S} \uplus P, \hat{\mathcal{R}}')$. We recall that $\mathcal{L}^{SP}(\hat{\Gamma}') = \mathcal{L}^{SP}(\Gamma')$ and $\text{size}(\Gamma') = \Theta(\text{size}(\hat{\Gamma}'))$.

We build the recognizer $(A_{\hat{\Gamma}'}, B_{\hat{\Gamma}'})$ based on the grammar $\hat{\Gamma}'$. By Lemma 28, we obtain $\mathcal{L}^{SP}(\hat{\Gamma}') = h_{\hat{\Gamma}'}^{-1}(B_{\hat{\Gamma}'})$, where $B_{\hat{\Gamma}'} \stackrel{\text{def}}{=} \{h_{\hat{\Gamma}'}(G) \mid G \in \mathcal{L}^{SP}(\hat{\Gamma}')\}$. By Lemma 29, $(A_{\hat{\Gamma}'}, B_{\hat{\Gamma}'})$ is a recognizer for $\mathcal{L}^{SP}(\hat{\Gamma}')$. Because of $\mathcal{L}^{SP}(\hat{\Gamma}') = \mathcal{L}^{SP}(\Gamma)$, $A_{\hat{\Gamma}'}$ is also a recognizer for the language of $\Gamma$. Moreover, $A_{\hat{\Gamma}'}$ is aperiodic, if $\hat{\Gamma}'$ is aperiodic, by the counterpart of Lemma 7 for $SP$. We further recall that $\hat{\Gamma}'$ is aperiodic iff $\Gamma'$ is aperiodic. The complexity upper bounds follow in the same way as in the proof of Theorem 5. □