for all $f \in \psi_L(\mathcal{O}(\Sigma^\Delta)_\uparrow)$, where

$$ \iota_{d,f}(x, x', y', y, z, t) = \neg \exists z' (U(x, x', z') \wedge z' < z) \wedge \\ \bigvee_{\substack{a \in \Sigma_{\text{call}}, b \in \Sigma_{\text{ret}}, r', r'' \in R_L \\ f = \text{left}_{r'} \circ \text{right}_{r''} \circ \psi_L(\text{ext}_{a,b})}} \left( \begin{array}{l} a(z) \wedge b(t) \wedge \\ \left( (x < z \wedge \eta_{d-1,r'}(x, z-1)) \vee F_{r'}(x, z) \right) \wedge \\ \left( (t < y \wedge \eta_{d-1,r''}(t+1, y)) \vee F_{r''}(y, t) \right) \end{array} \right) $$

with $F_s(x, z) = \begin{cases} x = z & \text{if } s = 1_{R_L} \text{ for all } \varphi_L(L)\text{-reachable } s \in R_L \text{ and} \\ \perp & \text{otherwise} \end{cases}$

$$ \zeta_{d,f}(x, x', z, t) = \exists z' \exists t' \left( U(x, x', z') \wedge z' < z \wedge \neg \exists z'' (z' < z'' < z \wedge U(x, x', z'')) \wedge z' \rightsquigarrow t' \wedge \right. \\ \left. \bigvee_{\substack{a \in \Sigma_{\text{call}}, b \in \Sigma_{\text{ret}}, r', r'' \in R_L \\ f = \text{left}_{r'} \circ \text{right}_{r''} \circ \psi_L(\text{ext}_{a,b})}} \left( a(z) \wedge b(t) \wedge \eta_{d-1,r'}(z' + 1, z - 1) \wedge \eta_{d-1,r''}(t + 1, t' - 1) \right) \right). $$

We now construct $\eta_{d,r}^\uparrow$ itself. Given $w \in \Sigma^\Delta \setminus \{\varepsilon\}$ and $i, j \in [1, |w|]$ such that $i$ is matched to $j$ in $w$, observe first that the infix $w_i \cdots w_j$ is of the form $w_i \cdots w_j = a_1vb_1 \in \Sigma^\Delta$ for some $a_1 \in \Sigma_{\text{call}}$, $b_1 \in \Sigma_{\text{ret}}$, and $v \in \Sigma^\Delta$. As above, we can directly express $\text{nd}(w_i \cdots w_j) \le d$ via the formula $\neg N_{d+1}$. Assuming this holds, towards expressing that $\varphi_L(w_i \cdots w_j) = r$, we make use of Lemma 4.16 and Lemma 4.17: for the infix $w_i \cdots w_j$ there is a nesting-maximal stair factorization

$$ w_i \cdots w_j = \text{ext}_{x_1, y_1} \circ \text{ext}_{a_1, b_1} \circ \cdots \circ \text{ext}_{x_k, y_k} \circ \text{ext}_{a_k, b_k}(u') $$

such that we have

1. $\text{nd}(x_1), \text{nd}(y_1), \dots, \text{nd}(x_k), \text{nd}(y_k) < d$; and

2. if $\varphi_L(w_i \cdots w_j) = r$, as $r$ is $\varphi_L(L)$-reachable, then $\psi_L(\text{ext}_{x_1, y_1} \circ \text{ext}_{a_1, b_1} \circ \cdots \circ \text{ext}_{x_k, y_k} \circ \text{ext}_{a_k, b_k})$ and $\varphi_L(u')$ are $\varphi_L(L)$-reachable.

By these points, we can use the formulas $\{\chi_{d,e}(x, x', y', y) \mid e \in O_L \ \varphi_L(L)\text{-reachable}\}$ to evaluate $\psi_L(\text{ext}_{x_1, y_1} \circ \text{ext}_{a_1, b_1} \circ \cdots \circ \text{ext}_{x_k, y_k} \circ \text{ext}_{a_k, b_k})$ and the formulas $\{\eta_{0,r'} \mid r' \in R_L \ \varphi_L(L)\text{-reachable}\}$ to evaluate $\varphi_L(u')$. We are now ready to give the formula $\eta_{d,r}^\uparrow$. We set

$$ \eta_{d,r}^{\uparrow}(x, y) = \neg N_{d+1}(x, y) \wedge \exists x' \exists y' \left( x \le x' < y' \le y \wedge x' \rightsquigarrow y' \wedge \right. \\ \left. \bigvee_{\substack{r' \in R_L, e \in O_L \\ e(r')=r}} \left( \chi_{d,e}(x, x', y', y) \wedge \eta_{0,r'}(x' + 1, y' - 1) \right) \right). $$

□

## 5.4 The intermediate case

The following theorem effectively characterizes the remaining case, namely those VPLs that are weakly length-synchronous but not length-synchronous and whose syntactic morphism is quasi-aperiodic: such VPLs are shown to be constant-depth equivalent to a non-empty disjoint union of
intermediate VPLs. The computability of $k,l \in \mathbb{N}$ with $k \neq l$ such that $\mathcal{L}_{k,l} \leq_{cd} L$ is subject of Section 5.4.2.

**Theorem 5.17.** If $L$ is weakly length-synchronous but not length-synchronous, and its syntactic morphism $(\varphi_L, \psi_L)$ is quasi-aperiodic, one can effectively compute vertically visibly pushdown grammars $G_1, \dots, G_m$ generating intermediate VPLs such that $L =_{cd} \bigcup_{i=1}^m L(G_i)$.

Before we give the proof of the theorem we need a bit of notation. Let $L \subseteq \Sigma^\Delta$ be a VPL that is weakly length-synchronous, not length-synchronous, and whose syntactic morphism $(\varphi_L, \psi_L)$ is quasi-aperiodic. By Proposition 5.1 one can effectively compute its syntactic Ext-algebra $(R_L, O_L)$, $(\varphi_L, \psi_L)$ and $\varphi_L(L)$ from (a given DVPA for) $L$.

For all $e \in O_L$ recall that

$$ \mathcal{U}_e = \{(u, v) \in \mathrm{Con}(\Sigma) \mid e \circ \psi_L(\mathrm{ext}_{u,v}) = e\}. $$

For all $\varphi_L(L)$-reachable $e \in O_L$ and some fresh internal letter $\# \notin \Sigma$ let

$$ M_e = \{u \# v \mid (u, v) \in \mathrm{Con}(\Sigma), \Delta(u) > 0, e \circ \psi_L(\mathrm{ext}_{u,v}) = e\}. $$

Note that since $L$ is assumed to be weakly length-synchronous, by Proposition 4.5, $\mathcal{U}_e$ is weakly length-synchronous for all $\varphi_L(L)$-reachable $e \in O_L$.

Also note that since $M_e = \bigcup \{L_f \mid f \in O_L : e \circ f = e\} \cap \{u \# v \mid uv \in \Sigma^\Delta, \Delta(u) > 0\}$, since for all languages $L_f$ one can effectively compute Ext-algebras recognizing them by Lemma 6.4, and since one can effectively computable an Ext-algebra recognizing the language $\{u \# v \mid uv \in \Sigma^\Delta, \Delta(u) > 0\}$, we obtain that one can effectively compute an Ext-algebra recognizing $M_e \subseteq \Sigma^* \# \Sigma^*$. The set $S_e = \{(k,l) \in \mathbb{N}^2 \mid \exists(u,v) \in \Sigma^k \times \Sigma^l : u \# v \in M_e\} \subseteq \mathbb{N}_{>0}^2$ is hence effectively semilinear by Lemma 6.5. Note that the word relation $\mathcal{U}_e$ is length-synchronous if, and only if, there exists some $\alpha \in \mathbb{Q}_{>0}$ such that $\frac{k}{l} = \alpha$ for all $(k,l) \in S_e$. Lemma 6.7 implies that the latter condition is decidable. As a consequence one can effectively compute the set

$$ \mathcal{Z} = \{e \in O_L \mid e \text{ is } \varphi_L(L)\text{-reachable and } \mathcal{U}_e \text{ is not length-synchronous}\}. $$

Observe that since $L$ is not length-synchronous by assumption, we have $\mathcal{Z} \neq \emptyset$ (Proposition 4.10).

Let us introduce two fresh copies $\tilde{\Sigma} = \{\tilde{\sigma} \mid \sigma \in \Sigma\}$ and $\tilde{\Sigma} = \{\bar{\sigma} \mid \sigma \in \Sigma\}$ of our alphabet $\Sigma$. Let $\tilde{\vartheta} : (\tilde{\Sigma} \cup \Sigma)^* \to \tilde{\Sigma}^*$ and $\bar{\vartheta} : (\bar{\Sigma} \cup \Sigma)^* \to \bar{\Sigma}^*$ be the (letter-to-letter and hence length-multiplying) morphisms satisfying $\tilde{\vartheta}(\sigma) = \tilde{\vartheta}(\tilde{\sigma}) = \tilde{\sigma}$ and $\bar{\vartheta}(\sigma) = \bar{\vartheta}(\bar{\sigma}) = \bar{\sigma}$ for all $\sigma \in \Sigma$. Conversely, let $\tilde{\vartheta}^{-1} : (\tilde{\Sigma} \cup \Sigma)^* \to \Sigma^*$ and $\bar{\vartheta}^{-1} : (\bar{\Sigma} \cup \Sigma)^* \to \Sigma^*$ be the morphisms satisfying $\tilde{\vartheta}^{-1}(\tilde{\sigma}) = \tilde{\vartheta}^{-1}(\sigma) = \sigma$ and $\bar{\vartheta}^{-1}(\bar{\sigma}) = \bar{\vartheta}^{-1}(\sigma) = \sigma$ for all $\sigma \in \Sigma$.

We define a new visibly pushdown alphabet $\Upsilon = \Upsilon_{\mathrm{call}} \cup \Upsilon_{\mathrm{int}} \cup \Upsilon_{\mathrm{ret}}$ where $\Upsilon_{\mathrm{call}} = \Sigma_{\mathrm{call}}$, $\Upsilon_{\mathrm{int}} = \Sigma_{\mathrm{int}} \cup \tilde{\Sigma} \cup \bar{\Sigma} \cup \{\#\}$, and $\Upsilon_{\mathrm{ret}} = \Sigma_{\mathrm{ret}}$.

For every word $u \# v \in M_e$ consider the unique factorization

$$ u \# v = \mathrm{ext}_{x_1, y_1} \circ \mathrm{ext}_{a_1, b_1} \circ \dots \circ \mathrm{ext}_{x_k, y_k} \circ \mathrm{ext}_{a_k, b_k} \circ \mathrm{ext}_{x_{k+1}, y_{k+1}} (\#) $$

where $k \geq 1$, $x_1, \dots, x_{k+1}, y_1, \dots, y_{k+1} \in \Sigma^\Delta$, $a_1, \dots, a_k \in \Sigma_{\mathrm{call}}$, and $b_1, \dots, b_k \in \Sigma_{\mathrm{ret}}$. For these we define

$$ (u \# v)^{\ddagger} = \mathrm{ext}_{\tilde{\vartheta}(x_1), \bar{\vartheta}(y_1)} \circ \mathrm{ext}_{a_1, b_1} \circ \dots \circ \mathrm{ext}_{\tilde{\vartheta}(x_k), \bar{\vartheta}(y_k)} \circ \mathrm{ext}_{a_k, b_k} \circ \mathrm{ext}_{\tilde{\vartheta}(x_{k+1}), \bar{\vartheta}(y_{k+1})} (\varepsilon) \in \Upsilon^\Delta. $$
Notably, $(u\#v)^{\ddagger}$ does not contain the letter #. Finally, for all $e \in \mathcal{Z}$ we define the language

$$N_e = \{(u\#v)^{\ddagger} \in \mathcal{Y}^* | u\#v \in M_e\} \cup \{\varepsilon\} \subseteq \mathcal{Y}^{\Delta}.$$

**Remark 5.18.** Let $n \in \mathbb{N}$ be the constant from Lemma 4.6 for $L$ and let $e \in \mathcal{Z}$. When setting $F = \varphi_L(L)$ and $(\varphi, \psi) = (\varphi_L, \psi_L)$, Lemma 4.6 states that the factorization

$$u\#v = \mathrm{ext}_{x_1, y_1} \circ \mathrm{ext}_{a_1, b_1} \circ \dots \circ \mathrm{ext}_{x_k, y_k} \circ \mathrm{ext}_{a_k, b_k} \circ \mathrm{ext}_{x_{k+1}, y_{k+1}} (\#)$$

of every word $u\#v \in M_e$ satisfies $|x_1|, \dots, |x_{k+1}|, |y_1|, \dots, |y_{k+1}| \le n$. As a consequence, for the corresponding factorization

$$(u\#v)^{\ddagger} = \mathrm{ext}_{\tilde{\vartheta}(x_1), \tilde{\vartheta}(y_1)} \circ \mathrm{ext}_{a_1, b_1} \circ \dots \circ \mathrm{ext}_{\tilde{\vartheta}(x_k), \tilde{\vartheta}(y_k)} \circ \mathrm{ext}_{a_k, b_k} \circ \mathrm{ext}_{\tilde{\vartheta}(x_{k+1}), \tilde{\vartheta}(y_{k+1})} (\varepsilon)$$

of every word $(u\#v)^{\ddagger} \in N_e \setminus \{\varepsilon\}$ we have $|\tilde{\vartheta}(x_1)|, \dots, |\tilde{\vartheta}(x_{k+1})|, |\tilde{\vartheta}(y_1)|, \dots, |\tilde{\vartheta}(y_{k+1})| \le n$.

### 5.4.1 Proof strategy

We are now ready to give the proof strategy for Theorem 5.17. The proof consists of the following steps.

1. $N_e$ is an intermediate VPL for all $e \in \mathcal{Z}$. Moreover, one can effectively compute a vertically visibly pushdown grammar $G_e$ witnessing that $N_e$ is indeed intermediate (Lemma 5.19).

2. $N_e \le_{cd} M_e$ for all $e \in \mathcal{Z}$ (Lemma 5.20).

3. $M_e \le_{cd} N_e$ for all $e \in \mathcal{Z}$ (Lemma 5.21).

4. $M_e \le_{cd} \biguplus_f \in O_L$ is $\varphi_L(L)$-reachable $L_f$ for all $e \in \mathcal{Z}$ (Lemma 5.22).

5. $L \le_{cd} \biguplus_{e \in \mathcal{Z}} M_e$ (Lemma 5.23).

Let us argue that Theorem 5.17 follows from the above steps. By Point 1 for all $e \in \mathcal{Z}$ we have that $N_e$ is an intermediate VPL, for which moreover one can effectively compute a vertically visibly pushdown grammar $G_e$ witnessing that $N_e$ is indeed intermediate. Recalling that $\mathcal{Z} \neq \emptyset$, it remains to argue that $L =_{cd} \biguplus \{N_e | e \in \mathcal{Z}\}$. Before we prove this let us recall some basics of constant-depth reductions. For this, let $K, L_1, \dots, L_n, K_1, \dots, K_n$ be languages. Firstly, observe that if $L_i \le_{cd} K_i$ for all $i \in [1, n]$, then $\biguplus_{i \in [1, n]} L_i \le_{cd} \biguplus_{i \in [1, n]} K_i$. Secondly, if $L_i \le_{cd} K$ for all $i \in [1, n]$, then $\biguplus_{i \in [1, n]} K_i \le_{cd} K$.
Hence we obtain the following sequence of reductions showing that $L =_{cd} \cup\{N_e \mid e \in \mathcal{Z}\}$.

$$
\begin{array}{l@{\qquad}l}
L &
  \begin{array}{@{}c@{\quad}c@{}}
    \text{Point 5} &
    \begin{tikzpicture}[baseline={([yshift=-1ex]current bounding box.center)}]
      \node[circle, fill, inner sep=1pt] (top) at (0,0) {};
      \node[circle, fill, inner sep=1pt] (bottom) at (0,1) {};
      \draw[thick] (top) -- (bottom);
    \end{tikzpicture} \\
    \le_{cd} &
    \begin{tikzpicture}[baseline={([yshift=-1ex]current bounding box.center)}]
      \node[circle, fill, inner sep=1pt] (top) at (0,0) {};
      \node[circle, fill, inner sep=1pt] (bottom) at (0,1) {};
      \draw[thick] (top) -- (bottom);
      \node[above] at (0.5,0.5) {$\cup$};
      \node[above] at (0.5,1.5) {$M_e$};
    \end{tikzpicture} \\
  \end{array} \\
& \\
&
  \begin{array}{@{}c@{\quad}c@{}}
    \text{Point 3} &
    \begin{tikzpicture}[baseline={([yshift=-1ex]current bounding box.center)}]
      \node[circle, fill, inner sep=1pt] (top) at (0,0) {};
      \node[circle, fill, inner sep=1pt] (bottom) at (0,1) {};
      \draw[thick] (top) -- (bottom);
      \node[above] at (0.5,0.5) {$\cup$};
      \node[above] at (0.5,1.5) {$N_e$};
    \end{tikzpicture} \\
    \le_{cd} &
    \begin{tikzpicture}[baseline={([yshift=-1ex]current bounding box.center)}]
      \node[circle, fill, inner sep=1pt] (top) at (0,0) {};
      \node[circle, fill, inner sep=1pt] (bottom) at (0,1) {};
      \draw[thick] (top) -- (bottom);
      \node[above] at (0.5,0.5) {$\cup$};
      \node[above] at (0.5,1.5) {$N_e$};
    \end{tikzpicture} \\
  \end{array} \\
& \\
&
  \begin{array}{@{}c@{\quad}c@{}}
    \text{Point 2} &
    \begin{tikzpicture}[baseline={([yshift=-1ex]current bounding box.center)}]
      \node[circle, fill, inner sep=1pt] (top) at (0,0) {};
      \node[circle, fill, inner sep=1pt] (bottom) at (0,1) {};
      \draw[thick] (top) -- (bottom);
      \node[above] at (0.5,0.5) {$\cup$};
      \node[above] at (0.5,1.5) {$M_e$};
    \end{tikzpicture} \\
    \le_{cd} &
    \begin{tikzpicture}[baseline={([yshift=-1ex]current bounding box.center)}]
      \node[circle, fill, inner sep=1pt] (top) at (0,0) {};
      \node[circle, fill, inner sep=1pt] (bottom) at (0,1) {};
      \draw[thick] (top) -- (bottom);
      \node[above] at (0.5,0.5) {$\cup$};
      \node[above] at (0.5,1.5) {$M_e$};
    \end{tikzpicture} \\
  \end{array} \\
& \\
&
  \begin{array}{@{}c@{\quad}c@{}}
    \text{Point 4} &
    \begin{tikzpicture}[baseline={([yshift=-1ex]current bounding box.center)}]
      \node[circle, fill, inner sep=1pt] (top) at (0,0) {};
      \node[circle, fill, inner sep=1pt] (bottom) at (0,1) {};
      \draw[thick] (top) -- (bottom);
      \node[above] at (0.5,0.5) {$\cup$};
      \node[above] at (0.5,1.5) {$L_f$};
    \end{tikzpicture} \\
    \le_{cd} &
    \begin{tikzpicture}[baseline={([yshift=-1ex]current bounding box.center)}]
      \node[circle, fill, inner sep=1pt] (top) at (0,0) {};
      \node[circle, fill, inner sep=1pt] (bottom) at (0,1) {};
      \draw[thick] (top) -- (bottom);
      \node[above] at (0.5,0.5) {$\cup$};
      \node[above] at (0.5,1.5) {$f \in O_L$ is $\varphi_L(L)$-reachable$^*$};
    \end{tikzpicture} \\
  \end{array} \\
&
  \begin{array}{@{}c@{\quad}c@{}}
    \text{Lemma 5.3} &
    L \\
    \le_{cd} &
    L.
  \end{array}
\end{array}
$$

**Lemma 5.19.** $N_e$ is an intermediate language for all $e \in \mathcal{Z}$. Moreover, one can effectively compute a vertically visibly pushdown grammar witnessing that $N_e$ is indeed an intermediate VPL.

*Proof.* Let $e \in \mathcal{Z}$. For showing that $N_e$ is an intermediate VPL we first show that $N_e$ is quasi-counterfree. To this end we show that $(\varphi_{N_e}, \psi_{N_e})$ of $N_e$ is quasi-aperiodic, which is equivalent by Proposition 4.18.

Assume by contradiction that $(\varphi_{N_e}, \psi_{N_e})$ is not quasi-aperiodic. Then there exist $k, l \in \mathbb{N}$ such that $\psi_{N_e}(\mathcal{O}(\Upsilon^\Delta)^{k,l})$ contains a non-trivial group, say $G \subseteq O_{N_e}$. Let $g_0$ be the identity of $G$ and let $g_1 \in G$ be such that $g_1 \neq g_0$. Thus, we have $g_1^{i+1} \neq g_1^i$ for all $\mathbb{N}_{>0}$. We claim that all $g \in G$ are $\varphi_{N_e}(N_e)$ reachable: indeed, if $g \in G$ were not $\varphi_{N_e}(N_e)$-reachable, then the same would hold for all $g' \in G$ since $g' = g'g^{-1}g$, hence implying that $g'$ is the (one and only) zero of $O_{N_e}$, contradicting that $G$ is non-trivial. Fix some $\mathrm{ext}_{u_0,v_0}, \mathrm{ext}_{u_1,v_1} \in \mathcal{O}(\Upsilon^\Delta)^{k,l}$ such that $\psi_{N_e}(\mathrm{ext}_{u_0,v_0}) = g_0$ and $\psi_{N_e}(\mathrm{ext}_{u_1,v_1}) = g_1$. Note that we must have $k > 0$ or $l > 0$ for otherwise we would have $u_0 = u_1 = \varepsilon$ and $v_0 = v_1 = \varepsilon$, a contradiction to $g_0 \neq g_1$. We moreover claim that $u_0, u_1 \notin \tilde{\Sigma}^*$ and hence $v_0, v_1 \notin \tilde{\Sigma}^*$: indeed, a consequence of Remark 5.18 is that $\mathrm{ext}_{u,v} \in \psi_{N_e}^{-1}(f) \cap \tilde{\Sigma}^s \times \tilde{\Sigma}^l$ implies $s, t \le n$ for all $\varphi_{N_e}(N_e)$-reachable $f \in O_{N_e}$, yet the fact that $\psi_{N_e}(\mathrm{ext}_{u^i,v^i})$ is in $G$ and thus $\varphi_{N_e}(N_e)$-reachable for all $i \ge 1$ contradicts this (recall that $|u_1| > 0$ or $|v_1| > 0$). In other words, both $u_0$ and $u_1$ contain at least one letter from $\Sigma_{\mathrm{call}}$ and both $v_0$ and $v_1$ contain a letter from $\Sigma_{\mathrm{ret}}$.

Next we claim that neither $u_0$ nor $u_1$ contain any letter from $\Sigma_{\mathrm{ret}}$: indeed, without loss of generality if $u_1$ were to contain a letter from $\Sigma_{\mathrm{ret}}$ then $\psi_{N_e}(\mathrm{ext}_{u_1^2,v_1^2})$ would be the zero of $O_{N_e}$, contradicting that $\psi_{N_e}(\mathrm{ext}_{u_1^2,v_1^2})$ is in $G$. It follows that $u_0, u_1 \in (\tilde{\Sigma}^*\Sigma_{\mathrm{call}}\tilde{\Sigma}^*)^+$ and hence that $v_0, v_1 \in (\tilde{\Sigma}^*\Sigma_{\mathrm{ret}}\tilde{\Sigma}^*)^+$.

Let $u'_0 = \tilde{\vartheta}^{-1}(u_0)$, $u'_1 = \tilde{\vartheta}^{-1}(u_1)$, $v'_0 = \tilde{\vartheta}^{-1}(v_0)$, $v'_1 = \tilde{\vartheta}^{-1}(v_1)$ and note that $\mathrm{ext}_{u'_0,v'_0}, \mathrm{ext}_{u'_1,v'_1} \in \mathcal{O}(\Sigma^{k,l})$. Since $\mathfrak{P}(O_L)$ forms a monoid there exists $p \in \mathbb{N}_{>0}$ such that

$$ \psi_L(\{\mathrm{ext}_{u'_0, v'_0}, \mathrm{ext}_{u'_1, v'_1}\})^p = \psi_L(\{\mathrm{ext}_{u'_0, v'_0}, \mathrm{ext}_{u'_1, v'_1}\})^{2p}. $$

This implies that for all $i \in \mathbb{N}_{>0}$, we have

$$ \psi_L(\mathrm{ext}_{u'_0^{p-1}, u'_1, v'_0^{p-1}})^i \in \psi_L(\{\mathrm{ext}_{u'_0, v'_0}, \mathrm{ext}_{u'_1, v'_1}\})^{ip} = \psi_L(\{\mathrm{ext}_{u'_0, v'_0}, \mathrm{ext}_{u'_1, v'_1}\})^p. $$

Hence, as $|u_0| = |u_1| = |u'_0| = |u'_1| = k$ and $|v_0| = |v_1| = |v'_0| = |v'_1| = l$, the semigroup
$\{\psi_L(\mathrm{ext}_{u_0^{p-1} u_1, v_1 v_0^{p-1}})^i | i \in \mathbb{N}_{>0}\}$ is contained in $\psi_L(\mathcal{O}(\Sigma^\Delta)^{kp,lp})$. We show that the latter semi-group is not aperiodic by showing $\psi_L(\mathrm{ext}_{u_0^{p-1} u_1, v_1 v_0^{p-1}})^i \neq \psi_L(\mathrm{ext}_{u_0^{p-1} u_1, v_1 v_0^{p-1}})^{i+1}$ for all $i \in \mathbb{N}_{>0}$. Indeed, since

$$ \psi_{N_e} \left( \left( \mathrm{ext}_{u_0^{p-1} u_1, v_1 v_0^{p-1}} \right)^{i+1} \right) = g_1^{i+1} \neq g_1^{i+2} = \psi_{N_e} \left( \left( \mathrm{ext}_{u_0^{p-1} u_1, v_1 v_0^{p-1}} \right)^{i+2} \right) $$

there exist $\mathrm{ext}_{x,y} \in \mathcal{O}(\Upsilon^\Delta)$ and $w \in \Upsilon^\Delta$ such that, without loss of generality

$$ \left( \mathrm{ext}_{x,y} \circ \left( \mathrm{ext}_{u_0^{p-1} u_1, v_1 v_0^{p-1}} \right)^{i+1} \right) (w) \in N_e \quad \text{and} \quad \left( \mathrm{ext}_{x,y} \circ \left( \mathrm{ext}_{u_0^{p-1} u_1, v_1 v_0^{p-1}} \right)^{i+2} \right) (w) \not\in N_e. $$

Now since $u_0, u_1 \in (\tilde{\Sigma}^*\Sigma_{\mathrm{call}}\tilde{\Sigma}^*)^+$ there exists a factorization $u_0^{p-1} u_1 w v_1 v_0^{p-1} = x'y'$ such that

$$ \left( \mathrm{ext}_{\tilde{\vartheta}^{-1}(x), \bar{\vartheta}^{-1}(y)} \circ \left( \mathrm{ext}_{\tilde{\vartheta}^{-1}(u_0^{p-1} u_1), \bar{\vartheta}^{-1}(v_1 v_0^{p-1})} \right)^i \right) (\tilde{\vartheta}^{-1}(x') \# \bar{\vartheta}^{-1}(y')) \in M_e $$

and

$$ \left( \mathrm{ext}_{\tilde{\vartheta}^{-1}(x), \bar{\vartheta}^{-1}(y)} \circ \left( \mathrm{ext}_{\tilde{\vartheta}^{-1}(u_0^{p-1} u_1), \bar{\vartheta}^{-1}(v_1 v_0^{p-1})} \right)^{i+1} \right) (\tilde{\vartheta}^{-1}(x') \# \bar{\vartheta}^{-1}(y')) \notin M_e $$

By definition of $M_e$ we obtain

$$ \begin{aligned} e &= e \circ \psi_L \left( \mathrm{ext}_{\tilde{\vartheta}^{-1}(x(u_0^{p-1} u_1)^i x'), \bar{\vartheta}^{-1}(y'(v_1 v_0^{p-1})^i y')} \right) \\ &= e \circ \psi_L \left( \mathrm{ext}_{\tilde{\vartheta}^{-1}(x), \bar{\vartheta}^{-1}(y)} \right) \circ \psi_L \left( \mathrm{ext}_{\tilde{\vartheta}^{-1}(u_0^{p-1} u_1), \bar{\vartheta}^{-1}(v_1 v_0^{p-1})} \right)^i \circ \psi_L \left( \mathrm{ext}_{\tilde{\vartheta}^{-1}(x'), \bar{\vartheta}^{-1}(y')} \right) \end{aligned} $$

and

$$ \begin{aligned} e &\neq e \circ \psi_L \left( \mathrm{ext}_{\tilde{\vartheta}^{-1}(x(u_0^{p-1} u_1)^{i+1} x'), \bar{\vartheta}^{-1}(y'(v_1 v_0^{p-1})^{i+1} y')} \right) \\ &= e \circ \psi_L \left( \mathrm{ext}_{\tilde{\vartheta}^{-1}(x), \bar{\vartheta}^{-1}(y)} \right) \circ \psi_L \left( \mathrm{ext}_{\tilde{\vartheta}^{-1}(u_0^{p-1} u_1), \bar{\vartheta}^{-1}(v_1 v_0^{p-1})} \right)^{i+1} \circ \psi_L \left( \mathrm{ext}_{\tilde{\vartheta}^{-1}(x'), \bar{\vartheta}^{-1}(y')} \right). \end{aligned} $$

Thus, we must have $\psi_L(\mathrm{ext}_{u_0^{p-1} u_1, v_1 v_0^{p-1}})^i \neq \psi_L(\mathrm{ext}_{u_0^{p-1} u_1, v_1 v_0^{p-1}})^{i+1}$, as required. As this is true for each $i \in \mathbb{N}_{>0}$, the semigroup $\{\psi_L(\mathrm{ext}_{u_0^{p-1} u_1, v_1 v_0^{p-1}})^i | i \in \mathbb{N}_{>0}\}$ that is contained in $\psi_L(\mathcal{O}(\Sigma^\Delta)^{kp,lp})$ is not aperiodic, contradicting quasi-aperiodicity of $(\varphi_L, \psi_L)$.

It remains to show that one can compute a vertically visibly pushdown grammar $G_e$ with $L(G_e) = N_e$ such that $\mathcal{R}(G_e)$ is weakly length-synchronous but not length-synchronous. By Remark 5.18 each non-empty word in $N_e$ is of the form

$$ (u \# v)^{\ddagger} = \mathrm{ext}_{\tilde{\vartheta}(x_1), \bar{\vartheta}(y_1)} \circ \mathrm{ext}_{a_1, b_1} \circ \cdots \circ \mathrm{ext}_{\tilde{\vartheta}(x_k), \bar{\vartheta}(y_k)} \circ \mathrm{ext}_{a_k, b_k} \circ \mathrm{ext}_{\tilde{\vartheta}(x_{k+1}), \bar{\vartheta}(y_{k+1})} (\varepsilon) $$

for some $k \ge 1$ and some words $x_1, \dots, x_{k+1}, y_1, \dots, y_{k+1} \in \Sigma^\Delta$ all of which have length at most $n$ such that moreover $e \circ \psi_L(\mathrm{ext}_{u,v}) = e$. We construct the grammar $G_e = (V, \Upsilon, P, S_e)$ as follows. The set of nonterminals is $V = \{S_f | f \in O_L\}$, $S_e \in V$ is the start nonterminal, the set of productions
consists of the union of {$S_e \to_{G_e} \varepsilon$} and

$$
\left\{
\begin{array}{l}
S_f \to_{G_e} \tilde{\vartheta}(x_1) a \tilde{\vartheta}(x_2) S_g \bar{\vartheta}(y_2) b \bar{\vartheta}(y_1) \quad | \quad f, g \in O_L, x_1, x_2, y_1, y_2 \in \Sigma^\Delta, |x_1|, |x_2|, |y_1|, |y_2| \le n, \\
\qquad a \in \Sigma_{\text{call}}, b \in \Sigma_{\text{ret}}, f \circ \psi_L(\text{ext}_{x_1 a x_2, y_2 b y_1}) = g
\end{array}
\right\} .
$$

As a consequence we obtain

$$
\begin{align*}
\mathcal{R}(G_e) &= \left\{ \left( \tilde{\vartheta}(x_1) \dots a_k \tilde{\vartheta}(x_{k+1}), \bar{\vartheta}(y_{k+1}) b_k \dots \bar{\vartheta}(y_1) \right) \middle| \begin{array}{@{}l@{}} x_1, \dots, x_{k+1}, x_1, \dots, y_{k+1} \in \Sigma^\Delta, \\ a_1, \dots, a_k \in \Sigma_{\text{call}}, b_1, \dots, b_k \in \Sigma_{\text{ret}}, \\ e \circ \psi_L(\text{ext}_{a_1 \dots a_k x_{k+1}, y_{k+1} b_k \dots y_1}) = e \end{array} \right\} \\
&= \left\{ \left( \tilde{\vartheta}(x_1) \dots a_k \tilde{\vartheta}(x_{k+1}), \bar{\vartheta}(y_{k+1}) b_k \dots \bar{\vartheta}(y_1) \right) \middle| \begin{array}{@{}l@{}} x_1, \dots, x_{k+1}, x_1, \dots, y_{k+1} \in \Sigma^\Delta, \\ a_1, \dots, a_k \in \Sigma_{\text{call}}, b_1, \dots, b_k \in \Sigma_{\text{ret}}, \\ (x_1 \dots a_k x_{k+1}, y_{k+1} b_k \dots y_1) \in \mathcal{U}_e \end{array} \right\}.
\end{align*}
$$

It follows that $\mathcal{R}(G_e)$ is weakly length-synchronous since $\mathcal{U}_e$ is: indeed, if $\mathcal{R}(G_e)$ were not weakly length-synchronous and without loss of generality there were to exist $(u, v)$, $(u', v') \in \mathcal{R}(G_e)$ with $u = u'$ and $|v| \neq |v'|$, then both $(\tilde{\vartheta}^{-1}(u), \bar{\vartheta}^{-1}(v))$ and $(\tilde{\vartheta}^{-1}(u'), \bar{\vartheta}^{-1}(v'))$ would be in $\mathcal{U}_e$ by definition. Yet $\tilde{\vartheta}^{-1}(u) = \tilde{\vartheta}^{-1}(u')$ and $|\bar{\vartheta}^{-1}(v)| = |v| \neq |v'| = |\bar{\vartheta}^{-1}(v')|$, so this would contradict that $\mathcal{U}_e$ is indeed weakly length-synchronous. Analogously it follows that $\mathcal{R}(G_e)$ is not length-synchronous since $\mathcal{U}_e$ is not length-synchronous by assumption. $\square$

**Lemma 5.20.** $N_e \le_{cd} M_e$ for all $e \in \mathcal{Z}$.

*Proof.* Assume we are given $w \in \Upsilon^*$. To decide if $w \in N_e$ using an oracle to $M_e$ we do the following constant-depth computation:

1. Accept if $w = \varepsilon$, otherwise continue.

2. Check if $w = uv$ for some $u \in (\tilde{\Sigma} \cup \Sigma_{\text{call}})^*$ and some $v \in (\bar{\Sigma} \cup \Sigma_{\text{ret}})^*$, reject if this is not the case.

3. Check whether $u$ can be factorized as $u = x_1 a_1 \cdots x_k a_k x_{k+1}$, where $k \ge 1$, $x_1, \dots, x_{k+1} \in \{x \in \tilde{\Sigma}^* \mid |x| \le n \wedge \tilde{\vartheta}^{-1}(x) \in \Sigma^\Delta\}$ and $a_1, \dots, a_k \in \Sigma_{\text{call}}$ and whether $v$ can be factorized as $v = y_{l+1} b_l y_l \cdots a_1 y_1$, where $l \ge 1$, $y_1, \dots, y_{l+1} \in \{y \in \bar{\Sigma}^* \mid |y| \le n \wedge \bar{\vartheta}^{-1}(y) \in \Sigma^\Delta\}$ and $b_1, \dots, b_l \in \Sigma_{\text{ret}}$. Reject if it is not possible. (Observe that this is doable by a constant depth and polynomial size circuit family since we test membership in finite sets that do not depend on the input.)

4. Finally accept if, and only if, the word

$$
\tilde{\vartheta}^{-1}(x_1) a_1 \cdots \tilde{\vartheta}^{-1}(x_{k-1}) a_k \tilde{\vartheta}^{-1}(x_{k+1}) \# \bar{\vartheta}^{-1}(y_{l+1}) b_l \bar{\vartheta}^{-1}(y_{l+1}) \cdots b_1 \bar{\vartheta}^{-1}(y_1)
$$

is in $M_e$.
**Lemma 5.21.** $M_e \le N_e$ for all $e \in \mathbb{Z}$.

*Proof.* Assume we are given $w \in (\Sigma \cup \{\#\})^*$, where $w = w_1 \cdots w_m$ and where $w_i \in \Sigma \cup \{\#\}$ for all $i \in [1, m]$. To decide if $w \in M_e$ using an oracle to $N_e$ we do the following constant-depth computation:

1. Check if $w = u\#v$ for some $u \in \Sigma^+$ and some $v \in \Sigma^+$, reject otherwise.

2. For all return letters $b \in \Sigma_{\text{ret}}$ and all positions $j$ within $u$ at which $b$ appears, check whether there exists a position $i$ within $u$ such that $1 \le j - i \le n - 1$ and the infix $w_i \cdots w_j$ is in $\Sigma^\Delta$. (As above, this is doable by a constant depth and polynomial size circuit family since we check well-matchedness of at most a fixed number of words that does not depend on the input.) Reject if it is not the case.

3. For all call letters $a \in \Sigma_{\text{call}}$ and all positions $i$ within $v$ at which $a$ appears, check whether there exists a position $j$ within $v$ such that $1 \le j - i \le n - 1$ and the infix $w_i \cdots w_j$ is in $\Sigma^\Delta$. Reject if it is not the case.

4. For each position $i$ within $u$, compute $P_{\text{call}}(i)$ where $P_{\text{call}}$ is the unary predicate defined by $w \models P_{\text{call}}(i)$ if, and only if, $i$ is a position within $u$, $w_i \in \Sigma_{\text{call}}$, and there does not exist any position $j$ within $u$ such that $1 \le j - i \le n - 1$ and the infix $w_i \cdots w_j$ is in $\Sigma^\Delta$.

5. For each position $j$ within $v$, compute $P_{\text{ret}}(j)$ where $P_{\text{ret}}$ is the unary predicate defined by $w \models P_{\text{ret}}(j)$ if, and only if, $j$ is a position within $v$, $w_j \in \Sigma_{\text{ret}}$, and there does not exist any position $i$ within $v$ such that $1 \le j - i \le n - 1$ and the infix $w_i \cdots w_j$ is in $\Sigma^\Delta$.

6. Let $1 \le i_1 < i_2 \cdots < i_k \le |u|$ be an enumeration of $\{i \in [1, |u|] \mid w \models P_{\text{call}}(i)\}$ and let $|u| + 2 \le j_1 < j_{l-1} \cdots < j_l \le m$ be an enumeration of $\{j \in [|u| + 2, m] \mid w \models P_{\text{ret}}(j)\}$. Build

$$u' = \tilde{\vartheta}(w_1 \cdots w_{i_1-1})w_{i_1} \cdots \tilde{\vartheta}(w_{i_{k-1}+1} \cdots w_{i_k-1})w_{i_k} \tilde{\vartheta}(w_{i_{k+1}+1} \cdots w_{|u|})$$

and

$$v' = \bar{\vartheta}(w_{|u|+2} \cdots w_{j_{l+1}-1})w_{j_l} \cdots \bar{\vartheta}(w_{j_2} + 1 \cdots w_{j_{l-1}})w_{j_1} \bar{\vartheta}(w_{j_1} + 1 \cdots w_m).$$

7. Accept if, and only if, the word $u'v'$ is in $N_e$. $\square$

**Lemma 5.22.** $M_e \le_{cd} \bigsqcup_{f \in O_L} \varphi_L(L)$-reachable $L_f$ for all $e \in \mathbb{Z}$.

*Proof.* Note that the following equivalence holds:

$$u\#v \in M_e \iff \exists f \in O_L \text{ that is } \varphi_L(L)\text{-reachable} : e \circ f = e \wedge u\#v \in L_f \wedge \Delta(u) > 0.$$

This holds because for $\text{ext}_{u,v} \in \mathcal{O}(\Sigma^\Delta)$ satisfying $e \circ \psi_L(\text{ext}_{u,v}) = e$, as $e$ is $\varphi_L(L)$-reachable, $\psi_L(\text{ext}_{u,v})$ must also be $\varphi_L(L)$-reachable. Assume we are given $w \in (\Sigma \cup \{\#\})^*$. To decide if $w \in M_e$ we do the following constant-depth computation using oracles to $\bigsqcup_{f \in O_L}$ is $\varphi_L(L)$-reachable $L_f$:

1. Check if $w = u\#v$ for some $u, v \in \Sigma^*$, reject otherwise.

2. Check if $u\#v \in L_f$ for some $\varphi_L(L)$-reachable $f \in O_L$ satisfying $e \circ f = e$, reject otherwise.

3. Finally, accept if, and only if for all $\varphi_L(L)$-reachable $f \in O_L$ we have $u\# \notin L_f$.

If the second check is successful, then $\psi_L(\text{ext}_{u,v})$ is necessarily $\varphi_L(L)$-reachable, so in that case when $\Delta(u) = 0$ it holds that $u \in \Sigma^\Delta$ and $\psi_L(\text{ext}_{u,\varepsilon})$ is $\varphi_L(L)$-reachable. Hence, in combination with the second check, the third check is successful if, and only if $\Delta(u) > 0$. $\square$
**Lemma 5.23.** $L \leq_{cd} \biguplus_{e \in \mathcal{Z}} M_e$.

*Proof.* By assumption $L$ is weakly length-synchronous but not length-synchronous, and its syntactic morphism $(\varphi_L, \psi_L)$ is quasi-aperiodic. There is a constant $d_L$ such that all words in $L$ have nesting depth at most $d_L$ by Proposition 4.14.

By the first point of Proposition 5.10 we may assume that the evaluation language $\mathcal{E}_{\varphi_L, r}$ is regular and its syntactic morphism is quasi-aperiodic for all $\varphi_L(L)$-reachable $r \in R_L$. This implies, by [29, Theorem VI.4.1], that for each $\varphi_L(L)$-reachable $r \in R_L$, there exists an $\text{FO}_{\Gamma_{\varphi_L}}[<, \text{MOD}]$-sentence $\nu_{\varphi_L, r}$ defining $\mathcal{E}_{\varphi_L, r}$.

As $L$ is not length-synchronous we cannot assume analogous sentences for the evaluation languages $\mathcal{E}_{\psi_L, e}$ for all $\varphi_L(L)$-reachable $e \in O_L$. Indeed, Remark 5.11 provides an example of a weakly length-synchronous but non-length-synchronous VPL whose syntactic morphism is quasi-aperiodic but for which some evaluation language $\mathcal{E}_{\psi_L, e}$ for $e \in O_L$ that is $\varphi_L(L)$-reachable has a non-quasi-aperiodic syntactic morphism.

However, let $e \in O_L$ be such that $\mathcal{R}_e = \{(u, v) \in \text{Con}(\Sigma) \mid \psi_L(\text{ext}_{u,v}) = e\}$ is length-synchronous. Take any $\varphi_L(L)$-reachable idempotent $f \in O_L$ such that there exist $g, h \in O_L$ satisfying $e = g \circ f \circ h$. There exist $\text{ext}_{x_g, y_g}, \text{ext}_{x_h, y_h} \in \mathcal{O}(\Sigma^\Delta)$ such that $\psi_L(\text{ext}_{x_g, y_g}) = g$ and $\psi_L(\text{ext}_{x_h, y_h}) = h$. Let $(u, v), (u', v') \in \text{Con}(\Sigma)$ such that $\Delta(u), \Delta(u') > 0$ and $\psi_L(\text{ext}_{u,v}) = \psi_L(\text{ext}_{u',v'}) = f$. Because $f$ is idempotent, we have that $\psi_L(\text{ext}_{u|v',|v|}) = \psi_L(\text{ext}_{u'|v',|v|}) = f$, thus $\psi_L(\text{ext}_{x_g u|v'|x_h, y_h v'|y_g}) = \psi_L(\text{ext}_{x_g u|v'|x_h, y_h v'|y_g}) = e$. Therefore, because of length-synchronicity of $\mathcal{R}_e$, it follows that

$$ 
\begin{aligned}
\frac{|x_g u^{v'|} x_h|}{|y_h v^{v'|} y_g|} &= \frac{|x_g u'|^v x_h|}{|y_h v'|^v y_g|} \\
\frac{|x_g| + |v'| \cdot |u| + |x_h|}{|y_h| + |v'| \cdot |v| + |y_g|} &= \frac{|x_g| + |v| \cdot |u'| + |x_h|}{|y_h| + |v| \cdot |v'| + |y_g|} \\
|v'| \cdot |u| &= |v| \cdot |u'| \\
\frac{|u|}{|v|} &= \frac{|u'|}{|v'|}.
\end{aligned}
$$

So we can conclude that $\mathcal{R}_f = \{(u, v) \in \text{Con}(\Sigma) \mid \psi_L(\text{ext}_{u,v}) = f\}$ is length-synchronous. Thus, by the second point of Proposition 5.10 we may assume that the evaluation language $\mathcal{E}_{\psi_L, e}$ is regular and its syntactic morphism is quasi-aperiodic for all $\varphi_L(L)$-reachable $e \in O_L$ with $\mathcal{R}_e$ length-synchronous. This implies again, by [29, Theorem VI.4.1], that for each $\varphi_L(L)$-reachable $e \in O_L$ with $\mathcal{R}_e$ length-synchronous, there exists an $\text{FO}_{\Gamma_{\psi_L}}[<, \text{MOD}]$-sentence $\nu_{\psi_L, e}$ defining $\mathcal{E}_{\psi_L, e}$.

For proving $L \leq_{cd} \biguplus_{e \in \mathcal{Z}} M_e$ we must thus make use of the oracles to $\biguplus_{e \in \mathcal{Z}} M_e$. All of the following predicates can be computed by a circuit family of constant depth and polynomial size with access to these oracles. More concretely, by accessing oracles to $\biguplus_{e \in \mathcal{Z}} M_e$, for all $e \in \mathcal{Z}$ we may assume that we have a predicate $\pi_e^{\text{exact}}$ such that for all $w \in \Sigma^+$ and $i, i', j', j \in [1, |w|], i \leq i' < j' \leq j$ the following holds:

$$ w \models \pi_e^{\text{exact}}(i, i', j', j) \iff \begin{aligned}[t] & w_i \cdots w_{i'} w_{j'} \cdots w_j \in \Sigma^\Delta, e \circ \psi_L(\text{ext}_{w_i \cdots w_{i'}, w_{j'} \cdots w_j}) = e \text{ and } (4) \\ & \Delta(w_i \cdots w_{i'}) > 0 \end{aligned} $$

For all $\varphi_L(L)$-reachable $e \in O_L$ that are not in $\mathcal{Z}$ we may assume, by Lemma 5.13, that we have the $\text{FO}[+]$-definable (and hence constant-depth computable) predicate $\pi_e$ at hand. It has the following properties: for all $w \in \Sigma^+$ and $i, i', j', j \in [1, |w|], i \leq i' < j' \leq j$:

* if $w \models \pi_e(i, i', j', j)$, then $w_i \cdots w_{i'} w_{j'} \cdots w_j \in \Sigma^\Delta$ and
• if $w_i \cdots w_i' w_{j'} \cdots w_j \in \Sigma^\Delta$, $\Delta(w_i \cdots w_{i'}) > 0$ and $e \circ \psi_L(\mathrm{ext}_{w_i \cdots w_{i'}, w_{j'} \cdots w_j}) = e$, then $w \models \pi_e(i, i', j', j)$.

We can first build an approximate matching $\mu$ relative to $L$. This is done totally analogously as done in Section 5.3.4 by replacing the there appearing $\pi_e$ for each $e \in \mathbb{Z}$ by our predicate $\pi_e^{\text{exact}}$: indeed, Remark 5.15 states that the predicates $\pi_e$ from of Lemma 5.13 could have been replaced by the predicate $\pi_e^{\text{exact}}$.

Thus, as in the proof of Proposition 5.16 we may assume that we have full access to the matching relation $M^\Delta(w)$ of our input word $w$.

For verifying if a given word $w \in \Sigma^\Delta$ is in $L$ we follow the same approach as the main construction in Section 5.3.5. It is however important to stress that this time we cannot assume quasi-aperiodicity of the syntactic morphisms of the evaluation languages $\mathcal{E}_{\psi_L, e}$ for all $\varphi_L(L)$-reachable $e \in O_L$. Still, we build formulas

• $\bar{\eta}_{d,r}^{\uparrow}(x, y)$ for all $d \in [0, d_L]$ and all $\varphi_L(L)$-reachable $r \in R_L$ and

• $\bar{\eta}_{d,r}(x, y)$ for all $d \in [0, d_L]$ and all $\varphi_L(L)$-reachable $r \in R_L$

that will have the following properties (as $\eta_{d,r}$ and $\eta_{d,r}^{\uparrow}$) for all $w \in \Sigma^\Delta$ and all $i, j \in [1, |w|]$:

• if $i$ is matched to $j$ in $w$, then $(w, M^\Delta(w)) \models \bar{\eta}_{d,r}^{\uparrow}(i, j)$ if, and only if, $\mathrm{nd}(w_i \cdots w_j) \le d$ and $\varphi_L(w_i \cdots w_j) = r$;

• if $w_i \cdots w_j \in \Sigma^\Delta$, then $(w, M^\Delta(w)) \models \bar{\eta}_{d,r}(i, j)$ if, and only if, $\mathrm{nd}(w_i \cdots w_j) \le d$ and $\varphi_L(w_i \cdots w_j) = r$.

It remains to define the formulas $\bar{\eta}_{d,r}$ and $\bar{\eta}_{d,r}^{\uparrow}$ for all $d \in [0, d_L]$ and all $\varphi_L(L)$-reachable $r \in R_L$. For the definition of the $\bar{\eta}_{0,r}^{\uparrow}$ and the $\bar{\eta}_{0,r}$ we can simply reuse $\eta_{0,r}$ and $\eta_{0,r}^{\uparrow}$ as in the proof of Proposition 5.16 respectively ($\eta_{0,r}$ will make use of our sentence $\nu_{\varphi_L, r}$). So let us assume $d > 0$.

We first construct for all $\varphi_L(L)$-reachable $e \in O_L$ a formula $\bar{\chi}_{d,e}(x, x', y', y)$ such that for all $w \in \Sigma^\Delta$ and $i, i', j', j \in [1, |w|], i \le i' < j' \le j$ we have that if $w_i \cdots w_{i'} w_{j'} \cdots w_j \in \Sigma^\Delta$ and $i'$ is matched to $j'$ in $w$, then given

$$ \mathrm{ext}_{w_i \cdots w_{i'}, w_{j'} \cdots w_j} = \mathrm{ext}_{x_1, y_1} \circ \mathrm{ext}_{a_1, b_1} \circ \cdots \circ \mathrm{ext}_{x_k, y_k} \circ \mathrm{ext}_{a_k, b_k} $$

the stair factorization of $\mathrm{ext}_{w_i \cdots w_{i'}, w_{j'} \cdots w_j}$ provided by Lemma 3.6, we have $(w, M^\Delta(w)) \models \bar{\chi}_{d,e}(i, i', j', j)$ if, and only if, $\mathrm{nd}(x_\ell)$, $\mathrm{nd}(y_\ell) < d$ for all $\ell \in [1, k]$ and $\psi_L(\mathrm{ext}_{w_i \cdots w_{i'}, w_{j'} \cdots w_j}) = e$. Given $w, i, i', j', j$ and the associated stair factorization as above, note that if $\psi_L(\mathrm{ext}_{w_i \cdots w_{i'}, w_{j'} \cdots w_j}) = e$, as $e$ is $\varphi_L(L)$-reachable, then $\varphi_L(x_\ell)$ and $\varphi_L(y_\ell)$ are $\varphi_L(L)$-reachable for all $\ell \in [1, k]$. If additionally $\mathrm{nd}(x_\ell)$, $\mathrm{nd}(y_\ell) < d$ for all $\ell \in [1, k]$, we can inductively make use of the formulas $\{\bar{\eta}_{d-1, r'} | r' \in R_L \text{ and } \varphi_L(L) \text{ reachable}\}$ in order to evaluate $\varphi_L(x_1), \varphi_L(y_1), \dots, \varphi_L(x_k), \varphi_L(y_k)$.

As expected, the problems are, firstly, that we cannot access our evaluation languages $\mathcal{E}_{\psi_L, e}$ and, secondly, that we have to build a formula that may not depend on $k$. As in Section 5.3.4 we define the product

$$ e_{\ell, \ell'} = \psi_L(\mathrm{ext}_{x_\ell, y_\ell} \circ \mathrm{ext}_{a_\ell, b_\ell} \circ \cdots \circ \mathrm{ext}_{x_{\ell'}, y_{\ell'}} \circ \mathrm{ext}_{a_{\ell'}, b_{\ell'}}) \quad \text{and} \quad e_\ell = e_{1, \ell} $$

for all $\ell, \ell' \in [1, k]$. For $e \in O_L$ we say an interval $I = [s, t] \subseteq [1, k]$ is *e-repetitive* if $s < t$ and $e_s = e_t$. We say $[s, t] \subseteq [1, k]$ is *repetitive* if it is *e-repetitive* for some $e \in O_L$.

By Claim 5.14 there exist indices $1 = t_0 \le s_1 < t_1 < s_2 < t_2 < \dots < s_q < t_q \le s_{q+1} = k$ such that $[s_1, t_1], \dots, [s_q, t_q]$ are all repetitive and for $D_0 = [t_0, s_1], D_1 = [t_1, s_2], \dots, D_q = [t_q, s_{q+1}]$
we have $q + \sum_{p=0}^{q} |D_p| \le 3|O_L|$. Let $i = i_1 < \dots < i_k$ and $j_k < \dots < j_1 = j$ be the positions that correspond to the positions of the letters $a_1, \dots, a_k \in \Sigma_{\text{call}}$ and $b_k, \dots, b_1 \in \Sigma_{\text{ret}}$ of the factorization of $\text{ext}_{w_i \cdots w_{i'}, w_{j'} \cdots w_j}$ in $w$, respectively: more precisely $i_\ell = i + |x_1 \cdots a_{\ell-1}x_\ell|$ and $j_\ell = |x_1 a_1 \cdots x_k a_k w_{i'+1} \cdots w_{j'-1} b_k y_k \cdots b_{\ell+1} y_{\ell+1}| + 1$ for all $\ell \in [1, k]$. Since the non-empty interval $[s_p, t_p]$ is repetitive for all $p \in [1, q]$, we have $e_{s_p} = e_{t_p}$ and thus obtain

$$e_{s_p} = e_{t_p} = e_{s_p} \circ \psi(\text{ext}_{x_{s_p+1} \cdots a_{t_p}, b_{t_p} \cdots y_{s_p+1}}).$$

Given $p \in [1, q]$, if $e_{s_p} \in \mathcal{Z}$, we can use the predicate $\pi_{e_{s_p}}^{\text{exact}}$ to check the above equality; we set $\theta_{d,e_{s_p}}(x, x', y', y) = \pi_{e_{s_p}}^{\text{exact}}(x, x', y', y)$. If $e_{s_p} \notin \mathcal{Z}$ and is $\varphi_L(L)$-reachable, then $\mathcal{U}_{e_{s_p}}$ is length-synchronous, so for all $e' \in O_L$ such that $e_{s_p} \circ e' = e_{s_p}$, we have that $e'$ is $\varphi_L(L)$-reachable and $\mathcal{R}_{e'} = \{(u, v) \in \Sigma^* \times \Sigma^* | uv \in \Sigma^\Delta, \Delta(u) > 0, \psi_L(\text{ext}_{u,v}) = e'\}$ is length-synchronous. So to check the above equality, we can use the formula $\theta_{d,e_{s_p}}(x, x', y', y)$ built by taking the disjunction over all $e' \in O_L$ such that $e_{s_p} \circ e' = e_{s_p}$ of the formulas defined inductively completely analogously as $\chi_{d,e'}(x, x', y', x')$ in Section 5.3.5 (using the sentence $\nu_{\psi_L, e'}$ defining $\mathcal{E}_{\psi_L, e'}$): we simply replace every occurrence of $\eta_{d-1,r}$ by $\bar{\eta}_{d-1,r}$.

Next, for all $m > 0$ and all $\varphi_L(L)$-reachable $f \in O_L$ we will construct a formula $\alpha_{d,m,f}(x, x', y', y)$ such that for all $w \in \Sigma^\Delta$ and $i, i', j', j \in [1, |w|]$, $i \le i' < j' \le j$ we have that if $w_i \cdots w_{i'} w_{j'} \cdots w_j \in \Sigma^\Delta$ and $i'$ is matched to $j'$ in $w$, then given

$$\text{ext}_{w_i \cdots w_{i'}, w_{j'} \cdots w_j} = \text{ext}_{x_1, y_1} \circ \text{ext}_{a_1, b_1} \circ \cdots \circ \text{ext}_{x_k, y_k} \circ \text{ext}_{a_k, b_k}$$

the stair factorization of $\text{ext}_{w_i \cdots w_{i'}, w_{j'} \cdots w_j}$ provided by Lemma 3.6, we have $(w, M^\Delta(w)) \models \alpha_{d,m,f}(i, i', j', j)$ if, and only if, $\text{nd}(x_\ell)$, $\text{nd}(y_\ell) < d$ for all $\ell \in [1, k]$, $\Delta(w_i \cdots w_{i'}) = -\Delta(w_{j'} \cdots w_j) = m$ and $\psi_L(\text{ext}_{w_i \cdots w_{i'}, w_{j'} \cdots w_j}) = e$. For $\boldsymbol{\sigma} = (\boldsymbol{\sigma}_1, \dots, \boldsymbol{\sigma}_m) \in \Sigma_{\text{call}}^m$, $\boldsymbol{\xi} = (\boldsymbol{\xi}_1, \dots, \boldsymbol{\xi}_m) \in \Sigma_{\text{ret}}^m$, $\boldsymbol{r} = (\boldsymbol{r}_1, \dots, \boldsymbol{r}_m) \in R_L^m$, and $\boldsymbol{r}^\dagger = (\boldsymbol{r}_1^\dagger, \dots, \boldsymbol{r}_m^\dagger) \in R_L^m$ we define

$$\prod (\boldsymbol{\sigma}, \boldsymbol{\xi}, \boldsymbol{r}, \boldsymbol{r}^{\dagger}) = \bigcirc_{g=1}^{m} \text{left}_{\boldsymbol{r}_g} \circ \text{right}_{\boldsymbol{r}_g^{\dagger}} \circ \psi_L(\text{ext}_{\boldsymbol{\sigma}_g, \boldsymbol{\xi}_g}).$$

The formula $\alpha_{d,m,f}$ can be expressed as follows:

$$\alpha_{d,m,f}(x, x', y', y) = \bigvee_{\substack{\boldsymbol{\sigma} \in \Sigma_{\text{call}}^m, \boldsymbol{\xi} \in \Sigma_{\text{ret}}^m \\ \boldsymbol{r}, \boldsymbol{r}^{\dagger} \in R_L^m : f = \prod (\boldsymbol{\sigma}, \boldsymbol{\xi}, \boldsymbol{r}, \boldsymbol{r}^{\dagger})}} \exists x_1, \dots, x_m \exists y_1, \dots, y_m \\ \left( \begin{array}{l} x' = x_m \wedge y' = y_m \wedge x \le x_1 < \dots < x_m < y_m < \dots < y_1 \le y \wedge \\ \qquad \bigwedge_{g=1}^m (\sigma_g(x_g) \wedge \xi_g(y_g) \wedge x_g \rightsquigarrow y_g) \wedge \\ \qquad \forall z ((x \le z \le x' \wedge \bigwedge_{g=1}^m z \ne x_g) \rightarrow \neg U(x, x', z)) \wedge \\ \qquad \left( (x < x_1 \wedge \bar{\eta}_{d-1, \boldsymbol{r}_1}(x, x_1 - 1)) \vee F_{\boldsymbol{r}_1}(x, x_1) \right) \wedge \\ \qquad \left( (y_1 < y \wedge \bar{\eta}_{d-1, \boldsymbol{r}_1^\dagger}(y_1 + 1, y)) \vee F_{\boldsymbol{r}_1^\dagger}(y_1, y) \right) \wedge \\ \qquad \bigwedge_{g=2}^m \bar{\eta}_{d-1, \boldsymbol{r}_g}(x_{g-1} + 1, x_g - 1) \wedge \bigwedge_{g=2}^m \bar{\eta}_{d-1, \boldsymbol{r}_g^\dagger}(y_g + 1, y_{g-1} - 1) \end{array} \right)$$
with $F_s(x, z) = \begin{cases} x = z & \text{if } s = 1_{R_L} \\ \perp & \text{otherwise} \end{cases}$ for all $\varphi_L(L)$-reachable $s \in R_L$.

We are now ready to define the formula $\bar{\chi}_{d,e}$:

$$ \bar{\chi}_{d,e}(x, x', y', x) = \bigvee_{\substack{q \in [0, |O|] \\ d_0, \dots, d_q \ge 1 \\ q+d_0+\dots+d_q \le 3|0|}} \bigvee_{\substack{e_0, f_0, \dots, f_{q-1}, e_q, f_q \in O \\ e_0 = 1_O \wedge \forall j \in [1,q] : e_j = e_{j-1} \circ f_{j-1} \\ e = e_q \circ f_q}} \exists x_1 \dots x_{q+1} \exists x'_0 \dots x'_q \exists y_1 \dots y_{q+1} \exists y'_1 \dots y'_0 \\ \left( \begin{array}{l} x'_0 \le x_1 < x'_1 < x_2 < \dots < x'_q < y'_q < y_q < \dots < y'_1 < y_1 \le y'_0 \wedge \\ x'_0 = x \wedge y'_0 = y \wedge x'_q = x' \wedge y'_q = y' \wedge \\ \bigwedge_{p=1}^q (\theta_{e_p}(x_p + 1, x'_p, y'_p, y_p - 1)) \wedge \bigwedge_{p=0}^q \alpha_{d_p, f_p}(x'_p + 1, x_{p+1}, y_{p+1}, y'_p - 1) \end{array} \right) . $$

The inductive definition of $\bar{\eta}_{d,r}^{\uparrow}$ is completely analogous to the definition of $\eta_{d,r}$ in Section 5.3.5: we simply replace every occurrence of $\eta_{d-1,r}$ by $\bar{\eta}_{d-1,r}$ and every occurrence of $\chi_{d,e}$ by $\bar{\chi}_{d,e}$.

The inductive definition of $\bar{\eta}_{d,r}$ is completely analogous to the definition of $\eta_{d,r}$ in Section 5.3.5: we access the horizontal evaluation languages $\mathcal{E}_{\varphi_L(L)}$ for all $\varphi_L(L)$-reachable $r \in R_L$ by making use of the sentence $\nu_{\varphi,r}$ and the already defined $\bar{\eta}_{d,r}^{\uparrow}$. $\square$

### 5.4.2 Computation of $k, l$

The following proposition implies the computability of $k, l \in \mathbb{N}$ such that $\mathcal{L}_{k,l} \le_{cd} L$ already when VPL $L$ is weakly length-synchronous but not length-synchronous.

**Proposition 5.24.** If a VPL $L$ is weakly length-synchronous but not length-synchronous, one can effectively compute $k, l \in \mathbb{N}_{>0}$ with $k \neq l$ such that $\mathcal{L}_{k,l} \le_{cd} L$.

*Proof.* Let $L \subseteq \Sigma^\Delta$ be a weakly length-synchronous VPL that is not length-synchronous. According to Point 2 (b) of Proposition 5.1 one can effectively compute a quadruple $(k_0, l_0, k'_0, l'_0) \in \mathbb{N}_{>0}^4$ for which there exist $\text{ext}_{u,v}, \text{ext}_{u',v'} \in \mathcal{O}(\Sigma^\Delta)$ such that

* $|u| = k_0, |v| = l_0, |u'| = k'_0, |v'| = l'_0,$

* $\psi_L(\text{ext}_{u,v}) = \psi_L(\text{ext}_{u',v'})$ is a $\varphi_L(L)$-reachable idempotent,

* $\Delta(u), \Delta(u') > 0$, and

* $\frac{k_0}{l_0} = \frac{|u|}{|v|} \neq \frac{|u'|}{|v'|} = \frac{k'_0}{l'_0}.$

We can explicitly compute such $\text{ext}_{u,v}$ and $\text{ext}_{u',v'}$ by just doing an exhaustive search. This enables us to assume without loss of generality while maintaining effective computability that $\Delta(u) = \Delta(u')$: indeed, in case $\Delta(u) \neq \Delta(u')$, we can consider $\text{ext}_{u_1,v_1} = \text{ext}_{u_\Delta(u'),v_\Delta(u')}$ and $\text{ext}_{u_2,v_2} = \text{ext}_{(u')\Delta(u'),(v')\Delta(u)}$ satisfying the desired properties.

Let us now define Green's relations on $O_L$ (see [26, Chapter 3, Section 1]). Let us consider two elements $x, y$ of $O_L$.
* We write $x \le_{\mathfrak{J}} y$ whenever there are elements $e, f$ of $O_L$ such that $x = e \circ y \circ f$. We write $x \mathfrak{J} y$ if $x \le_{\mathfrak{J}} y$ and $y \le_{\mathfrak{J}} x$. We finally write $x <_{\mathfrak{J}} y$ if $x \not\le_{\mathfrak{J}} y$ and $x \not\mathfrak{J} y$.

* We write $x \le_{\mathfrak{R}} y$ whenever there is an element $e$ of $O_L$ such that $x = y \circ e$. We write $x \mathfrak{R} y$ if $x \le_{\mathfrak{R}} y$ and $y \le_{\mathfrak{R}} x$.

* We write $x \le_{\mathcal{L}} y$ whenever there is an element $e$ of $O_L$ such that $x = e \circ y$. We write $x \mathcal{L} y$ if $x \le_{\mathcal{L}} y$ and $y \le_{\mathcal{L}} x$.

* We write $x \mathfrak{H} y$ if $x \mathfrak{R} y$ and $x \mathcal{L} y$.

Observe that because $\Delta(u) = \Delta(u')$, we have that $uv' \in \Sigma^\Delta$ and $u'v \in \Sigma^\Delta$, so that we can consider the elements $\mathrm{ext}_{uuu,vv'v} = \mathrm{ext}_{u,v} \circ \mathrm{ext}_{u,v'} \circ \mathrm{ext}_{u,v}$ and $\mathrm{ext}_{uu'u,vvv} = \mathrm{ext}_{u,v} \circ \mathrm{ext}_{u',v} \circ \mathrm{ext}_{u,v}$ in $\mathcal{O}(\Sigma^\Delta)$. These elements satisfy $\psi_L(\mathrm{ext}_{uuu,vv'v}) \le_{\mathfrak{J}} \psi_L(\mathrm{ext}_{u,v})$ and $\psi_L(\mathrm{ext}_{uu'u,vvv}) \le_{\mathfrak{J}} \psi_L(\mathrm{ext}_{u,v})$. We claim that we actually have $\psi_L(\mathrm{ext}_{uuu,vv'v}) <_{\mathfrak{J}} \psi_L(\mathrm{ext}_{u,v})$ and $\psi_L(\mathrm{ext}_{uu'u,vvv}) <_{\mathfrak{J}} \psi_L(\mathrm{ext}_{u,v})$. Indeed, assume we would have $\psi_L(\mathrm{ext}_{uu'u,vvv}) \mathfrak{J} \psi_L(\mathrm{ext}_{u,v})$. Set $x = \psi_L(\mathrm{ext}_{u,v})$ and $y = \psi_L(\mathrm{ext}_{u',v})$. By a classical property of Green's relations (see [26, Chapter 3, Proposition 1.4]), since it would hold that $x \circ y \circ x \le_{\mathfrak{R}} x$ and $x \circ y \circ x \mathfrak{J} x$, we would have $x \circ y \circ x \mathfrak{R} x$ and dually, since it would hold that $x \circ y \circ x \le_{\mathcal{L}} x$ and $x \circ y \circ x \mathfrak{J} x$, we would have $x \circ y \circ x \mathcal{L} x$. Therefore, we would have $x \circ y \circ x \mathfrak{H} x$. By another classical result on Green's relations [26, Chapter 3, Corollary 1.7], as $x$ is an idempotent, its $\mathfrak{H}$-class is a group, hence for $\omega \in \mathbb{N}_{>0}$ the idempotent power of $O_L$, we would have $(x \circ y \circ x)^\omega = x^\omega = x$ (as the only idempotent element in a group is the identity). This would finally entail that $\psi_L(\mathrm{ext}_{(uu'u)^\omega,(vvv)^\omega}) = \psi_L(\mathrm{ext}_{(uuu)^\omega,(vvv)^\omega})$ is a $\varphi_L(L)$-reachable idempotent and $\Delta((uu'u)^\omega) = \Delta((uuu)^\omega) > 0$ but $|(uu'u)^\omega| \neq |(uuu)^\omega|$, a contradiction to the fact that $(\varphi_L, \psi_L)$ is $\varphi_L(L)$-weakly-length-synchronous. Symmetrically, we can prove that if we had $\psi_L(\mathrm{ext}_{uuu,vv'v}) \mathfrak{J} \psi_L(\mathrm{ext}_{u,v})$, this would contradict the fact that $(\varphi_L, \psi_L)$ is $\varphi_L(L)$-weakly-length-synchronous.

We distinguish three cases. In each of these we prove that there exist $k,l \in \mathbb{N}_{>0}$, $k \neq l$ such that $\mathcal{L}_{k,l} \le_{cd} L_{\psi_L(\mathrm{ext}_{u,v})}$, so that since $L_{\psi_L(\mathrm{ext}_{u,v})} \le_{cd} L$ (by Lemma 5.3) and by transitivity of $\le_{cd}$ we have $\mathcal{L}_{k,l} \le_{cd} L$.

**Case** $|v| = |v'|$. In that case, we necessarily have $|u| \neq |u'|$. Then, we can exploit the fact that matching $u^3$ with $vv'v$ or $uu'u$ with $v^3$ makes us fall down to a smaller $\mathfrak{J}$-class to reduce $\mathcal{L}_{3|u|,2|u|+|u'|}$ to $L_{\psi_L(\mathrm{ext}_{u,v})}$. The constant-depth reduction works as follows on input $w \in \Sigma^*$:

1. check if $w = xy$ with $x \in (ac^{3|u|-1} + ac^{2|u|+|u'|-1})^*$ and $y \in (b_1 + b_2)^*$, reject if it's not the case;

2. build $x'$ by sending $ac^{3|u|-1}$ to $u^3$, $ac^{2|u|+|u'|-1}$ to $uu'u$ and $y'$ by sending $b_1$ to $v^3$ and $b_2$ to $vv'v$;

3. accept whenever $x'\#y' \in L_{\psi_L(\mathrm{ext}_{u,v})}$.

This forms a valid reduction. Indeed, take a word $w = xy$ with $x \in (ac^{3|u|-1} + ac^{2|u|+|u'|-1})^n$ for $n \in \mathbb{N}$ and $y \in (b_1+b_2)^m$ for $m \in \mathbb{N}$ and consider $x'\#y'$ produced by the reduction with $x' \in (u^3+uu'u)^n$ and $y' \in (v^3+vv'v)^m$. If $w \in \mathcal{L}_{3|u|,2|u|+|u'|}$, then it easily follows that $x'\#y' \in L_{\psi_L(\mathrm{ext}_{u,v})}$. Otherwise, if $w \notin \mathcal{L}_{3|u|,2|u|+|u'|}$, then either $n \neq m$ and thus $x'y'$ is not well-matched because $\Delta(x') = n \cdot 3 \cdot \Delta(u)$ and $\Delta(y') = m \cdot 3 \cdot \Delta(v)$, or $n = m$ and thus $x'y'$ is well-matched, so $\mathrm{ext}_{x',y'} = \mathrm{ext}_{z'_1,t'_1} \circ \cdots \circ \mathrm{ext}_{z'_n,t'_n}$
with $z'_1, \dots, z'_n \in \{u^3, uu'u\}$ and $t'_1, \dots, t'_n \in \{v^3, vv'v\}$ such that there exists $i \in [1, n]$ satisfying $\mathrm{ext}_{z'_i, t'_i} \in \{\mathrm{ext}_{u^3, vv'v}, \mathrm{ext}_{uu'u, v^3}\}$, thereby implying

$$ \psi_L(\mathrm{ext}_{x', y'}) \leq_{\mathfrak{J}} \psi_L(\mathrm{ext}_{z'_i, t'_i}) <_{\mathfrak{J}} \psi_L(\mathrm{ext}_{u, v}). $$

Our algorithm therefore outputs the pair $(k, l) = (3k_0, 2k_0 + k'_0)$.

**Case** $|u| = |u'|$. This case is symmetric to the previous case. Our algorithm outputs the pair $(k, l) = (2l_0 + l'_0, 3l_0)$.

**Case** $|u| \neq |u'|$ and $|v| \neq |v'|$. Then, we can again exploit the fact that matching $u^3$ with $vv'v$ or $uu'u$ with $v^3$ makes us fall down to a smaller $\mathfrak{J}$-class to reduce $\mathcal{L}_{A \cdot B', A' \cdot B}$ where $A = 3|u| = 3k_0$, $A' = 2|u| + |u'| = 2k_0 + k'_0$, $B = 3|v| = 3l_0$ and $B' = 2|v| + |v'| = 2l_0 + l'_0$ to $L_{\psi_L(\mathrm{ext}_{u, v})}$. Indeed, we have $A \cdot B' \neq A' \cdot B$ because otherwise we would have

$$ \begin{aligned} 3|u| \cdot (2|v| + |v'|) &= (2|u| + |u'|) \cdot 3|v| \\ 6|u||v| + 3|u||v'| &= 6|u||v| + 3|u'||v| \\ |u||v'| &= |u'||v|. \end{aligned} $$

The constant-depth reduction works as follows on input $w \in \Sigma^*$:

1. check if $w = xy$ with $x \in (ac^{A \cdot B'^{-1}} + ac^{A' \cdot B^{-1}})^*$ and $y \in (b_1 + b_2)^*$, reject if it is not the case;

2. build $x'$ by sending $ac^{A \cdot B'^{-1}}$ to $(u^3)^{B'}$, $ac^{A' \cdot B^{-1}}$ to $(uu'u)^B$ and $y'$ by sending $b_1$ to $(v^3)^{B'}$ and $b_2$ to $(vv'v)^B$;

3. accept whenever $x' \# y' \in L_{\psi_L(\mathrm{ext}_{u, v})}$.

This forms a valid reduction. Indeed, take a word $w = xy$ with $x = z_1 \cdots z_n$ where $n \in \mathbb{N}$ and $z_1, \dots, z_n \in \{ac^{A \cdot B'^{-1}}, ac^{A' \cdot B^{-1}}\}$ and $y = t_1 \cdots t_m$ where $m \in \mathbb{N}$ and $t_1, \dots, t_m \in \{b_1, b_2\}$. Consider $x' \# y'$ produced by the reduction with $x' = z'_1 \cdots z'_n$ where $z'_1, \dots, z'_n \in \{(u^3)^{B'}, (uu'u)^B\}$ and $y' = t'_1 \cdots t'_m$ where $t'_1, \dots, t'_m \in \{(v^3)^{B'}, (vv'v)^B\}$. If $w \in \mathcal{L}_{A \cdot B', A' \cdot B}$, then it easily follows that $x' \# y' \in L_{\psi_L(\mathrm{ext}_{u, v})}$. Otherwise, if $w \notin \mathcal{L}_{A \cdot B', A' \cdot B}$, three situations can occur.

* There exists $i \in [1, \min\{n, m\}]$ such that $z_1 \cdots z_{i-1} t_{i-1} \cdots t_1 \in \mathcal{L}_{A \cdot B', A' \cdot B}$ but it holds that $(z_i, t_i) \in \{(ac^{A \cdot B'^{-1}}, b_2), (ac^{A' \cdot B^{-1}}, b_1)\}$. Assume first $(z_i, t_i) = (ac^{A' \cdot B^{-1}}, b_1)$. In this case, let $\tilde{x}' = (uu'u)^{B^{-1}} z'_{i+1} \cdots z'_n$ and $\tilde{y}' = t'_n \cdots t'_{i+1} (v^3)^{B'^{-1}}$. If $\Delta(\tilde{x}'\tilde{y}') \neq 0$, then

$$ \Delta(x'y') = \Delta(z'_1 \cdots z'_{i-1}(uu'u)v^3 t'_{i-1} \cdots t'_1) + \Delta(\tilde{x}'\tilde{y}') = \Delta(\tilde{x}'\tilde{y}') \neq 0, $$

thus $x'y'$ is not well-matched. Otherwise, if $\Delta(\tilde{x}'\tilde{y}') = 0$, we can show that $\tilde{x}'\tilde{y}'$ is well-matched. Indeed, since $uv \in \Sigma^\Delta$, for all $j \in [1, |u|]$, we have $\Delta(u_1 \cdots u_j) \ge 0$ and for all $j \in [1, |v|]$, we have $\Delta(v_j \cdots v_{|v|}) = -\Delta(uv_1 \cdots v_{j-1}) \le 0$. Similarly, since $u'v' \in \Sigma^\Delta$, for all $j \in [1, |u'|]$, we have $\Delta(u'_1 \cdots u'_j) \ge 0$ and for all $j \in [1, |v'|]$, we have $\Delta(v'_j \cdots v'_{|v'|}) = -\Delta(u'v'_1 \cdots v'_{j-1}) \le 0$. This implies that for all $j \in [1, |\tilde{x}'|]$, we have $\Delta(\tilde{x}'_1 \cdots \tilde{x}'_j) \ge 0$ and for all $j \in [1, |\tilde{y}'|]$, we have $\Delta(\tilde{x}'_j \cdots \tilde{y}'_{|\tilde{y}'|}) = -\Delta(\tilde{y}'_j \cdots \tilde{y}'_{|\tilde{y}'|}) \ge 0$. Therefore, $\tilde{x}'\tilde{y}' \in \Sigma^\Delta$. Hence $x'y'$ is well-matched and

$$ \mathrm{ext}_{x', y'} = \mathrm{ext}_{z'_1 \cdots z'_{i-1}, t'_{i-1} \cdots t'_1} \circ \mathrm{ext}_{z'_i, t'_i} \circ \mathrm{ext}_{\tilde{x}', \tilde{y}'} $$

so that

$$ \psi_L(\mathrm{ext}_{x', y'}) \leq_{\mathfrak{J}} \psi_L(\mathrm{ext}_{z'_i, t'_i}) <_{\mathfrak{J}} \psi_L(\mathrm{ext}_{u, v}). $$
If we assume that $(z_i, t_i) = (ac^{A \cdot B'^{-1}}, b_2)$, then we prove in the same way that either $x'y'$ is not well-matched or it is well-matched and $\psi_L(\mathrm{ext}_{x',y'}) <_J \psi_L(\mathrm{ext}_{u,v})$.

* It holds that $n < m$ and $z_1 \cdots z_n t_n \cdots t_1 \in \mathcal{L}_{A \cdot B', A' \cdot B}$. This entails that $\Delta(x't'_n \cdots t'_1) = \Delta(z'_1 \cdots z'_n t'_n \cdots t'_1) = 0$, so that

$$ \Delta(x'y') = \Delta(x't'_n \cdots t'_1) + \Delta(t'_m \cdots t'_{n+1}) = \Delta(t'_m \cdots t'_{n+1}) < 0 $$

because $m > n$ and $\Delta(v) < 0$ as well as $\Delta(v') < 0$. Therefore, $x'y'$ is not well-matched.

* It holds that $n > m$ and $z_1 \cdots z_m t_m \cdots t_1 \in \mathcal{L}_{A \cdot B', A' \cdot B}$. Symmetrically to the previous case, we can also show that then, $x'y'$ is not well-matched.

Hence, our algorithm outputs the pair $(k, l) = (A \cdot B', A' \cdot B) = (3k_0(2l_0 + l'_0), (2k_0 + k'_0)3l_0)$ in this last case. □

## 5.5 Proof of Corollary 2.11

Let $A = (Q, \Sigma, q_0, F, \delta_0, \dots, \delta_m)$ be a $m$-VCA and let $L = L(A)$. One easily computes from $A'$ a DVPA such that $L(A') = L$. Details of this standard translation are omitted. It will be sufficient to prove that $L$ is weakly length-synchronous if, and only if, $L$ is length-synchronous: indeed, one can simply perform the case distinction of Section 5.1 and observe that, under the assumption that weak length-synchronicity and length synchronicity coincide, the algorithm for Theorem 2.9 will either output that $L$ is in $\mathcal{AC}^0$ or some $m \ge 2$ such that $\mathrm{MOD}_m \le_{cd} L$.

It thus suffices to prove that if $L$ is not length-synchronous, then $L$ is not weakly length-synchronous. Let $(R_L, O_L)$ be the syntactic Ext-algebra of $L$ along with its syntactic morphism $(\varphi_L, \psi_L) : (\Sigma^\Delta, \mathcal{O}(\Sigma^\Delta)) \to (R_L, O_L)$.

Let $\mathcal{M} = [0, m] \times (Q^Q)^{[0,m]} \times (Q^Q)^{[0,m]}$. The behavior of the $m$-VCA can be described as follows. To each $\mathrm{ext}_{u,v} \in \mathcal{O}(\Sigma^\Delta)$ we assign the triple $\zeta(\mathrm{ext}_{u,v}) = (j, (f_i)_{i \in [0,m]}, (g_i)_{i \in [0,m]}) \in \mathcal{M}$, where

* $j = \min(\Delta(u), m) \in [0, m]$,

* $f_i(q) = q'$ where $q' \in Q$ is the unique state such that $q(i) \xrightarrow{u} A q'(i + j)$ for all $q \in Q$ and all $i \in [0, m]$, and

* $g_i(q) = q'$, where $q' \in Q$ is the unique state such that $q'(i + j) \xrightarrow{v} A q'(i)$ for all $q \in Q$ and all $i \in [0, m]$.

Over $\mathcal{M}$ we define the product

$$ (j, (f_i)_{i \in [0,m]}, (g_i)_{i \in [0,m]}) \odot_{\mathcal{M}} (j', (f'_i)_{i \in [0,m]}, (g'_i)_{i \in [0,m]}) $$

as

$$ (\min(j + j', m), (f'_{\min(i+j,m)} \circ f_i)_{i \in [0,m]}, (g_{\min(i+j,m)} \circ g'_{\min(i+j',m)})_{i \in [0,m]}) $$

We claim $\odot_{\mathcal{M}}$ is associative. For this, let us fix

* $m = (j, (f_i)_{i \in [0,m]}, (g_i)_{i \in [0,m]}) \in \mathcal{M}$,

* $m' = (j', (f'_i)_{i \in [0,m]}, (g'_i)_{i \in [0,m]}) \in \mathcal{M}$, and

* $m'' = (j'', (f''_i)_{i \in [0,m]}, (g''_i)_{i \in [0,m]}) \in \mathcal{M}$.
Let $\tilde{m} = m \odot_M m' = (\tilde{j}, (\tilde{f}_i)_{i \in [0,m]}, (\tilde{g}_i)_{i \in [0,m]})$ and $\bar{m} = m' \odot_M m'' = (\bar{j}, (\bar{f}_i)_{i \in [0,m]}, (\bar{g}_i)_{i \in [0,m]})$. We need to prove $\tilde{m} \odot_M m'' = m \odot_M \bar{m}$.

Since $j, j', j'', m \ge 0$ we have $\min(\tilde{j}+j'', m) = \min(\min(j+j', m)+j'', m) = \min(j+j'+j'', m) = \min(j + \min(j' + j'', m), m)) = \min(j + \bar{j}, m)$ associativity holds on the first component. For each $i \in [0, m]$ the $i^{th}$ component of the second component of $\tilde{m} \odot_M m''$ is

$$ 
\begin{align*}
f''_{\min(i+\tilde{j},m)} \circ \tilde{f}_i &= f''_{\min(i+\tilde{j},m)} \circ (f'_{\min(i+\tilde{j},m)} \circ f_i) \\
&= f''_{\min(i+\min(j+\tilde{j}',m),m)} \circ (f'_{\min(i+\tilde{j},m)} \circ f_i) \\
&= f''_{\min(i+\tilde{j}+j',m)} \circ (f'_{\min(i+\tilde{j},m)} \circ f_i) \\
&= (f''_{\min(i+\tilde{j}+j'',m)} \circ f'_{\min(i+\tilde{j},m)}) \circ f_i \\
&= (f''_{\min(\min(i+\tilde{j},m)+j',m)} \circ f'_{\min(i+\tilde{j},m)}) \circ f_i \\
&= \bar{f}_{\min(i+\tilde{j},m)} \circ f_i
\end{align*}
$$

the latter of which is the $i^{th}$ component of the second component of $m \odot_M \bar{m}$, as required. For each $i \in [0, m]$ the $i^{th}$ component of the third component of $m \odot_M \bar{m}$ is

$$ 
\begin{align*}
g_{\min(i+\tilde{j},m)} \circ \bar{g}_{\min(i+\tilde{j}+\bar{j},m))} &= g_{\min(i+\tilde{j},m)} \circ \bar{g}_{\min(i+\tilde{j}+j'+j'',m)} \\
&= g_{\min(i+\tilde{j},m)} \circ \bar{g}_{\min(\min(i+\tilde{j},m)+j'+j'',m)} \\
&= g_{\min(i+\tilde{j},m)} \circ (g'_{\min(\min(i+\tilde{j},m)+j')} \circ g''_{\min(\min(i+\tilde{j},m),j'+j'',m)}) \\
&= (g_{\min(i+\tilde{j},m)} \circ g'_{\min(\min(i+\tilde{j},m)+j')}) \circ g''_{\min(\min(i+\tilde{j},m),j'+j'',m)} \\
&= (g_{\min(i+\tilde{j},m)} \circ g'_{\min(i+\tilde{j}+j',m)}) \circ g''_{\min(i+\min(i+\tilde{j}',m)+j'',m)} \\
&= \tilde{g}_i \circ g''_{\min(i+\tilde{j}+j'',m)}
\end{align*}
$$

the latter of which is the $i^{th}$ component of the third component of $\tilde{m} \odot_M m''$, as required. Clearly $(0, (\mathrm{id}_Q)^{[0,m]}, (\mathrm{id}_Q)^{[0,m]})$ is the identity of $M$ with respect to $\odot_M$, hence $(M, \odot_M)$ is a monoid. The following points can easily be verified.

1. The function $\zeta : \mathcal{O}(\Sigma^\Delta) \to \mathcal{M}$ is a monoid morphism.

2. For all $\mathrm{ext}_{u,v}, \mathrm{ext}_{u',v'} \in \mathcal{O}(\Sigma^\Delta)$ with $\Delta(u) = \Delta(u')$ we have

$$ \zeta(\mathrm{ext}_{u,v}) = \zeta(\mathrm{ext}_{u',v'}) \implies \zeta(\mathrm{ext}_{u,v}) = \zeta(\mathrm{ext}_{u',v}) = \zeta(\mathrm{ext}_{u,v'}) = \zeta(\mathrm{ext}_{u',v'}). $$

3. For all $\mathrm{ext}_{u,v}, \mathrm{ext}_{u',v'} \in \mathcal{O}(\Sigma^\Delta)$ we have

$$ \zeta(\mathrm{ext}_{u,v}) = \zeta(\mathrm{ext}_{u',v'}) \implies \psi_L(\mathrm{ext}_{u,v}) = \psi_L(\mathrm{ext}_{u',v>). $$

Now assume that $L$ is not length-synchronous. We will prove that $L$ is not length-synchronous. By assumption there exist a $\varphi_L(L)$-reachable idempotent $e \in O_L$ and $\mathrm{ext}_{u,v}, \mathrm{ext}_{u',v'} \in \mathcal{O}(\Sigma^\Delta)$ such that $\Delta(u), \Delta(u') > 0$, $|\frac{u}{v}| \neq |\frac{u'}{v'}|$, and $\psi_L(\mathrm{ext}_{u,v}) = \psi_L(\mathrm{ext}_{u',v'}) = e$. Without loss of generality we may assume $\Delta(u) = \Delta(u')$. Let $\omega$ denote the idempotent power of $M$. Consider the elements

$$ \mathrm{ext}_{x,y} = (\mathrm{ext}_{u,v}^{2\omega} \circ \mathrm{ext}_{u',v'}^{\omega})^{\omega} \text{ and } \mathrm{ext}_{x',y'} = (\mathrm{ext}_{u,v}^{\omega} \circ \mathrm{ext}_{u',v'}^{2\omega})^{\omega}. $$
By definition we have $\zeta(\mathrm{ext}_{x,y}) = \zeta(\mathrm{ext}_{x',y'})$, and since $\Delta(x) = \Delta(x')$ we obtain $\zeta(\mathrm{ext}_{x,y}) = \zeta(\mathrm{ext}_{x',y'}) = \zeta(\mathrm{ext}_{x',y'})$ by Point 2. Hence,

$$ \psi_L(\mathrm{ext}_{x,y}) = \psi_L(\mathrm{ext}_{x',y}) = \psi_L(\mathrm{ext}_{x,y'}) = \psi_L(\mathrm{ext}_{x',y'}) = e $$

by Point 3.

We finally make a case distinction on whether $|u| = |u'|$ or not.

First, assume $|u| \neq |u'|$. Then $|x| \neq |x'|$ by construction. Since $\psi_L(\mathrm{ext}_{x,y}) = \psi_L(\mathrm{ext}_{x',y}) = e$, which is an idempotent of $O_L$, we obtain that $L$ is not weakly length-synchronous.

Now assume $|u| = |u'|$. Since $|\frac{u}{|v|} \neq \frac{|u'|}{|v'|}$ by assumption, we conclude that $|v| \neq |v'|$. By construction, the latter implies $|y| \neq |y'|$. Since $\psi_L(\mathrm{ext}_{x,y}) = \psi_L(\mathrm{ext}_{x,y'}) = e$, again we obtain that $L$ is not weakly length-synchronous.

# 6 Proof of Proposition 5.1

We will prove the different statements appearing in Proposition 5.1 in the following subsections.

**Computability of the syntactic Ext-algebra.** This paragraph will be devoted to proving Point 1 of Proposition 5.1, rephrased in the following proposition.

**Proposition 6.1.** Given a DVPA A with $L = L(A)$, one can compute the syntactic Ext-algebra $(R_L, O_L)$ of L, its syntactic morphism $(\varphi_L, \psi_L)$ and $\varphi_L(L)$.

We require a bit of notation. For each visibly pushdown alphabet $\Sigma$ and each finite Ext-algebra $(R, O)$ it follows from Proposition 3.7 that each morphism $(\varphi, \psi): (\Sigma^\Delta, \mathcal{O}(\Sigma^\Delta)) \to (R, O)$ has a unique finite presentation: it is given by the tuples

$$ (\varphi(c))_{c \in \Sigma_{\mathrm{int}}} \quad \text{and} \quad (\psi(\mathrm{ext}_{a,b}))_{(a,b) \in \Sigma_{\mathrm{call}} \times \Sigma_{\mathrm{ret}}}. $$

The syntactic Ext-algebra $(R_L, O_L)$ of a VPL $L$ over a visibly pushdown alphabet $\Sigma$ can be represented by any Ext-algebra $(R, O)$ such that $R$ has $[1, |R_L|]$ as base set and such that there exists a bijective morphism $(\alpha, \beta): (R, O) \to (R_L, O_L)$. Indeed, in that case we have

1. $xy = z \Leftrightarrow \alpha(x)\alpha(y) = \alpha(z)$ for all $x, y, z \in R$;

2. $x'y' = z' \Leftrightarrow \alpha^{-1}(x')\alpha^{-1}(y') = \alpha^{-1}(z')$ for all $x', y', z' \in R_L$;

3. $f(x) = y \Leftrightarrow \beta(f)(\alpha(x)) = \alpha(y)$ for all $f \in O$ and all $x, y \in R$; and

4. $f'(x') = y' \Leftrightarrow \beta^{-1}(f')(\alpha^{-1}(x')) = \alpha^{-1}(y')$ for all $f' \in O_L$ and all $x', y' \in R_L$.

For the following claim we avoid the tedious standard algebraic constructions on Ext-algebras to show decidability of the equivalence problem, since the latter decidability has already been established in $[2]$.

**Claim 6.2.** There is an algorithm that decides, given two morphisms into finite Ext-algebras $(\varphi_1, \psi_1): (\Sigma^\Delta, \mathcal{O}(\Sigma^\Delta)) \to (R_1, O_1)$ and $(\varphi_2, \psi_2): (\Sigma^\Delta, \mathcal{O}(\Sigma^\Delta)) \to (R_1, O_1)$ for $\Sigma$ a visibly push-down alphabet and subsets $F_1 \subseteq R_1$ and $F_2 \subseteq R_2$, whether $\varphi_1^{-1}(F_1) = \varphi_2^{-1}(F_2)$.

*Proof of the Claim.* The proof of Theorem 3.18 shows that one can effectively compute DVPAs $A_1$ and $A_2$ such that $L(A_1) = \varphi_1^{-1}(F_1)$ and $L(A_2) = \varphi_2^{-1}(F_2)$. By [2] one can effectively decide if $L(A_1) = L(A_2)$ by deciding $L(A_1) \subseteq L(A_2)$ and $L(A_2) \subseteq L(A_1)$. $\square$
Proof of Proposition 6.1. By Theorem 3.18 we first compute from our DVPA A on the visibly push-down alphabet Σ an Ext-algebra (R_A, O_A), a morphism (φ_A, ψ_A): (Σ^Δ, O(Σ^Δ)) → (R_A, O_A), and a subset F_A ⊆ R_A such that L(A) = φ_A^{-1}(F_A). For an Ext-algebra (R, O) define #(R, O) = (|R|, |O|). Let ≺⊆ (N × N)² be the lexicographic order on N × N, i.e. (i, j) ≺ (k, l) if, and only if either i < k, or i = k and j < l.

Observe that since $(R_A, O_A)$ recognizes $L$, we have that the syntactic Ext-algebra $(R_L, O_L)$ of $L$ divides $(R_A, O_A)$ by Proposition 3.17, so that $\#(R_L, O_L) \le \#(R_A, O_A)$. In fact, we have that any Ext-algebra $(R, O)$ having $[1, i]$ for $i \in [1, |R_L|]$ as base set, satisfying $\#(R, O) \le \#(R_L, O_L)$ and recognizing $L$ via a morphism $(\varphi, \psi): (\Sigma^\Delta, \mathcal{O}(\Sigma^\Delta)) \to (R, O)$ is a presentation of $(R_L, O_L)$ with $(\varphi, \psi)$ and $F$ presentations of, respectively, $(\varphi_L, \psi_L)$ and $\varphi_L(L)$. Indeed, since such an Ext-algebra recognizes $L$, by Proposition 3.17 it is divided by $(R_L, O_L)$: this implies that $\#(R_L, O_L) \le \#(R, O)$, but as also $\#(R, O) \le \#(R_L, O_L)$, we have $\#(R, O) = \#(R_L, O_L)$. The morphism $(\varphi, \psi)$ must be surjective, otherwise, by Lemma 3.15, $(\varphi(\Sigma^\Delta), \psi(\mathcal{O}(\Sigma^\Delta))|_{\varphi(\Sigma^\Delta)})$ would be a sub-Ext-algebra of $(R, O)$ recognizing $L$ such that $\#(\varphi(\Sigma^\Delta), \psi(\mathcal{O}(\Sigma^\Delta))|_{\varphi(\Sigma^\Delta)}) < \#(R, O) = \#(R_L, O_L)$ while $(R_L, O_L)$ divides $(\varphi(\Sigma^\Delta), \psi(\mathcal{O}(\Sigma^\Delta))|_{\varphi(\Sigma^\Delta)})$, which is contradictory. Therefore, by Lemma 3.16, there is a surjective morphism $(\alpha, \beta): (R, O) \to (R_L, O_L)$, that must be bijective, such that $\varphi_L = \alpha \circ \varphi$, so that $(R, O)$ is a presentation of $(R_L, O_L)$ with $(\varphi, \psi)$ and $F$ presentations of, respectively, $(\varphi_L, \psi_L)$ and $\varphi_L(L)$.

Under the assumption that such an Ext-algebra exists, we compute $(R_L, O_L)$, $(\varphi_L, \psi_L)$ and $\varphi_L(L)$ by enumerating all the finitely many triples made of a finite Ext-algebra $(R, O)$, a morphism $(\varphi, \psi): (\Sigma^\Delta, \mathcal{O}(\Sigma^\Delta)) \to (R, O)$ and a subset $F \subseteq R$ such that $R$ has $[1, i]$ for $i \in [1, |R_A|]$ as base set and $\#(R, O) \le \#(R_A, O_A)$. For each of these we test whether $\varphi^{-1}(F) = \varphi_A^{-1}(F_A)$, which is possible by the above claim and take $(R, O)$, $(\varphi, \psi)$ and $F$ from a triple validating this test with $\#(R, O)$ minimal with respect to ≺.

It remains to prove that an Ext-algebra $(R, O)$ having $[1, i]$ for $i \in [1, |R_L|]$ as base set, satisfying $\#(R, O) \le \#(R_L, O_L)$ and recognizing $L$ exists. Take any bijection $\alpha: R_L \to [1, |R_L|]$. We define $R$ to be the monoid with base set $[1, |R_L|]$ and operation defined by $x \cdot y = \alpha(\alpha^{-1}(x)\alpha^{-1}(y))$ for all $x, y \in [1, |R_L|]$. This is a monoid because

* $x \cdot \alpha(1_R) = \alpha(\alpha^{-1}(x)\alpha^{-1}(\alpha(1_R))) = \alpha(\alpha^{-1}(x)) = \alpha(\alpha^{-1}(\alpha(1_R))\alpha^{-1}(x)) = \alpha(1_R) \cdot x$ for all $x \in R$; and

* for all $x, y, z \in R$, we have

$$ 
\begin{aligned}
x \cdot (y \cdot z) &= \alpha \left( \alpha^{-1}(x) \alpha^{-1} \left( \alpha \left( \alpha^{-1}(y) \alpha^{-1}(z) \right) \right) \right) \\
&= \alpha \left( \alpha^{-1}(x) \alpha^{-1}(y) \alpha^{-1}(z) \right) \\
&= \alpha \left( \alpha^{-1} \left( \alpha \left( \alpha^{-1}(x) \alpha^{-1}(y) \right) \right) \alpha^{-1}(z) \right) \\
&= (x \cdot y) \cdot z.
\end{aligned}
$$

Define the function $\beta: O_L \to R^R$ by $\beta(f')(x) = \alpha(f'(\alpha^{-1}(x)))$ for all $f' \in O_L$ and $x \in R$. Set $O$ to be the monoid with base set $\beta(O_L)$ and with composition as operation. This is a monoid because

* $\beta(1_O)(x) = \alpha(1_O(\alpha^{-1}(x))) = x = \mathrm{id}_R(x)$ for all $x \in R$; and
• for all $f', g' \in O_L$,

$$ \beta(f') \circ \beta(g')(x) = \alpha\left(f'\left(\alpha^{-1}\left(\alpha(g'(\alpha^{-1}(x))))\right)\right)\right) = \alpha(f' \circ g'(\alpha^{-1}(x))) = \beta(f' \circ g')(x) $$

for all $x \in R$, so that $\beta(f') \circ \beta(g') \in O$.

Then $(R, O)$ is an Ext-algebra, because for all $r' \in R_L$, we have

$$ \beta(\text{left}_{r'})(x) = \alpha(\text{left}_{r'}(\alpha^{-1}(x))) = \alpha(\alpha^{-1}(\alpha(r'))\alpha^{-1}(x)) = \alpha(r') \cdot x = \text{left}_{\alpha(r')}(x) $$

for all $x \in R$ and $\beta(\text{right}_{r'})(x) = \text{right}_{\alpha(r')}(x)$ for all $x \in R$, so that $\text{left}_r, \text{right}_r \in O$ for all $r \in R$ by surjectivity of $\alpha$.

We now define $(\varphi, \psi) : (\Sigma^\Delta, \mathcal{O}(\Sigma^\Delta)) \to (R, O)$ as the unique morphism satisfying $\varphi(c) = \alpha(\varphi_L(c))$ for all $c \in \Sigma_{\text{int}}$ and $\psi(\text{ext}_{a,b}) = \beta(\psi_L(\text{ext}_{a,b}))$ for all $a \in \Sigma_{\text{call}}, b \in \Sigma_{\text{ret}}$ given by Proposition 3.7. It is easy to show that then, $\varphi(w) = \alpha(\varphi_L(w))$ for all $w \in \Sigma^\Delta$ by structural induction on $w$. Hence, by injectivity of $\alpha$, we have

$$ \begin{aligned} \varphi^{-1}(\alpha(\varphi_L(L))) &= \{w \in \Sigma^\Delta \mid \alpha(\varphi_L(w)) \in \alpha(\varphi_L(L))\} \\ &= \{w \in \Sigma^\Delta \mid \varphi_L(w) \in \varphi_L(L)\} = \varphi_L^{-1}(\varphi_L(L)) = L, \end{aligned} $$

thus $(R, O)$ recognizes $L$. $\square$

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

**Decidability of quasi-aperiodicity.** This paragraph is devoted to proving Point 2 (a) of Proposition 5.1, rephrased in the following proposition.

**Proposition 6.3.** Given a morphism $(\varphi, \psi) : (\Sigma^\Delta, \mathcal{O}(\Sigma^\Delta)) \to (R, O)$ for $\Sigma$ a visibly pushdown alphabet and $(R, O)$ a finite Ext-algebra, it is decidable if $(\varphi, \psi)$ is quasi-aperiodic. If $(\varphi, \psi)$ is not quasi-aperiodic, one can effectively compute $k, l \in \mathbb{N}$ such that $\psi(\mathcal{O}(\Sigma^\Delta)^{k,l})$ is not aperiodic.

For the rest of this paragraph, let us fix a morphism $(\varphi, \psi) : (\Sigma^\Delta, \mathcal{O}(\Sigma^\Delta)) \to (R, O)$, where $\Sigma$ is a visibly pushdown alphabet and $(R, O)$ is some finite Ext-algebra that is the input to our problem. We first have the following lemma.

**Lemma 6.4.** For all $e \in O$ one can effectively compute a finite Ext-algebra recognizing $L_e = \{u \# v \mid uv \in \Sigma^\Delta : \psi(\text{ext}_{u,v}) = e\}$, where $\#$ is a fresh internal letter that does not appear in $\Sigma$, along with an associated morphism and subset.

*Proof.* Let $\Sigma'$ be the alphabet that emerges from $\Sigma$ by additionally declaring $\#$ as an internal letter. We will construct an Ext-algebra $(R', O')$ and a morphism $(\varphi', \psi') : (\Sigma'^\Delta, \mathcal{O}(\Sigma'^\Delta)) \to (R', O')$ such that for some element $r' \in R'$ we have $L_e = \varphi'^{-1}(r')$.

We define $R' = R \cup O \cup \{\perp\}$, for some fresh zero $\perp$, where multiplication between two elements in $R'$ is defined as follows:

• multiplication between two elements in $R$ is inherited from the monoid $R$;

• $r \cdot f = \text{left}_r \circ f$ and $f \cdot r = \text{right}_r \circ f$ for all $r \in R$ and all $f \in O$;

• $\perp$ acts as a zero, i.e. $\perp \cdot r' = r' \cdot \perp = \perp$ for all $r' \in R'$;

• $f \cdot g = \perp$ for all $f, g \in O$.
Clearly the identity of $R$ is the identity of $R'$. Associativity is immediate except for products of the form $r_1 \cdot f \cdot r_2, r_1 \cdot r_2 \cdot f$, and $f \cdot r_1 \cdot r_2$, where $f \in O$ and $r_1, r_2 \in R$. In the first case we have

$$ (r_1 \cdot f) \cdot r_2 = (\mathrm{left}_{r_1} \circ f) \cdot r_2 = \mathrm{right}_{r_2} \circ (\mathrm{left}_{r_1} \circ f) = (\mathrm{right}_{r_2} \circ \mathrm{left}_{r_1}) \circ f \\ = (\mathrm{left}_{r_1} \circ \mathrm{right}_{r_2}) \circ f = r_1 \cdot (\mathrm{right}_{r_2} \circ f) = r_1 \cdot (f \cdot r_2). $$

In the second case we have

$$ (r_1 \cdot r_2) \cdot f = \mathrm{left}_{r_1 r_2} \circ f = (\mathrm{left}_{r_1} \circ \mathrm{left}_{r_2}) \circ f = \mathrm{left}_{r_1} \circ (\mathrm{left}_{r_2} \circ f) = r_1 \cdot (r_2 \cdot f) $$

and in the third case we have

$$ f \cdot (r_1 \cdot r_2) = \mathrm{right}_{r_1 r_2} \circ f = (\mathrm{right}_{r_2} \circ \mathrm{right}_{r_1}) \circ f = \mathrm{right}_{r_2} \circ (\mathrm{right}_{r_1} \circ f) = (f \cdot r_1) \cdot r_2. $$

We define $O' = (R')^{R'}$ which is clearly a monoid for composition and thus directly get that $(R', O')$ is an Ext-algebra. Applying Proposition 3.7, we define the morphism $(\varphi', \psi')$: $(\Sigma'^{\Delta}, \mathcal{O}(\Sigma')^{\Delta}) \to (R', O')$ as the unique one satisfying $\varphi'(c) = \varphi(c)$ for all $c \in \Sigma_{\mathrm{int}}$, $\varphi'(\#) = \mathrm{id}_O$ and where for all $a \in \Sigma_{\mathrm{call}}, b \in \Sigma_{\mathrm{ret}}$, we have

$$ \psi'(\mathrm{ext}_{a,b})(x) = \begin{cases} \psi(\mathrm{ext}_{a,b})(x) & \text{if } x \in R \\ \psi(\mathrm{ext}_{a,b}) \circ x & \text{if } x \in O \\ \perp & \text{otherwise (i.e. if } x = \perp) \end{cases} $$

for all $x \in R'$. It suffices to prove the following claim, which directly implies the desired equality $\varphi'^{-1}(e) = \{u \# v \mid uv \in \Sigma^{\Delta} \text{ s.t. } \psi(\mathrm{ext}_{u,v}) = e\}$. For all $w \in \Sigma'^{\Delta}$ we have

$$ \varphi'(w) = \begin{cases} \varphi(w) & \text{if } w \in \Sigma^{\Delta} \\ \psi(\mathrm{ext}_{u,v}) & \text{if } w = u \# v \text{ for some } uv \in \Sigma^{\Delta} \\ \perp & \text{otherwise.} \end{cases} $$

We prove it by structural induction on $w$. The cases when $w = \varepsilon$ or $w = c \in \Sigma_{\mathrm{int}}$ follow immediately from the definition of $\varphi'$. In case $w = \# = \varepsilon \# \varepsilon$, we have $\varphi'(w) = \mathrm{id}_O = \psi(\mathrm{ext}_{\varepsilon,\varepsilon})$.

For the inductive step first assume $w = aw'b$ for some $w' \in \Sigma'^{\Delta}$. If $w'$ is neither in $\Sigma^{\Delta}$ nor of the form $u \# v$ with $uv \in \Sigma^{\Delta}$, then $\varphi'(w') = \perp$ by induction hypothesis and thus $\varphi'(w) = \psi'(\mathrm{ext}_{a,b})(\varphi'(w')) = \psi'(\mathrm{ext}_{a,b})(\perp) = \perp$ as required. If $w' \in \Sigma^{\Delta}$, then $\varphi'(w') = \varphi(w') \in R$ by induction hypothesis, and hence $\varphi'(w) = \psi'(\mathrm{ext}_{a,b})(\varphi'(w')) = \psi'(\mathrm{ext}_{a,b})(\varphi(w')) = \varphi(w)$ as required. If $w' = u \# v$ with $uv \in \Sigma^{\Delta}$, i.e. $w = au \# vb$, then $\varphi'(w') = \psi(\mathrm{ext}_{u,v}) \in O$ by induction hypothesis. Hence, we have $\varphi'(w) = \psi'(\mathrm{ext}_{a,b})(\varphi'(w')) = \psi'(\mathrm{ext}_{a,b})(\psi(\mathrm{ext}_{u,v})) = \psi(\mathrm{ext}_{a,b}) \circ \psi(\mathrm{ext}_{u,v}) = \psi(\mathrm{ext}_{au,vb})$.

Finally assume $w = xy$ for some $x, y \in \Sigma'^{\Delta} \setminus \{\varepsilon\}$. The case when $x$ or $y$ is neither in $\Sigma^{\Delta}$ nor of the form $u \# v$ with $uv \in \Sigma^{\Delta}$ is easily handled by applying the induction hypothesis and observing that $\perp$ is a zero in $R'$. Two other immediate cases are when both $x$ and $y$ are in $\Sigma^{\Delta}$ and when both $x$ and $y$ are of the form $u \# v$ with $uv \in \Sigma^{\Delta}$. Consider the case when $x \in \Sigma^{\Delta} \setminus \{\varepsilon\}$ and $y = u \# v$ with $uv \in \Sigma^{\Delta}$, hence $w = xu \# v$. The induction hypothesis yields $\varphi'(x) = \varphi(x) \in R$ and $\varphi'(y) = \psi(\mathrm{ext}_{u,v}) \in O$. We obtain

$$ \varphi'(xy) = \varphi'(x) \cdot \varphi'(y) = \varphi(x) \cdot \psi(\mathrm{ext}_{u,v}) = \mathrm{left}_{\varphi(x)} \circ \psi(\mathrm{ext}_{u,v}) = \psi(\mathrm{ext}_{xu,v}) $$
as required. Finally, let us treat the case when $x = u#v$ with $uv \in \Sigma^\Delta$ and $y \in \Sigma^\Delta \setminus \{\varepsilon\}$, i.e. $w = u#vy$. The induction hypothesis yields $\varphi'(x) = \psi(\mathrm{ext}_{u,v}) \in O$ and $\varphi'(y) = \varphi(y) \in R$. We obtain

$$ \varphi'(xy) = \varphi'(x) \cdot \varphi'(y) = \psi(\mathrm{ext}_{u,v}) \cdot \varphi(y) = \mathrm{right}_{\varphi(y)} \circ \psi(\mathrm{ext}_{u,v}) = \psi(\mathrm{ext}_{u,v y}) $$

as required.

□

The next goal will be to prove that the set of pairs of word lengths ($|u|, |v|$) of words $u#v \in L_e$ is effectively semilinear for each $e \in O$.

A (realtime) pushdown automaton (PDA for short) is a tuple $A = (Q, \Sigma, \Gamma, \Omega, q_0, F, \perp)$, where $Q$ is a finite set of states, $\Sigma$ is a finite input alphabet, $\Gamma$ is a finite stack alphabet, $q_0 \in Q$ is an initial state, $F \subseteq Q$ is the set of final states, $\perp \in \Gamma \setminus \Sigma$ is the bottom-of-stack symbol, and $\Omega \subseteq Q \times \Sigma \times \Gamma \times Q \times \Gamma^*$ is a finite transition relation such that for all $(p, a, X, q, \alpha) \in \Omega$ we have $\alpha \in \Gamma^* \perp$ if $X = \perp$ and $\alpha \in (\Gamma \setminus \{\perp\})^*$ otherwise. The relation $\Omega$ is naturally extended to the relation $\Omega^* \subseteq Q \times \Sigma^* \times \Gamma^* \perp \times Q \times \Gamma^* \perp$, namely as the smallest relation containing the set $\{(p, \varepsilon, \alpha, p, \alpha) \mid p \in Q, \alpha \in \Gamma^* \perp\}$ and such that moreover, if $(p, a, X, q, \alpha) \in \Omega$ and $(q, w, \alpha\beta, r, \gamma) \in \Omega^*$, then $(p, aw, X\beta, r, \gamma) \in \Omega^*$. The language of $A$ is $L(A) = \{w \in \Sigma^* \mid \exists \alpha \in \Gamma^* \perp, \exists q \in F : (q_0, w, \perp, q, \alpha) \in \Omega^*\}$. Hence it is clear that one can compute a PDA $A'$ such that $L(A') = L(A)$.

**Lemma 6.5.** Let $A$ be a DVPA that accepts a language over a visibly pushdown alphabet $\Sigma'$ such that $L(A) \subseteq \{u#v \mid uv \in \Sigma'^\Delta \setminus \Sigma'^* \# \Sigma'^*\}$ and $\# \in \Sigma'_{int}$. Then the set

$$ P(L(A)) = \{(k,l) \in \mathbb{N} \times \mathbb{N} \mid \exists u \in (\Sigma' \setminus \{\#\})^k, v \in (\Sigma' \setminus \{\#\})^l : u#v \in L(A)\} $$

is effectively semilinear.

*Proof.* We first compute a PDA $A'$ accepting the same language as $A$, i.e. $L(A') = L(A)$. Let us assume without loss of generality that $0, 1 \notin \Sigma'$. We claim that from $A' = (Q, \Sigma', \Gamma, \Omega, q_0, F, \perp)$ one can compute a PDA $A''$ such that

$$ L(A'') = \{0^{|u|} \# 1^{|v|} \mid u#v \in L(A')\}. $$

Indeed, the PDA $A''$ can simply be computed as follows: we set

$$ A'' = (Q \times \{0,1\}, \{0,1,\#\}, \Gamma, \Omega', \langle q_0, 0 \rangle, F \times \{1\}, \perp), $$

where $\Omega'$ is the union of $\{(\langle p, i \rangle, i, X, \langle q, i \rangle, \alpha) \mid i \in \{0,1\}, \exists c \in \Sigma' \setminus \{\#\} : (p, c, X, q, \alpha) \in \Omega\}$ and $\{(\langle p, 0 \rangle, \#X, \langle q, 1 \rangle, \alpha) \mid (p, \#X, q, \alpha) \in \Omega\}$. Finally, we apply Parikh's Theorem, cf. [14, Section 3], which implies that the set $\{(m,n) \in \mathbb{N} \times \mathbb{N} \mid 0^m \# 1^n \in L(A'')\} = P(L(A))$ is effectively semilinear. □

We are now ready to prove Proposition 6.3.

*Proof of Proposition 6.3.* Let $e \in O$. By Lemma 6.4 we first compute a finite Ext-algebra recognizing $L_e$, along with an associated morphism and subset. From the latter we can compute (by Theorem 3.18) a DVPA $A_e$ accepting $L_e$. We then use Lemma 6.5 to conclude that the set

$$ P(L_e) = \{(k,l) \in \mathbb{N} \times \mathbb{N} \mid \exists u \in \Sigma^k, v \in \Sigma^l : uv \in \Sigma^\Delta, \psi(\mathrm{ext}_{u,v}) = e\} $$

is effectively semilinear, and this holds for all $e \in O$.

We make use of the folklore fact that semilinear sets are effectively closed under Boolean operations, cf. [9] for a recent study. To decide whether $(\varphi, \psi)$ is quasi-aperiodic, we go through all
possible subsets $U \subseteq O$: if it is a subsemigroup of $O$ that is a non-trivial group, we compute the set $\bigcap_{e \in U} P(L_e)$ and reject if it is non-empty (which is easy to check given a semilinear presentation of the set), otherwise we continue. If we were able to go through all those subsets without rejecting, we accept.

Thus, if $(\varphi, \psi)$ is not quasi-aperiodic we can find a subset $U \subseteq O$ that contains a non-trivial group and output a pair $(k, l) \in \bigcap_{e \in U} P(L_e)$; it witnesses that $\psi(\mathcal{O}(\Sigma^\Delta)^{k,l})$ is not aperiodic. $\square$

**Decidability of length-synchronicity.** This paragraph is devoted to proving Point 2 (b) of Proposition 5.1, rephrased in the following proposition.

**Proposition 6.6.** Given a morphism $(\varphi, \psi) : (\Sigma^\Delta, \mathcal{O}(\Sigma^\Delta)) \to (R, O)$, for $\Sigma$ a visibly pushdown alphabet and $(R, O)$ a finite Ext-algebra, and some $F \subseteq R$, it is decidable if $(\varphi, \psi)$ is $F$-length-synchronous. If $(\varphi, \psi)$ is not length-synchronous, one can effectively compute a tuple $(k, l, k', l') \in \mathbb{N}^4_{>0}$ such that there exist $uv, u'v' \in \Sigma^\Delta$ and some $F$-reachable idempotent $e \in O$ such that $\psi(\mathrm{ext}_{u,v}) = \psi(\mathrm{ext}_{u',v'}) = e$, $k = |u|$, $l = |v|$, $k' = |u'|$, $l' = |v'|$ and $\frac{k}{l} \neq \frac{k'}{l'}$.

Before proving the proposition we need a technical lemma characterizing when a two-dimensional semilinear set contains only vectors with the same slope. We say two vectors $\vec{x}, \vec{y} \in \mathbb{N}^2$ are collinear if $\vec{y} = \alpha \cdot \vec{x}$ for some $\alpha \in \mathbb{Q}_{>0}$

**Lemma 6.7.** Let $S = \bigcup_{i \in I} (\vec{x}_{i,0} + \sum_{j=1}^{t_i} \mathbb{N}\vec{x}_{i,j}) \subseteq \mathbb{N}^2_{>0}$ be a non-empty semilinear set, where $\vec{x}_{i,j} \neq (0,0)$ for all $i \in I$ and all $j \in [0, t_i]$. Then,

$$ \left| \left\{ \frac{k}{l} \middle| (k, l) \in S \right\} \right| = 1 \iff \forall i, i' \in I \ \forall j \in [0, t_i] \ \forall j' \in [0, t_{i'}) : \vec{x}_{i,j} \text{ and } \vec{x}_{i',j'} \text{ are collinear.} $$

*Proof.* First assume that $\vec{x}_{i,j}$ and $\vec{x}_{i',j'}$ are collinear for all $i, i' \in I$, $j \in [0, t_i]$, and $j' \in [0, t_{i'}]$. Let $(k, l), (k', l') \in S$. That is, $(k, l) = \vec{x}_{i,0} + n_1\vec{x}_{i,1} + \cdots + n_{t_i}\vec{x}_{i,t_i}$ and $(k', l') = \vec{x}_{i',0} + n'_1\vec{x}_{i',1} + \cdots + n'_{t_{i'}}\vec{x}_{i',t_{i'}}$ for some $i, i' \in I$ and some $n_1, \dots, n_{t_i}, n'_1, \dots, n'_{t_{i'}} \in \mathbb{N}$. But due to pairwise collinearity there exist $\alpha, \alpha' \in \mathbb{Q}_{>0}$ such that $(k, l) = \alpha\vec{x}_{i,0}$ and $(k', l') = \alpha'\vec{x}_{i,0}$, thus implying $\frac{k}{l} = \frac{k'}{l'}$.

Conversely assume that there exist two vectors $(k, l) = \vec{x}_{i,j}$ and $(k', l') = \vec{x}_{i',j'}$ that are not collinear. In case this is possible when $i \neq i'$ and $j = j' = 0$ we are done, since then $(k, l), (k', l') \in S$ and thus $\frac{k}{l} \neq \frac{k'}{l'}$. Otherwise $\vec{x}_{i,0}$ and $\vec{x}_{i',0}$ are collinear for all $i, i' \in I$, so there must exist $i \in I$ and $j \in [0, t_i]$ such that $\vec{x}_{i,0}$ and $\vec{x}_{i,j}$ are not collinear. Then $\vec{x}_{i,0}$ and $\vec{x}_{i,0} + \vec{x}_{i,j}$ are in $S$ but also not collinear: indeed, if $\alpha\vec{x}_{i,0} = \vec{x}_{i,0} + \vec{x}_{i,j}$ for some $\alpha \in \mathbb{Q}_{>0}$, then $\vec{x}_{i,j} = (\alpha - 1)\vec{x}_{i,0}$ with $\alpha - 1 > 0$ due to $\vec{x}_{i,0}, \vec{x}_{i,j} \in \mathbb{N}^2 \setminus \{(0,0)\}$, a contradiction. Hence there exist $(k, l), (k', l') \in S$ that are not collinear, and therefore $\frac{k}{l} \neq \frac{k'}{l'}$. $\square$

*Proof of Proposition 6.6.* Let us fix the Ext-algebra morphism $(\varphi, \psi) : (\Sigma^\Delta, \mathcal{O}(\Sigma^\Delta)) \to (R, O)$, where $(R, O)$ is a finite Ext-algebra and where $F \subseteq R$.

Recall that over the alphabet $\Sigma'$, obtained from $\Sigma$ by declaring a fresh letter $\#$ as internal, the language

$$ L_{e\uparrow} = \{u\#v \mid uv \in \Sigma^\Delta : \Delta(u) > 0, \psi(\mathrm{ext}_{u,v}) = e\} = L_e \cap \{u\#v \mid uv \in \Sigma^\Delta : \Delta(u) > 0\} $$

is given for all $e \in O$. The language $\{u\#v \mid uv \in \Sigma^\Delta : \Delta(u) > 0\}$ is a clearly a VPL. Thus, for all $e \in O$, we have that the set

$$ P(L_{e\uparrow}) = \{ (k, l) \in \mathbb{N} \times \mathbb{N} \mid \exists u \in \Sigma^k, v \in \Sigma^l : uv \in \Sigma^\Delta, \Delta(u) > 0, \psi(\mathrm{ext}_{u,v}) = e \} $$
is effectively semilinear: indeed, given $e \in O$, using Lemma 6.4 and Theorem 3.18, we can as in the proof of Point 2 (a) of Proposition 5.1 compute a DVPA $A_e$ accepting $L_e$; we then compute a DVPA $A_{e\uparrow}$ accepting $L_{e\uparrow} = L(A_e) \cap L(A)$ by using the effective construction given in [2] and finally use Lemma 6.5 to conclude.

Observe that $(\varphi, \psi)$ is $F$-length-synchronous if, and only if, for each $F$-reachable idempotent $e \in O$ for which $P(L_{e\uparrow})$ is non-empty we have $|\{\frac{k}{l} | (k,l) \in P(L_{e\uparrow})\}| = 1$. The latter condition is easily seen to be decidable by the characterization provided in Lemma 6.7. Hence, for deciding if $(\varphi, \psi)$ is length-synchronous our algorithm verifies if for all $F$-reachable $e \in O$ for which $P(L_{e\uparrow})$ is non-empty we have $|\{\frac{k}{l} | (k,l) \in P(L_{e\uparrow})\}| = 1$. On the other hand, if this verification fails, i.e. in case $(\varphi, \psi)$ is not $F$-length-synchronous, our algorithm outputs, again using the characterization of Lemma 6.7, a quadruple $(k, l, k', l') \in \mathbb{N}_{>0}^4$ such that for some $F$-reachable idempotent $e \in O$ we have $(k, l), (k', l') \in P(L_{e\uparrow})$ and $\frac{k}{l} \neq \frac{k'}{l'}$. $\square$

**Decidability of weak length-synchronicity.** This paragraph is devoted to proving Point 2 (c) of Proposition 5.1, rephrased in the following proposition.

**Proposition 6.8.** Given a morphism $(\varphi, \psi): (\Sigma^\Delta, \mathcal{O}(\Sigma^\Delta)) \to (R, O)$, for $\Sigma$ a visibly pushdown alphabet and $(R, O)$ a finite Ext-algebra, and some $F \subseteq R$, it is decidable if $(\varphi, \psi)$ is $F$-weakly-length-synchronous.

Let us fix the morphism $(\varphi, \psi): (\Sigma^\Delta, \mathcal{O}(\Sigma^\Delta)) \to (R, O)$, for $\Sigma$ a visibly pushdown alphabet and $(R, O)$ a finite Ext-algebra, and some $F \subseteq R$.

Define the new visibly pushdown alphabet $\bar{\Sigma}$ by $\bar{\Sigma}_{\text{call}} = \{\bar{b} | b \in \Sigma_{\text{ret}}\}$, $\bar{\Sigma}_{\text{int}} = \{\bar{c} | c \in \Sigma_{\text{int}}\}$ and $\bar{\Sigma}_{\text{ret}} = \{\bar{a} | a \in \Sigma_{\text{call}}\}$. For all $w \in \Sigma^*$, we define

$$ \bar{w} = \begin{cases} \varepsilon & \text{if } w = \varepsilon \\ \bar{w}_n \cdots \bar{w}_1 & \text{if } w = w_1 \cdots w_n \text{ for } n \in \mathbb{N}_{>0} \text{ and } w_1, \ldots w_n \in \Sigma. \end{cases} $$

We have the following lemma, that we prove later on.

**Lemma 6.9.** For all $e \in O$ one can effectively compute a finite Ext-algebra recognizing the language of well-matched words $K_e = \{u\#u' | u, u' \in \Sigma^*, \exists v \in \Sigma^* : uv \in \Sigma^\Delta, u'v \in \Sigma^\Delta, \psi(\text{ext}_{u,v}) = \psi(\text{ext}_{u',v}) = e\}$, where $\#$ is a fresh internal letter that does not appear in $\Sigma \cup \bar{\Sigma}$, along with an associated morphism and subset.

Over the alphabet $\Sigma'$ obtained from $\Sigma \cup \bar{\Sigma}$ by declaring the fresh letter $\#$ as internal, we define

$$ K_{e\uparrow} = \left\{ \begin{array}{l} u\#\bar{u}' \quad \begin{array}{l} | \quad u, u' \in \Sigma^*, \exists v \in \Sigma^* : \\ uv \in \Sigma^\Delta, u'v \in \Sigma^\Delta, \Delta(u) > 0, \psi(\text{ext}_{u,v}) = \psi(\text{ext}_{u',v}) = e \end{array} \end{array} \right\} \\ \\ = K_e \cap \{u\#u' | uu' \in (\Sigma \cup \bar{\Sigma})^\Delta : \Delta(u) > 0\} $$

for all $e \in O$. As in the proof of Point (2) of the second statement of Proposition 5.1, we can prove that the language $\{u\#u' | uu' \in (\Sigma \cup \bar{\Sigma})^\Delta : \Delta(u) > 0\}$ is a VPL and thus conclude that for all $e \in O$, the set

$$ P(K_{e\uparrow}) = \left\{ (k,l) \in \mathbb{N} \times \mathbb{N} \mid \exists u \in \Sigma^k, u' \in \Sigma^l, v \in \Sigma^* : uv \in \Sigma^\Delta, u'v \in \Sigma^\Delta, \Delta(u) > 0, \psi(\text{ext}_{u,v}) = \psi(\text{ext}_{u',v}) = e \right\} $$

is effectively semilinear.
It is clear that $(\varphi, \psi)$ is $F$-weakly-length-synchronous if and only if for each idempotent $e \in O$ that is $F$-reachable, there does not exist any $(x_1, x_2) \in P(K_{e\uparrow})$ such that $x_1 \neq x_2$. Therefore, to decide whether $(\varphi, \psi)$ is $F$-weakly-length-synchronous, we go through all $e \in O$: if $e$ is an idempotent that is $F$-reachable, we compute the set $P(K_{e\uparrow})$ and reject if it contains a vector $(x_1, x_2)$ such that $x_1 \neq x_2$ (which is easy to check given a semilinear presentation of the set), otherwise we continue. Finally, if we were able to go through all those elements without rejecting, we accept.

*Proof of Lemma 6.9.* Let $\Sigma'$ be the alphabet that emerges from $\Sigma \cup \bar{\Sigma}$ by additionally declaring # as an internal letter. We will construct an Ext-algebra $(R', O')$ and a morphism $(\varphi', \psi')$ from $(\Sigma'^{\Delta}, \mathcal{O}(\Sigma')^{\Delta})$ to $(R', O')$ such that for some subset $F \subseteq R'$ we have $K_e = \varphi'^{-1}(F)$.

Let $\bar{R} = \{\bar{r} \mid r \in R\}$. We define $R' = R \cup \bar{R} \cup \mathfrak{P}(O^2) \setminus \emptyset \cup \{\perp, 1\}$, for some fresh zero $\perp$ and identity 1, where multiplication between two elements in $R'$ is defined as follows:

* for all $r_1, r_2 \in R$,

$$ \begin{aligned} r_1 \cdot r_2 &= r_1 r_2 & \bar{r}_1 \cdot r_2 &= \perp \\ \bar{r}_1 \cdot \bar{r}_2 &= \bar{r}_2 \bar{r}_1 & r_1 \cdot \bar{r}_2 &= \perp; \end{aligned} $$

* for all $r \in R$ and $E \in \mathfrak{P}(O^2) \setminus \emptyset$,

$$ \begin{aligned} r \cdot E &= \{(\mathrm{left}_r \circ e_1, e_2) \mid (e_1, e_2) \in E\} & E \cdot r &= \perp \\ E \cdot \bar{r} &= \{(e_1, \mathrm{left}_r \circ e_2) \mid (e_1, e_2) \in E\} & \bar{r} \cdot E &= \perp; \end{aligned} $$

* for all $E_1, E_2 \in \mathfrak{P}(O^2) \setminus \emptyset$, we have $E_1 \cdot E_2 = \perp$;

* $\perp$ acts as a zero, i.e. $\perp \cdot r' = r' \cdot \perp = \perp$ for all $r' \in R'$;

* 1 acts as an identity, i.e. $1 \cdot r' = r' \cdot 1 = r'$ for all $r' \in R'$.

Associativity is immediate except for products of the form $\bar{r}_1 \cdot \bar{r}_2 \cdot \bar{r}_3$, $r_1 \cdot E \cdot \bar{r}_2$, $r_1 \cdot r_2 \cdot E$ and $E \cdot \bar{r}_1 \cdot \bar{r}_2$, where $E \in \mathfrak{P}(O^2) \setminus \emptyset$ and $r_1, r_2, r_3 \in R$. In the first case we have

$$ (\bar{r}_1 \cdot \bar{r}_2) \cdot \bar{r}_3 = \bar{r}_2 \bar{r}_1 \cdot \bar{r}_3 = \bar{r}_3 \bar{r}_2 \bar{r}_1 = \bar{r}_1 \cdot \bar{r}_3 \bar{r}_2 = \bar{r}_1 \cdot (\bar{r}_2 \cdot \bar{r}_3). $$

In the second case we have

$$ \begin{aligned} (r_1 \cdot E) \cdot \bar{r}_2 &= \{(\mathrm{left}_{r_1} \circ e_1, e_2) \mid (e_1, e_2) \in E\} \cdot \bar{r}_2 \\ &= \{(\mathrm{left}_{r_1} \circ e_1, \mathrm{left}_{r_2} \circ e_2) \mid (e_1, e_2) \in E\} \\ &= r_1 \cdot \{(e_1, \mathrm{left}_{r_2} \circ e_2) \mid (e_1, e_2) \in E\} = r_1 \cdot (E \cdot \bar{r}_2). \end{aligned} $$

In the third case we have

$$ \begin{aligned} (r_1 \cdot r_2) \cdot E &= \{(\mathrm{left}_{r_1 r_2} \circ e_1, e_2) \mid (e_1, e_2) \in E\} \\ &= \{(\mathrm{left}_{r_1} \circ \mathrm{left}_{r_2} \circ e_1, e_2) \mid (e_1, e_2) \in E\} \\ &= r_1 \cdot \{(\mathrm{left}_{r_2} \circ e_1, e_2) \mid (e_1, e_2) \in E\} = r_1 \cdot (r_2 \cdot E) \end{aligned} $$
and in the fourth case we have

$$
\begin{align*}
E \cdot (\bar{r}_1 \cdot \bar{r}_2) &= \{(e_1, \text{left}_{r_2 r_1} \circ e_2) \mid (e_1, e_2) \in E\} \\
&= \{(e_1, \text{left}_{r_2} \circ \text{left}_{r_1} \circ e_2) \mid (e_1, e_2) \in E\} \\
&= \{(e_1, \text{right}_{r_1} \circ e_2) \mid (e_1, e_2) \in E\} \cdot \bar{r}_2 = (E \cdot \bar{r}_1) \cdot \bar{r}_2.
\end{align*}
$$

We define $O' = (R')^{R'}$ which is clearly a monoid for composition and thus directly get that $(R', O')$ is a finite Ext-algebra. Applying Proposition 3.7, we define the morphism $(\varphi', \psi')$: $(\Sigma'^{\Delta}, \mathcal{O}(\Sigma')^{\Delta}) \to (R', O')$ as the unique one satisfying $\varphi'(c) = \varphi(c)$ and $\varphi'(\bar{c}) = \bar{\varphi}(c)$ for all $c \in \Sigma_{\text{int}}$, $\varphi'(\#) = \{(\psi(\text{ext}_{\varepsilon,v}), \psi(\text{ext}_{\bar{\varepsilon},v})) \mid v \in \Sigma^{\Delta}\}$ and where for all $a, a' \in \Sigma_{\text{call}}, b, b' \in \Sigma_{\text{ret}}$, we have

$$
\begin{align*}
\psi'(\text{ext}_{a,b})(x) &= \begin{cases} \psi(\text{ext}_{a,b})(1_R) & \text{if } x = 1 \\ \psi(\text{ext}_{a,b})(x) & \text{if } x \in R \\ \bot & \text{otherwise} \end{cases} \\
\psi'(\text{ext}_{\bar{b}',\bar{a}'})(x) &= \begin{cases} \frac{\psi(\text{ext}_{a',b'})(1_R)}{\psi(\text{ext}_{a',b'})(x')} & \text{if } x = 1 \\ \psi(\text{ext}_{a',b'})(x') & \text{if } x = \bar{x}' \text{ for } x' \in R \\ \bot & \text{otherwise} \end{cases} \\
\psi'(\text{ext}_{a,\bar{a}'})(x) &= \left\{ \begin{array}{ll} \bigcup_{b \in \Sigma_{\text{ret}}} \{(\psi(\text{ext}_{a,bz}) \circ e_1, \psi(\text{ext}_{a',bz}) \circ e_2)\} & \text{if } x \in \mathfrak{P}(O^2) \setminus \emptyset \\ \bot & \text{otherwise} \end{array} \right. \\
\psi'(\text{ext}_{\bar{b}',\bar{b}})(x) &= \bot
\end{align*}
$$

for all $x \in R'$. Note that $(\varphi', \psi')$ is computable because

$$
\{ (\psi(\text{ext}_{\varepsilon,v}), \psi(\text{ext}_{\bar{\varepsilon},v})) \mid v \in \Sigma^{\Delta} \} &= \{ (\text{right}_{\varphi(v)}, \text{right}_{\bar{\varphi}(v)}) \mid v \in \Sigma^{\Delta} \} \\
&= \{ (\text{right}_r, \text{right}_r) \mid r \in R \}
$$

and

$$
\begin{align*}
& \bigcup_{\substack{b \in \Sigma_{\text{ret}} \\ z \in \Sigma^{\Delta} \\ (e_1, e_2) \in x}} \{(\psi(\text{ext}_{a,bz}) \circ e_1, \psi(\text{ext}_{a',bz}) \circ e_2)\} \\
&= \bigcup_{\substack{b \in \Sigma_{\text{ret}} \\ z \in \Sigma^{\Delta} \\ (e_1, e_2) \in x}} \{(\text{right}_{\varphi(z)} \circ \psi(\text{ext}_{a,b}) \circ e_1, \text{right}_{\bar{\varphi}(z)} \circ \psi(\text{ext}_{a',b}) \circ e_2)\} \\
&= \bigcup_{\substack{b \in \Sigma_{\text{ret}} \\ r \in R \\ (e_1, e_2) \in x}} \{(\text{right}_r \circ \psi(\text{ext}_{a,b}) \circ e_1, \text{right}_r \circ \psi(\text{ext}_{a',b}) \circ e_2)\}
\end{align*}
$$

for all $x \in \mathfrak{P}(O^2) \setminus \emptyset$ and $a, a' \in \Sigma_{\text{call}}$.

Now define the set of pairs $P = \{(u, u') \in \Sigma^* \times \Sigma^* \mid \exists v \in \Sigma^* : uv \in \Sigma^\Delta, u'v \in \Sigma^\Delta\}$; it is not difficult to check that for all $w \in \Sigma'^*$, $w \in \Sigma'^\Delta \cap \Sigma^*\#\Sigma^*$ if and only if $w = u\#\overline{u'}$ for $(u, u') \in P$. It
suffices to prove the following claim, which directly implies the desired equality

$$
\begin{align*}
\varphi'^{-1}(\{E \in \mathfrak{P}(O^2) \setminus \emptyset \mid (e, e) \in E\})
&= \{u \# \overline{u'} \mid (u, u') \in P, \exists v \in \Sigma^* : uv \in \Sigma^\Delta, u'v \in \Sigma^\Delta, \psi(\mathrm{ext}_{u,v}) = \psi(\mathrm{ext}_{u',v}) = e\} \\
&= \{u \# \overline{u'} \mid u, u' \in \Sigma^*, \exists v \in \Sigma^* : uv \in \Sigma^\Delta, u'v \in \Sigma^\Delta, \psi(\mathrm{ext}_{u,v}) = \psi(\mathrm{ext}_{u',v}) = e\}.
\end{align*}
$$

For all $w \in \Sigma'^{\Delta}$ we have

$$
\varphi'(w) = \begin{cases}
1 & \text{if } w = \varepsilon \\
\frac{\varphi(w)}{\varphi(w')} & \text{if } w \in \Sigma^{\Delta} \setminus \{\varepsilon\} \\
\{(\psi(\mathrm{ext}_{u,v}), \psi(\mathrm{ext}_{u',v})) \mid v \in \Sigma^{*}, uv, u'v \in \Sigma^{\Delta}\} & \text{if } w = \overline{w'} \text{ for } w' \in \Sigma^{\Delta} \setminus \{\varepsilon\} \\
\perp & \text{otherwise.}
\end{cases}
$$

We prove it by structural induction on $w$. The cases when $w = \varepsilon$ or $w = c \in \Sigma_{\text{int}}$ or $w = \bar{c} \in \bar{\Sigma}_{\text{int}}$
follow immediately from the definition of $\varphi'$. In case $w = \# = \varepsilon\#\varepsilon$, we have

$$
\varphi'(w) = \{(\psi(\mathrm{ext}_{\varepsilon,v}), \psi(\mathrm{ext}_{\varepsilon,v})) \mid v \in \Sigma^{\Delta}\} = \{(\psi(\mathrm{ext}_{\varepsilon,v}), \psi(\mathrm{ext}_{\varepsilon,v})) \mid v \in \Sigma^{*}, \varepsilon v \in \Sigma^{\Delta}\}
$$

as required.

For the inductive step first assume $w = \alpha w' \beta$ for $w' \in \Sigma'^{\Delta}$, $\alpha \in \Sigma_{\text{call}} \cup \bar{\Sigma}_{\text{call}}$ and $\beta \in \Sigma_{\text{ret}} \cup \bar{\Sigma}_{\text{ret}}$.
If $w'$ is neither in $\Sigma^{\Delta} \cup \bar{\Sigma}^{\Delta}$ nor of the form $u \# \overline{u'}$ with $(u, u') \in P$, then $\varphi'(w') = \perp$ by induction
hypothesis and thus $\varphi'(w) = \psi'(\mathrm{ext}_{\alpha,\beta})(\varphi'(w')) = \psi'(\mathrm{ext}_{\alpha,\beta})(\perp) = \perp$ as required, since $w$ is also
neither in $\Sigma^{\Delta} \cup \bar{\Sigma}^{\Delta}$ nor of the form $u \# \overline{u'}$ with $(u, u') \in P$. If $w' = \varepsilon$, then $\varphi'(w') = 1$ and hence

$$
\begin{align*}
\varphi'(w) &= \psi'(\mathrm{ext}_{\alpha,\beta})(\varphi'(w')) \\
&= \psi'(\mathrm{ext}_{\alpha,\beta})(1) \\
&= \begin{cases}
\psi(\mathrm{ext}_{\alpha,\beta})(1_R) = \varphi(w) & \text{if } \alpha \in \Sigma_{\text{call}} \text{ and } \beta \in \Sigma_{\text{ret}} \\
\psi(\mathrm{ext}_{\alpha,b})(1_R) = \varphi(ab) & \text{if } \alpha = \bar{b} \in \bar{\Sigma}_{\text{call}} \text{ and } \beta = \bar{a} \in \bar{\Sigma}_{\text{ret}} \\
\perp & \text{otherwise}
\end{cases}
\end{align*}
$$

as required, because $w = \bar{b}\bar{a} = \overline{ab}$ in the second case. If $w' \in \Sigma^\Delta \setminus \{\varepsilon\}$, then $\varphi'(w') = \varphi(w') \in R$ by
induction hypothesis, and hence

$$
\varphi'(w) = \psi'(\mathrm{ext}_{\alpha,\beta})(\varphi'(w')) = \psi'(\mathrm{ext}_{\alpha,\beta})(\varphi(w')) \\
= \begin{cases}
\psi(\mathrm{ext}_{\alpha,\beta})(\varphi(w')) = \varphi(w) & \text{if } \alpha \in \Sigma_{\text{call}} \text{ and } \beta \in \Sigma_{\text{ret}} \\
\perp & \text{otherwise}
\end{cases}
$$

as required. If $w' \in \bar{\Sigma}^{\Delta} \setminus \{\varepsilon\}$, then $w' = \overline{w''}$ for $w'' \in \Sigma^{\Delta} \setminus \{\varepsilon\}$, so $\varphi'(w') = \overline{\varphi(w'')} \in \bar{R}$ by induction
hypothesis, and hence

$$
\begin{align*}
\varphi'(w) &= \psi'(\mathrm{ext}_{\alpha,\beta})(\varphi'(w')) \\
&= \psi'(\mathrm{ext}_{\alpha,\beta})(\overline{\varphi(w'')}) \\
&= \left\{
\begin{array}{ll}
\overline{\psi(\mathrm{ext}_{a,b})(\varphi(w''))} & = \overline{\varphi(aw''b)} & \text{if } \alpha = \bar{b} \in \bar{\Sigma}_{\mathrm{call}} \text{ and } \beta = \bar{a} \in \bar{\Sigma}_{\mathrm{ret}} \\
\perp & = & \text{otherwise}
\end{array}
\right.
\end{align*}
$$

as required, because $w = \bar{b}\overline{w''}\bar{a} = \overline{aw''b}$ in the first case. If $w' = u\#u'$ with $(u, u') \in P$, i.e. $w = \alpha u\#u'\beta$, then

$$
\varphi'(w') = \{(\psi(\mathrm{ext}_{u,v'}), \psi(\mathrm{ext}_{u',v'})) \mid v' \in \Sigma^*, uv', u'v' \in \Sigma^\Delta\} \in \mathfrak{P}(O^2) \setminus \emptyset
$$

by induction hypothesis. Hence, we have

$$
\begin{align*}
\varphi'(w) &= \psi'(\mathrm{ext}_{\alpha,\beta})(\varphi'(w')) \\
&= \psi'(\mathrm{ext}_{\alpha,\beta})\{(\psi(\mathrm{ext}_{u,v'}), \psi(\mathrm{ext}_{u',v'})) \mid v' \in \Sigma^*, uv', u'v' \in \Sigma^\Delta\}) \\
&= \bigcup_{\substack{b \in \Sigma_{\mathrm{ret}} \\ z \in \Sigma^\Delta}} \{(\psi(\mathrm{ext}_{au,v'bz}), \psi(\mathrm{ext}_{a'u',v'bz})) \mid v' \in \Sigma^*, uv', u'v' \in \Sigma^\Delta\} \\
&= \{(\psi(\mathrm{ext}_{au,v}), \psi(\mathrm{ext}_{a'u',v})) \mid v \in \Sigma^*, auv, a'u'v \in \Sigma^\Delta\}
\end{align*}
$$

if $\alpha = a \in \Sigma_{\text{call}}$ and $\beta = \bar{a}' \in \bar{\Sigma}_{\text{ret}}$ (where the last inclusion from right to left follows by considering
the unique stair factorizations given by Lemma 3.6 for the elements of each pair) and $\varphi'(w) = \perp$
otherwise, as required.

Finally assume $w = xy$ for some $x, y \in \Sigma^{\Delta} \setminus \{\varepsilon\}$. The case when $x$ or $y$ is neither in $\Sigma^{\Delta} \cup \bar{\Sigma}^{\Delta}$
nor of the form $u\#u'$ with $(u, u') \in P$ is easily handled by applying the induction hypothesis and
observing that $\perp$ is a zero in $R'$. Four other immediate cases are when both $x$ and $y$ are in $\Sigma^{\Delta}$,
when $x$ is in $\Sigma^{\Delta}$ and $y$ in $\bar{\Sigma}^{\Delta}$, when $x$ is in $\bar{\Sigma}^{\Delta}$ and $y$ in $\Sigma^{\Delta}$ and when both $x$ and $y$ are of the form
$u\#u'$ with $(u, u') \in P$. For the case when both $x$ and $y$ are in $\bar{\Sigma}^{\Delta}$, we have that $x = \bar{x}'$ and $y = \bar{y}'$
for $x', y' \in \Sigma^{\Delta}$, so that $\varphi'(x) = \overline{\varphi(x')} \in \bar{R}$ and $\varphi'(y) = \overline{\varphi(y')} \in \bar{R}$ by induction hypothesis, hence

$$
\varphi'(xy) = \varphi'(x) \cdot \varphi'(y) = \overline{\varphi(x')} \cdot \overline{\varphi(y')} = \overline{\varphi(y')\varphi(x')} = \overline{\varphi(y'x')}
$$

as required, because $xy = \overline{x'y'} = \overline{y'x'}$. Consider the case when $x \in (\Sigma^\Delta \cup \bar{\Sigma}^\Delta) \setminus \{\varepsilon\}$ and $y = u\#u'$ with $(u, u') \in P$, hence $w = xu\#u'$. The induction hypothesis yields

$$
\varphi'(x) = \begin{cases} \varphi(x) \in \mathbb{R} & \text{if } x \in \Sigma^\Delta \setminus \{\varepsilon\} \\ \overline{\varphi(x')} \in \bar{\mathbb{R}} & \text{if } x = \bar{x}' \text{ for } x' \in \Sigma^\Delta \setminus \{\varepsilon\} \end{cases}
$$

and $\varphi'(y) = \{(\psi(\mathrm{ext}_{u,v}), \psi(\mathrm{ext}_{u',v})) \mid v \in \Sigma^*, uv, u'v \in \Sigma^\Delta\} \in \mathfrak{P}(O^2) \setminus \emptyset$. We obtain

$$
\begin{align*}
\varphi'(w) &= \varphi'(x) \cdot \varphi'(y) \\
&= \varphi(x) \cdot \{(\psi(\mathrm{ext}_{u,v}), \psi(\mathrm{ext}_{u',v})) \mid v \in \Sigma^*, uv, u'v \in \Sigma^\Delta\} \\
&= \{(\mathrm{left}_{\varphi(x)} \circ \psi(\mathrm{ext}_{u,v}), \psi(\mathrm{ext}_{u',v})) \mid v \in \Sigma^*, uv, u'v \in \Sigma^\Delta\} \\
&= \{(\psi(\mathrm{ext}_{xu,v}), \psi(\mathrm{ext}_{u',v})) \mid v \in \Sigma^*, xuv, u'v \in \Sigma^\Delta\}
\end{align*}
$$
if $x \in \Sigma^\Delta \setminus \{\varepsilon\}$ and $\varphi'(w) = \overline{\varphi(x)} \cdot \{(\psi(\mathrm{ext}_{u,v}), \psi(\mathrm{ext}_{u',v})) \mid v \in \Sigma^*, uv, u'v \in \Sigma^\Delta\} = \perp$ if $x = \overline{x}'$ for $x' \in \Sigma^\Delta \setminus \{\varepsilon\}$, as required. Eventually, let us treat the case when $x = u\#u'$ with $(u, u') \in P$ and $y \in (\Sigma^\Delta \cup \overline{\Sigma^\Delta}) \setminus \{\varepsilon\}$, hence $w = u\#\overline{u'}y$. The induction hypothesis yields $\varphi'(x) = \{(\psi(\mathrm{ext}_{u,v}), \psi(\mathrm{ext}_{u',v})) \mid v \in \Sigma^*, uv, u'v \in \Sigma^\Delta\}$ if $y \in \Sigma^\Delta \setminus \{\varepsilon\}$.

$$ \begin{aligned} \varphi'(w) &= \varphi'(x) \cdot \varphi'(y) \\ &= \{(\psi(\mathrm{ext}_{u,v}), \psi(\mathrm{ext}_{u',v})) \mid v \in \Sigma^*, uv, u'v \in \Sigma^\Delta\} \cdot \overline{\varphi(y')} \\ &= \{(\psi(\mathrm{ext}_{u,v}), \mathrm{left}_{\varphi(y')}) \circ \psi(\mathrm{ext}_{u',v})) \mid v \in \Sigma^*, uv, u'v \in \Sigma^\Delta\} \\ &= \{(\psi(\mathrm{ext}_{u,v}), \psi(\mathrm{ext}_{y'u',v})) \mid v \in \Sigma^*, uv, y'u'v \in \Sigma^\Delta\} \end{aligned} $$

if $y = \overline{y'}$ for $y' \in \Sigma^\Delta \setminus \{\varepsilon\}$ and $\varphi'(w) = \{(\psi(\mathrm{ext}_{u,v}), \psi(\mathrm{ext}_{u',v})) \mid v \in \Sigma^*, uv, u'v \in \Sigma^\Delta\} \cdot \varphi(y) = \perp$ if $x \in \Sigma^\Delta \setminus \{\varepsilon\}$, as required, because $\overline{y'u'} = \overline{u'}\overline{y'}$ in the first case. $\square$

# 7 Conclusion

In this paper we have studied the question which visibly pushdown languages lie in the complexity class $\mathbf{AC}^0$.

We have introduced the notions of length-synchronicity, weak length-synchronicity and quasi-counterfreeness. We have introduced intermediate VPLs: these are quasi-counterfree VPLs generated by context-free grammars $G$ involving the production $S \to_G \varepsilon$ for the start nonterminal $S$ and whose further productions are all of the form $T \to_G uT'v$, where $uv$ is well-matched, $u \in (\Sigma_{\mathrm{int}}^* \Sigma_{\mathrm{call}} \Sigma_{\mathrm{int}}^*)^+$, $v \in (\Sigma_{\mathrm{int}}^* \Sigma_{\mathrm{ret}} \Sigma_{\mathrm{int}}^*)^+$, and the set of contexts $\{(u, v) \in \mathrm{Con}(\Sigma) \mid S \Rightarrow_G^* uSv\}$ weakly-length synchronous but not length-synchronous. To the best of our knowledge our community is unaware of whether at all there is an intermediate VPL that is provably in $\mathbf{AC}^0$ (even in $\mathbf{ACC}^0$) or provably not in $\mathbf{AC}^0$. We conjecture that none of the intermediate VPLs are in $\mathbf{ACC}^0$ nor $\mathbf{TC}^0$-hard.

Our main result states that there is an algorithm that, given a visibly pushdown language $L$, outputs if $L$ surely lies in $\mathbf{AC}^0$, surely does not lie in $\mathbf{AC}^0$ (by providing some $m > 1$ such that $\mathrm{MOD}_m$ is constant-depth reducible to $L$), or outputs a disjoint finite union of intermediate VPLs that $L$ is constant-depth equivalent to. In the latter case one can moreover compute distinct $k, l \in \mathbb{N}_{>0}$ such that already $\mathcal{L}_{k,l} = L(S \to \varepsilon \mid ac^{k-1}Sb_1 \mid ac^{l-1}Sb_2)$ is constant-depth reducible to $L$.

We conjecture that due to the particular nature of intermediate VPLs, either all of them are in $\mathbf{AC}^0$ or all are not: this conjecture together with our main result indeed implies that there is an algorithm that decides if a given visibly pushdown language is in $\mathbf{AC}^0$.

As main tools we carefully revisited Ext-algebras, introduced by Czarnetzki et al. [10], being closely related to forest algebras, introduced by Bojańczyk and Walukiewicz [7]. For the reductions from $\mathcal{L}_{k,l}$ we made use of Green's relations.

Natural questions arise. Is there any concrete intermediate VPL that is provably in $\mathbf{ACC}^0$, provably not in $\mathbf{AC}^0$, or hard for $\mathbf{TC}^0$? Another exciting question is whether one can effectively compute those visibly pushdown languages that lie in the complexity class $\mathbf{TC}^0$. Is there is a $\mathbf{TC}^0/\mathbf{NC}^1$ complexity dichotomy? For these questions new techniques seem to be necessary. In this context it is already interesting to mention there is an $\mathbf{NC}^1$-complete visibly pushdown language whose syntactic Ext-algebra is aperiodic. Another exciting question is to give an algebraic characterization of the visibly counter languages.
# 8 Some errata in previous work

The following section summarizes some crucial errata in [24].

1. On page 176 line 8 it is written

if a VPL has SHB there exist unique rationals $\Delta_m^\uparrow$ and $\Delta_m^\downarrow$ such that for $(u, v) \in \eta_L^{-1}(m)$ we unambiguously have $\frac{\Delta(u)}{|u|} = \Delta_m^\uparrow$ and $\frac{\Delta(v)}{|v|} = \Delta_m^\downarrow$

The following language is a counter-example to this claim: consider the VPL generated by the context-free grammar $S \to aSb \mid a'cSb' \mid \varepsilon$, where $a, a'$ are call letters, $b, b'$ are return letters and $c$ is an internal letter. This rest of the section makes use of the above.

2. The previous point leads to problems, for instance the last two sentences on page 176 are problematic. By definition, it does not follow that for each $m$ there is a unique slope $\gamma$ such that for all $(u, v) \in \eta^{-1}(m)$ we have $\gamma = \frac{\Delta(u)}{|u|}$.

3. The reduction in Proposition 135 has some problems. Firstly, one cannot assume that $\alpha u \beta v \gamma$ is necessarily in $L$. It can be assumed without loss of generality though. Secondly, if $p > 2$, then $w \mapsto \alpha\phi(w)\beta\psi(w^R)\gamma$ could possibly be mapped to an element $i \in \mathbb{Z}_p$, where $i \notin \{0, 1\}$; in this case it is not clear if $\alpha\phi(w)\beta\psi(w^R)\gamma$ is in $L$ or not.

4. Top of page 182: The quotient $n_v^\uparrow/d_v^\uparrow \in \mathbb{Q}$. As mentioned in Point 1 its existence does not follow from the definition of bounded corridor. The construction of the approximate matching (proof of Proposition 126 relies on this).

5. Page 184: The relation $\rightsquigarrow_L$ is not well-defined. Proposition 126 essentially states a property that $\rightsquigarrow_L$ should satisfy, but the relation $\rightsquigarrow_L$ is defined by the formula appearing in Proposition 126. Yet, the formulas appearing already rely on the wrong observation that unique slopes exist (Point 1 from above). This has consequences for Lemma 127, Conjecture 128, Corollary 129, Conjecture 130, Conjecture 132, and Proposition 137.

6. Conjecture 128: If one were to interpret $\rightsquigarrow_L$ as “the matching relation”, then the Conjecture 128 is easily seen to be wrong. The VPL generated by the grammar $S \to acbc \mid aSb \mid \varepsilon$ does not satisfy SHB, but its matching relation is definable in FO arb.

7. Page 177, line -6. It is written

If such an $m$ exists, we also find such an element that is idempotent.

The language generated by the grammar $S \to aSb \mid a_1cb_1 \mid a_2ccb_2$ is a counter-example.

8. The statement of Proposition 131 is wrong. The language $\{a^n b^n \mid n \ge 0\}^*$ is a counter-example.

9. Proposition 131: the proof has problems since the morphism is not length-multiplying.

10. Page 181: In the characterization the first bullet point is incorrect.

11. The statement of Lemma 125 is wrong. Counter-example: $L = \{a^n b^n \mid n \ge 0\}^*$. Clearly, $\text{cancel}^{|H_L|}(w) = \Sigma_{\text{int}}^*$ for all $w \in L$ but $L$ does not have the WSHB.
12. The statement of Proposition 144 is wrong. Consider the language generated by the grammar $S \to aSb | a_1cb_1 | a_2cb_2$ which is a visibly counter language that does not have the SHB property. However, it is in $AC^0$.

13. Corollary 145 is wrong due to the previous point.

14. In the proof on page 192 in line 3 one cannot assume that an idempotent $m' \in V$ exists for which $\eta_L^{-1}(m')$ is also a witness.

15. Statement of Lemma 146 is unclear since $\rightsquigarrow_L$ is not clearly defined.

16. Lemma 147 is unclear since $\rightsquigarrow_L$ is not clearly defined. There is no proof given.

## References

[1] Rajeev Alur, Viraj Kumar, P. Madhusudan, and Mahesh Viswanathan. Congruences for visibly pushdown languages. In Luís Caires, Giuseppe F. Italiano, Luís Monteiro, Catuscia Palamidessi, and Moti Yung, editors, *Automata, Languages and Programming, 32nd International Colloquium, ICALP 2005, Lisbon, Portugal, July 11-15, 2005, Proceedings*, volume 3580 of *Lecture Notes in Computer Science*, pages 1102–1114. Springer, 2005. doi:10.1007/11523468\_89.

[2] Rajeev Alur and P. Madhusudan. Visibly pushdown languages. In László Babai, editor, *Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13-16, 2004*, pages 202–211. ACM, 2004. doi:10.1145/1007352.1007390.

[3] Vince Bárány, Christof Löding, and Olivier Serre. Regularity problems for visibly pushdown languages. In Bruno Durand and Wolfgang Thomas, editors, *STACS 2006, 23rd Annual Symposium on Theoretical Aspects of Computer Science, Marseille, France, February 23-25, 2006, Proceedings*, volume 3884 of *Lecture Notes in Computer Science*, pages 420–431. Springer, 2006. URL: https://doi.org/10.1007/11672142_34.

[4] David A. Mix Barrington. Bounded-Width Polynomial-Size Branching Programs Recognize Exactly Those Languages in $NC^1$. *J. Comput. Syst. Sci.*, 38(1):150–164, 1989. doi:10.1016/0022-0000(89)90037-8.

[5] David A. Mix Barrington, Kevin J. Compton, Howard Straubing, and Denis Thérien. Regular languages in $nc^1$. *J. Comput. Syst. Sci.*, 44(3):478–499, 1992. doi:10.1016/0022-0000(92)90014-A.

[6] Richard Beigel. The polynomial method in circuit complexity. In *Proceedings of the Eighth Annual Structure in Complexity Theory Conference, San Diego, CA, USA, May 18-21, 1993*, pages 82–95. IEEE Computer Society, 1993. doi:10.1109/SCT.1993.336538.

[7] Mikolaj Bojanczyk and Igor Walukiewicz. Forest algebras. In Jörg Flum, Erich Grädel, and Thomas Wilke, editors, *Logic and Automata: History and Perspectives [in Honor of Wolfgang Thomas]*, volume 2 of *Texts in Logic and Games*, pages 107–132. Amsterdam University Press, 2008.

[8] Ashok K. Chandra, Larry J. Stockmeyer, and Uzi Vishkin. Constant depth reducibility. *SIAM J. Comput.*, 13(2):423–439, 1984. doi:10.1137/0213028.
[9] Dmitry Chistikov and Christoph Haase. The taming of the semi-linear set. In *Automata, Languages, and Programming, ICALP*, volume 55 of LIPICS, pages 128:1–128:13. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. doi:10.4230/LIPIcs.ICALP.2016.128.

[10] Silke Czarnetzki, Andreas Krebs, and Klaus-Jörn Lange. Visibly pushdown languages and free profinite algebras. *CoRR*, abs/1810.12731, 2018. URL: http://arxiv.org/abs/1810.12731, arXiv:1810.12731.

[11] Patrick W. Dymond. Input-driven languages are in log n depth. *Inf. Process. Lett.*, 26(5):247–250, 1988. doi:10.1016/0020-0190(88)90148-2.

[12] Samuel Eilenberg. *Automata, Languages, and Machines. Volume A*. Pure and applied mathematics. Academic Press, New York, 1974. URL: https://www.sciencedirect.com/bookseries/pure-and-applied-mathematics/vol/59/part/PA.

[13] Samuel Eilenberg. *Automata, Languages, and Machines. Volume B*. Pure and applied mathematics. Academic Press, New York, 1976. URL: https://www.sciencedirect.com/bookseries/pure-and-applied-mathematics/vol/59/part/PB.

[14] Javier Esparza, Pierre Ganty, Stefan Kiefer, and Michael Luttenberger. Parikh's theorem: A simple and direct automaton construction. *Inf. Process. Lett.*, 111(12):614–619, 2011. doi: 10.1016/j.ipl.2011.03.019.

[15] Javier Esparza, Michael Luttenberger, and Maximilian Schlund. A brief history of strahler numbers. In Adrian-Horia Dediu, Carlos Martín-Vide, José Luis Sierra-Rodríguez, and Bianca Truthe, editors, *Language and Automata Theory and Applications - 8th International Conference, LATA 2014, Madrid, Spain, March 10-14, 2014. Proceedings*, volume 8370 of *Lecture Notes in Computer Science*, pages 1–13. Springer, 2014. doi:10.1007/978-3-319-04921-2_1.

[16] Yuri Gurevich and Harry R. Lewis. A logic for constant-depth circuits. *Inf. Control.*, 61(1):65–74, 1984. doi:10.1016/S0019-9958(84)80062-5.

[17] Michael A. Harrison. *Introduction to Formal Language Theory*. Addison-Wesley, 1978.

[18] Johan Håstad. Almost optimal lower bounds for small depth circuits. In Juris Hartmanis, editor, *Proceedings of the 18th Annual ACM Symposium on Theory of Computing, May 28-30, 1986, Berkeley, California, USA*, pages 6–20. ACM, 1986. doi:10.1145/12130.12132.

[19] Neil Immerman. Languages that capture complexity classes. *SIAM J. Comput.*, 16(4):760–778, 1987. doi:10.1137/0216051.

[20] Neil Immerman. *Descriptive complexity*. Graduate texts in computer science. Springer, 1999. doi:10.1007/978-1-4612-0539-5.

[21] Stasys Jukna. *Boolean Function Complexity - Advances and Frontiers*, volume 27 of *Algorithms and combinatorics*. Springer, 2012. doi:10.1007/978-3-642-24508-4.

[22] Andreas Krebs, Klaus-Jörn Lange, and Michael Ludwig. Visibly counter languages and constant depth circuits. In Ernst W. Mayr and Nicolas Ollinger, editors, *32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015, March 4-7, 2015, Garching, Germany*, volume 30 of LIPICS, pages 594–607. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015. doi:10.4230/LIPIcs.STACS.2015.594.
[23] Andreas Krebs, Klaus-Jörn Lange, and Michael Ludwig. Visibly counter languages and constant depth circuits. In Ernst W. Mayr and Nicolas Ollinger, editors, *32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015, March 4-7, 2015, Garching, Germany*, volume 30 of *LIPIcs*, pages 594–607. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015. doi:10.4230/LIPIcs.STACS.2015.594.

[24] Michael Ludwig. *Tree-Structured Problems and Parallel Computation*. PhD thesis, University of Tübingen, Germany, 2019. URL: https://publikationen.uni-tuebingen.de/xmlui/handle/10900/85960/.

[25] Kurt Mehlhorn. Pebbling Moutain Ranges and its Application of DCFL-Recognition. In J. W. de Bakker and Jan van Leeuwen, editors, *Automata, Languages and Programming, 7th Colloquium, Noordweijkerhout, The Netherlands, July 14-18, 1980, Proceedings*, volume 85 of *Lecture Notes in Computer Science*, pages 422–435. Springer, 1980. doi:10.1007/3-540-10003-2_89.

[26] Jean-Éric Pin. *Varieties of Formal Languages*. North Oxford, London and Plenum, New-York, 1986. (Traduction de Variétés de langages formels).

[27] Jean-Éric Pin, editor. *Handbook of Automata Theory*. European Mathematical Society Publishing House, Zürich, Switzerland, 2021. doi:10.4171/Automata.

[28] Marcel Paul Schützenberger. On finite monoids having only trivial subgroups. *Inf. Control.*, 8(2):190–194, 1965. doi:10.1016/S0019-9958(65)90108-7.

[29] Howard Straubing. *Finite Automata, Formal Logic, and Circuit Complexity*. Birkhäuser Boston, 1994. doi:10.1007/978-1-4612-0289-9.

[30] Howard Straubing. On logical descriptions of regular languages. In Sergio Rajsbaum, editor, *LATIN 2002: Theoretical Informatics, 5th Latin American Symposium, Cancun, Mexico, April 3-6, 2002, Proceedings*, volume 2286 of *Lecture Notes in Computer Science*, pages 528–538. Springer, 2002. doi:10.1007/3-540-45995-2_46.

[31] Heribert Vollmer. *Introduction to Circuit Complexity - A Uniform Approach*. Texts in Theoretical Computer Science. An EATCS Series. Springer, 1999. doi:10.1007/978-3-662-03927-4.