w_{i_{1}-1})w_{i_{1}}\cdots\widetilde{\vartheta}(w_{i_{k-1}+1}\cdots
w_{i_{k}-1})w_{i_{k}}\widetilde{\vartheta}(w_{i_{k+1}+1}\cdots w_{|u|})$

and

$v^{\prime}=\overline{\vartheta}(w_{|u|+2}\cdots
w_{j_{l+1}-1})w_{j_{l}}\cdots\overline{\vartheta}(w_{j_{2}}+1\cdots
w_{j_{1}-1})w_{j_{1}}\overline{\vartheta}(w_{j_{1}}+1\cdots w_{m}).$

  7. 7.

Accept if, and only if, the word $u^{\prime}v^{\prime}$ is in $N_{e}$. ∎

######  Lemma 5.22.

$M_{e}\leq_{\text{cd}}\biguplus_{\text{$f\in O_{L}$ is
$\varphi_{L}(L)$-reachable}}L_{f}$ for all $e\in\mathcal{Z}$.

###### Proof.

Note that the following equivalence holds:

$u\\#v\in M_{e}\quad\Longleftrightarrow\quad\text{$\exists f\in O_{L}$ that is
$\varphi_{L}(L)$-reachable}:e\circ f=e\wedge u\\#v\in
L_{f}\wedge\Delta(u)>0\,\,\text{.}$

This holds because for
$\operatorname{ext}_{u,v}\in\mathcal{O}(\Sigma^{\triangle})$ satisfying
$e\circ\psi_{L}(\operatorname{ext}_{u,v})=e$, as $e$ is
$\varphi_{L}(L)$-reachable, $\psi_{L}(\operatorname{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 $\biguplus_{\text{$f\in O_{L}$ is
$\varphi_{L}(L)$-reachable}}L_{f}$:

  1. 1.

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

  2. 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. 3.

Finally, accept if, and only if for all $\varphi_{L}(L)$-reachable $f\in
O_{L}$ we have $u\\#\not\in L_{f}$.

If the second check is successful, then $\psi_{L}(\operatorname{ext}_{u,v})$
is necessarily $\varphi_{L}(L)$-reachable, so in that case when $\Delta(u)=0$
it holds that $u\in\Sigma^{\triangle}$ and
$\psi_{L}(\operatorname{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$. ∎

######  Lemma 5.23.

$L\leq_{\text{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
$\mathsf{FO}_{\Gamma_{\varphi_{L}}}[<,\mathsf{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\mathsf{Con}(\Sigma)\mid\psi_{L}(\operatorname{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
$\operatorname{ext}_{x_{g},y_{g}},\operatorname{ext}_{x_{h},y_{h}}\in\mathcal{O}(\Sigma^{\triangle})$
such that $\psi_{L}(\operatorname{ext}_{x_{g},y_{g}})=g$ and
$\psi_{L}(\operatorname{ext}_{x_{h},y_{h}})=h$. Let
$(u,v),(u^{\prime},v^{\prime})\in\mathsf{Con}(\Sigma)$ such that
$\Delta(u),\Delta(u^{\prime})>0$ and
$\psi_{L}(\operatorname{ext}_{u,v})=\psi_{L}(\operatorname{ext}_{u^{\prime},v^{\prime}})=f$.
Because $f$ is idempotent, we have that
$\psi_{L}(\operatorname{ext}_{u^{\mathopen{}\left|v^{\prime}\right|\mathclose{}},v^{\mathopen{}\left|v^{\prime}\right|\mathclose{}}})=\psi_{L}(\operatorname{ext}_{u^{\prime\mathopen{}\left|v\right|\mathclose{}},v^{\prime\mathopen{}\left|v\right|\mathclose{}}})=f$,
thus
$\psi_{L}(\operatorname{ext}_{x_{g}u^{\mathopen{}\left|v^{\prime}\right|\mathclose{}}x_{h},y_{h}v^{\mathopen{}\left|v^{\prime}\right|\mathclose{}}y_{g}})=\psi_{L}(\operatorname{ext}_{x_{g}u^{\prime\mathopen{}\left|v\right|\mathclose{}}x_{h},y_{h}v^{\prime\mathopen{}\left|v\right|\mathclose{}}y_{g}})=e$.
Therefore, because of length-synchronicity of $\mathcal{R}_{e}$, it follows
that

$\displaystyle\frac{\mathopen{}\left|x_{g}u^{\mathopen{}\left|v^{\prime}\right|\mathclose{}}x_{h}\right|\mathclose{}}{\mathopen{}\left|y_{h}v^{\mathopen{}\left|v^{\prime}\right|\mathclose{}}y_{g}\right|\mathclose{}}$
$\displaystyle=\frac{\mathopen{}\left|x_{g}u^{\prime\mathopen{}\left|v\right|\mathclose{}}x_{h}\right|\mathclose{}}{\mathopen{}\left|y_{h}v^{\prime\mathopen{}\left|v\right|\mathclose{}}y_{g}\right|\mathclose{}}$
$\displaystyle\frac{\mathopen{}\left|x_{g}\right|\mathclose{}+\mathopen{}\left|v^{\prime}\right|\mathclose{}\cdot\mathopen{}\left|u\right|\mathclose{}+\mathopen{}\left|x_{h}\right|\mathclose{}}{\mathopen{}\left|y_{h}\right|\mathclose{}+\mathopen{}\left|v^{\prime}\right|\mathclose{}\cdot\mathopen{}\left|v\right|\mathclose{}+\mathopen{}\left|y_{g}\right|\mathclose{}}$
$\displaystyle=\frac{\mathopen{}\left|x_{g}\right|\mathclose{}+\mathopen{}\left|v\right|\mathclose{}\cdot\mathopen{}\left|u^{\prime}\right|\mathclose{}+\mathopen{}\left|x_{h}\right|\mathclose{}}{\mathopen{}\left|y_{h}\right|\mathclose{}+\mathopen{}\left|v\right|\mathclose{}\cdot\mathopen{}\left|v^{\prime}\right|\mathclose{}+\mathopen{}\left|y_{g}\right|\mathclose{}}$
$\displaystyle\mathopen{}\left|v^{\prime}\right|\mathclose{}\cdot\mathopen{}\left|u\right|\mathclose{}$
$\displaystyle=\mathopen{}\left|v\right|\mathclose{}\cdot\mathopen{}\left|u^{\prime}\right|\mathclose{}$
$\displaystyle\frac{\mathopen{}\left|u\right|\mathclose{}}{\mathopen{}\left|v\right|\mathclose{}}$
$\displaystyle=\frac{\mathopen{}\left|u^{\prime}\right|\mathclose{}}{\mathopen{}\left|v^{\prime}\right|\mathclose{}}\,\,\text{.}$

So we can conclude that
$\mathcal{R}_{f}=\\{(u,v)\in\mathsf{Con}(\Sigma)\mid\psi_{L}(\operatorname{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
$\mathsf{FO}_{\Gamma_{\psi_{L}}}[<,\mathsf{MOD}]$-sentence $\nu_{\psi_{L},e}$
defining $\mathcal{E}_{\psi_{L},e}$.

For proving $L\leq_{\text{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}^{\mathsf{exact}}$ such that for
all $w\in\Sigma^{+}$ and
$i,i^{\prime},j^{\prime},j\in[1,\mathopen{}\left|w\right|\mathclose{}],i\leq
i^{\prime}<j^{\prime}\leq j$ the following holds:

$\displaystyle w\models\pi_{e}^{\mathsf{exact}}(i,i^{\prime},j^{\prime},j)$
$\displaystyle\quad\Longleftrightarrow\quad$ $\displaystyle w_{i}\cdots
w_{i^{\prime}}w_{j^{\prime}}\cdots
w_{j}\in\Sigma^{\triangle},e\circ\psi_{L}(\operatorname{ext}_{w_{i}\cdots
w_{i^{\prime}},w_{j^{\prime}}\cdots w_{j}})=e\text{~and }$
$\displaystyle\Delta(w_{i}\cdots w_{i^{\prime}})>0$

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
$\mathsf{FO}[\mathsf{+}]$-definable (and hence constant-depth computable)
predicate $\pi_{e}$ at hand. It has the following properties: for all
$w\in\Sigma^{+}$ and
$i,i^{\prime},j^{\prime},j\in[1,\mathopen{}\left|w\right|\mathclose{}],i\leq
i^{\prime}<j^{\prime}\leq j$:

  * •

if $w\models\pi_{e}(i,i^{\prime},j^{\prime},j)$, then $w_{i}\cdots
w_{i^{\prime}}w_{j^{\prime}}\cdots w_{j}\in\Sigma^{\triangle}$ and

  * •

if $w_{i}\cdots w_{i^{\prime}}w_{j^{\prime}}\cdots
w_{j}\in\Sigma^{\triangle}$, $\Delta(w_{i}\cdots w_{i^{\prime}})>0$ and
$e\circ\psi_{L}(\operatorname{ext}_{w_{i}\cdots
w_{i^{\prime}},w_{j^{\prime}}\cdots w_{j}})=e$, then
$w\models\pi_{e}(i,i^{\prime},j^{\prime},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\mathcal{Z}$ by our predicate
$\pi_{e}^{\mathsf{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}^{\mathsf{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^{\triangle}$ 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

  * •

$\overline{\eta}_{d,r}^{\uparrow}(x,y)$ for all $d\in[0,d_{L}]$ and all
$\varphi_{L}(L)$-reachable $r\in R_{L}$ and

  * •

$\overline{\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^{\triangle}$ and all
$i,j\in[1,\mathopen{}\left|w\right|\mathclose{}]$:

  * •

if $i$ is matched to $j$ in $w$, then
$(w,M^{\triangle}\left(w\right))\models\overline{\eta}_{d,r}^{\uparrow}(i,j)$
if, and only if, $\operatorname{nd}(w_{i}\cdots w_{j})\leq d$ and
$\varphi_{L}(w_{i}\cdots w_{j})=r$;

  * •

if $w_{i}\cdots w_{j}\in\Sigma^{\triangle}$, then
$(w,M^{\triangle}\left(w\right))\models\overline{\eta}_{d,r}(i,j)$ if, and
only if, $\operatorname{nd}(w_{i}\cdots w_{j})\leq d$ and
$\varphi_{L}(w_{i}\cdots w_{j})=r$.

It remains to define the formulas $\overline{\eta}_{d,r}$ and
$\overline{\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
$\overline{\eta}_{0,r}^{\uparrow}$ and the $\overline{\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
$\overline{\chi}_{d,e}(x,x^{\prime},y^{\prime},y)$ such that for all
$w\in\Sigma^{\triangle}$ and
$i,i^{\prime},j^{\prime},j\in[1,\mathopen{}\left|w\right|\mathclose{}],i\leq
i^{\prime}<j^{\prime}\leq j$ we have that if $w_{i}\cdots
w_{i^{\prime}}w_{j^{\prime}}\cdots w_{j}\in\Sigma^{\triangle}$ and
$i^{\prime}$ is matched to $j^{\prime}$ in $w$, then given

$\operatorname{ext}_{w_{i}\cdots w_{i^{\prime}},w_{j^{\prime}}\cdots
w_{j}}=\operatorname{ext}_{x_{1},y_{1}}\circ\operatorname{ext}_{a_{1},b_{1}}\circ\cdots\circ\operatorname{ext}_{x_{k},y_{k}}\circ\operatorname{ext}_{a_{k},b_{k}}$

the stair factorization of $\operatorname{ext}_{w_{i}\cdots
w_{i^{\prime}},w_{j^{\prime}}\cdots w_{j}}$ provided by Lemma 3.6, we have
$(w,M^{\triangle}\left(w\right))\models\overline{\chi}_{d,e}(i,i^{\prime},j^{\prime},j)$
if, and only if, $\operatorname{nd}(x_{\ell}),\operatorname{nd}(y_{\ell})<d$
for all $\ell\in[1,k]$ and $\psi_{L}(\operatorname{ext}_{w_{i}\cdots
w_{i^{\prime}},w_{j^{\prime}}\cdots w_{j}})=e$. Given
$w,i,i^{\prime},j^{\prime},j$ and the associated stair factorization as above,
note that if $\psi_{L}(\operatorname{ext}_{w_{i}\cdots
w_{i^{\prime}},w_{j^{\prime}}\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 $\operatorname{nd}(x_{\ell}),\operatorname{nd}(y_{\ell})<d$
for all $\ell\in[1,k]$, we can inductively make use of the formulas
$\\{\overline{\eta}_{d-1,r^{\prime}}\mid r^{\prime}\in R_{L}\text{
$\varphi_{L}(L)$-reachable}\\}$ in order to evaluate
$\varphi_{L}(x_{1}),\varphi_{L}(y_{1}),\ldots,\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^{\prime}}=\psi_{L}(\operatorname{ext}_{x_{\ell},y_{\ell}}\circ\operatorname{ext}_{a_{\ell},b_{\ell}}\circ\cdots\circ\operatorname{ext}_{x_{\ell^{\prime}},y_{\ell^{\prime}}}\circ\operatorname{ext}_{a_{\ell^{\prime}},b_{\ell^{\prime}}})\quad\text{and}\quad
e_{\ell}=e_{1,\ell}$

for all $\ell,\ell^{\prime}\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}\leq
s_{1}<t_{1}<s_{2}<t_{2}<\cdots<s_{q}<t_{q}\leq s_{q+1}=k$ such that
$[s_{1},t_{1}],\ldots,[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}\left|D_{p}\right|\leq 3\left|O_{L}\right|$. Let
$i=i_{1}<\cdots<i_{k}$ and $j_{k}<\cdots<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
$\operatorname{ext}_{w_{i}\cdots w_{i^{\prime}},w_{j^{\prime}}\cdots w_{j}}$
in $w$, respectively: more precisely $i_{\ell}=i+\mathopen{}\left|x_{1}\cdots
a_{\ell-1}x_{\ell}\right|\mathclose{}$ and
$j_{\ell}=\mathopen{}\left|x_{1}a_{1}\cdots x_{k}a_{k}w_{i^{\prime}+1}\cdots
w_{j^{\prime}-1}b_{k}y_{k}\cdots b_{\ell+1}y_{\ell+1}\right|\mathclose{}+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(\operatorname{ext}_{x_{s_{p}+1}\cdots
a_{t_{p}},b_{t_{p}}\cdots y_{s_{p}+1}})\,\,\text{.}$

Given $p\in[1,q]$, if $e_{s_{p}}\in\mathcal{Z}$, we can use the predicate
$\pi_{e_{s_{p}}}^{\mathsf{exact}}$ to check the above equality; we set
$\theta_{d,e_{s_{p}}}(x,x^{\prime},y^{\prime},y)=\pi_{e_{s_{p}}}^{\mathsf{exact}}(x,x^{\prime},y^{\prime},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^{\prime}\in
O_{L}$ such that $e_{s_{p}}\circ e^{\prime}=e_{s_{p}}$, we have that
$e^{\prime}$ is $\varphi_{L}(L)$-reachable and
$\mathcal{R}_{e^{\prime}}=\\{(u,v)\in\Sigma^{*}\times\Sigma^{*}\mid
uv\in\Sigma^{\triangle},\Delta(u)>0,\psi_{L}(\operatorname{ext}_{u,v})=e^{\prime}\\}$
is length-synchronous. So to check the above equality, we can use the formula
$\theta_{d,e_{s_{p}}}(x,x^{\prime},y^{\prime},y)$ built by taking the
disjunction over all $e^{\prime}\in O_{L}$ such that $e_{s_{p}}\circ
e^{\prime}=e_{s_{p}}$ of the formulas defined inductively completely
analogously as $\chi_{d,e^{\prime}}(x,x^{\prime},y^{\prime},x^{\prime})$ in
Section 5.3.5 (using the sentence $\nu_{\psi_{L},e^{\prime}}$ defining
$\mathcal{E}_{\psi_{L},e^{\prime}}$): we simply replace every occurrence of
$\eta_{d-1,r}$ by $\overline{\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^{\prime},y^{\prime},y)$ such that for
all $w\in\Sigma^{\triangle}$ and
$i,i^{\prime},j^{\prime},j\in[1,\mathopen{}\left|w\right|\mathclose{}],i\leq
i^{\prime}<j^{\prime}\leq j$ we have that if $w_{i}\cdots
w_{i^{\prime}}w_{j^{\prime}}\cdots w_{j}\in\Sigma^{\triangle}$ and
$i^{\prime}$ is matched to $j^{\prime}$ in $w$, then given

$\operatorname{ext}_{w_{i}\cdots w_{i^{\prime}},w_{j^{\prime}}\cdots
w_{j}}=\operatorname{ext}_{x_{1},y_{1}}\circ\operatorname{ext}_{a_{1},b_{1}}\circ\cdots\circ\operatorname{ext}_{x_{k},y_{k}}\circ\operatorname{ext}_{a_{k},b_{k}}$

the stair factorization of $\operatorname{ext}_{w_{i}\cdots
w_{i^{\prime}},w_{j^{\prime}}\cdots w_{j}}$ provided by Lemma 3.6, we have
$(w,M^{\triangle}\left(w\right))\models\alpha_{d,m,f}(i,i^{\prime},j^{\prime},j)$
if, and only if, $\operatorname{nd}(x_{\ell}),\operatorname{nd}(y_{\ell})<d$
for all $\ell\in[1,k]$, $\Delta(w_{i}\cdots
w_{i^{\prime}})=-\Delta(w_{j^{\prime}}\cdots w_{j})=m$ and
$\psi_{L}(\operatorname{ext}_{w_{i}\cdots w_{i^{\prime}},w_{j^{\prime}}\cdots
w_{j}})=e$. For
$\bm{\sigma}=(\bm{\sigma}_{1},\dots,\bm{\sigma}_{m})\in\Sigma_{\text{call}}^{m}$,
$\bm{\xi}=(\bm{\xi}_{1}\dots,\bm{\xi}_{m})\in\Sigma_{\text{ret}}^{m}$,
$\bm{r}=(\bm{r}_{1},\dots,\bm{r}_{m})\in{R_{L}}^{m}$, and
$\bm{r}^{\dagger}=(\bm{r}_{1}^{\dagger},\dots,\bm{r}_{m}^{\dagger})\in{R_{L}}^{m}$
we define

$\prod(\bm{\sigma},\bm{\xi},\bm{r},\bm{r}^{\dagger})=\bigcirc_{g=1}^{m}\mathrm{left}_{\bm{r}_{g}}\circ\mathrm{right}_{\bm{r}_{g}^{\dagger}}\circ\psi_{L}(\operatorname{ext}_{\bm{\sigma}_{g},\bm{\xi}_{g}}).$

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

$\displaystyle\alpha_{d,m,f}(x,x^{\prime},y^{\prime},y)=$
$\displaystyle\bigvee_{\begin{subarray}{c}\bm{\sigma}\in\Sigma_{\text{call}}^{m},\bm{\xi}\in\Sigma_{\text{ret}}^{m}\\\
\bm{r},\bm{r}^{\dagger}\in{R_{L}}^{m}:f=\prod(\bm{\sigma},\bm{\xi},\bm{r},\bm{r}^{\dagger})\end{subarray}}\exists
x_{1},\dots,x_{m}\exists y_{1},\dots,y_{m}$
$\displaystyle\biggl{(}\begin{aligned} &x^{\prime}=x_{m}\wedge
y^{\prime}=y_{m}\wedge x\leq x_{1}<\cdots<x_{m}<y_{m}<\cdots<y_{1}\leq
y\wedge\\\
&\bigwedge_{g=1}^{m}\bigl{(}\bm{\sigma}_{g}(x_{g})\wedge\bm{\xi}_{g}(y_{g})\wedge
x_{g}\leftrightsquigarrow y_{g}\bigr{)}\wedge\\\ &\forall z\bigl{(}(x\leq
z\leq x^{\prime}\wedge\bigwedge_{g=1}^{m}z\neq x_{g})\rightarrow\neg
U(x,x^{\prime},z)\bigr{)}\wedge\\\
&\Bigl{(}\bigl{(}x<x_{1}\wedge\overline{\eta}_{d-1,\bm{r}_{1}}(x,x_{1}-1)\bigr{)}\vee
F_{\bm{r}_{1}}(x,x_{1})\Bigr{)}\wedge\\\
&\Bigl{(}\bigl{(}y_{1}<y\wedge\overline{\eta}_{d-1,\bm{r}_{1}^{\dagger}}(y_{1}+1,y)\bigr{)}\vee
F_{\bm{r}_{1}^{\dagger}}(y_{1},y)\Bigr{)}\wedge\\\
&\bigwedge_{g=2}^{m}\overline{\eta}_{d-1,\bm{r}_{g}}(x_{g-1}+1,x_{g}-1)\wedge\bigwedge_{g=2}^{m}\overline{\eta}_{d-1,\bm{r}_{g}^{\dagger}}(y_{g}+1,y_{g-1}-1)\biggr{)}\end{aligned}$

with $F_{s}(x,z)=\begin{cases}x=z&\text{if $s=1_{R_{L}}$}\\\
\bot&\text{otherwise}\end{cases}$ for all $\varphi_{L}(L)$-reachable $s\in
R_{L}$.

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

$\displaystyle\overline{\chi}_{d,e}(x,x^{\prime},y^{\prime},x)$
$\displaystyle=$ $\displaystyle\bigvee_{q\in[0,|O|]\atop{d_{0},\dots,d_{q}\geq
1:\atop q+d_{0}+\dots+d_{q}\leq
3|0|}}\bigvee_{e_{0},f_{0},e_{1},\dots,f_{q-1},e_{q},f_{q}\in
O\atop{e_{0}=1_{O}\wedge\forall j\in[1,q]:e_{j}=e_{j-1}\circ f_{j-1}\atop
e=e_{q}\circ f_{q}}}$ $\displaystyle\exists x_{1}\dots x_{q+1}\exists
x_{0}^{\prime}\dots x_{q}^{\prime}\exists y_{1}\dots y_{q+1}\exists
y_{1}^{\prime}\dots y_{0}^{\prime}$
$\displaystyle\left(\Biggl{.}\\!\\!\\!\\!\\!\phantom{\bigwedge_{p=1}^{q}}x_{0}^{\prime}\leq
x_{1}<x_{1}^{\prime}<x_{2}<\dots<x_{q}^{\prime}<y_{q}^{\prime}<y_{q}<\dots<y_{1}^{\prime}<y_{1}\leq
y_{0}^{\prime}\right.\wedge$ $\displaystyle\quad x_{0}^{\prime}=x\wedge
y_{0}^{\prime}=y\wedge x_{q}^{\prime}=x^{\prime}\wedge
y_{q}^{\prime}=y^{\prime}\wedge$
$\displaystyle\quad\left.\bigwedge_{p=1}^{q}\left(\theta_{e_{p}}(x_{p}+1,x_{p}^{\prime},y_{p}^{\prime},y_{p}-1)\right)\wedge\bigwedge_{p=0}^{q}\alpha_{d_{p},f_{p}}(x_{p}^{\prime}+1,x_{p+1},y_{p+1},y_{p}^{\prime}-1)\right)\,\,\text{.}$

The inductive definition of $\overline{\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 $\overline{\eta}_{d-1,r}$ and
every occurrence of $\chi_{d,e}$ by $\overline{\chi}_{d,e}$

The inductive definition of $\overline{\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},r}$ for all
$\varphi_{L}(L)$-reachable $r\in R_{L}$ by making use of the sentence
$\nu_{\varphi,r}$ and the already defined $\overline{\eta}_{d,r}^{\uparrow}$.
∎

####  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}\leq_{\text{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}\leq_{\text{cd}}L$ .

###### Proof.

Let $L\subseteq\Sigma^{\triangle}$ 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}^{\prime},l_{0}^{\prime})\in\mathbb{N}_{>0}^{4}$ for which
there exist
$\operatorname{ext}_{u,v},\operatorname{ext}_{u^{\prime},v^{\prime}}\in\mathcal{O}(\Sigma^{\triangle})$
such that

  * •

$|u|=k_{0}$, $|v|=l_{0}$, $|u^{\prime}|=k_{0}^{\prime}$,
$|v^{\prime}|=l_{0}^{\prime}$,

  * •

$\psi_{L}(\operatorname{ext}_{u,v})=\psi_{L}(\operatorname{ext}_{u^{\prime},v^{\prime}})$
is a $\varphi_{L}(L)$-reachable idempotent,

  * •

$\Delta(u),\Delta(u^{\prime})>0$, and

  * •

$\frac{k_{0}}{l_{0}}=\frac{\mathopen{}\left|u\right|\mathclose{}}{\mathopen{}\left|v\right|\mathclose{}}\neq\frac{\mathopen{}\left|u^{\prime}\right|\mathclose{}}{\mathopen{}\left|v^{\prime}\right|\mathclose{}}=\frac{k_{0}^{\prime}}{l_{0}^{\prime}}$.

We can explicitly compute such $\operatorname{ext}_{u,v}$ and
$\operatorname{ext}_{u^{\prime},v^{\prime}}$ by just doing an exhaustive
search. This enables us to assume without loss of generality while maintaining
effective computability that $\Delta(u)=\Delta(u^{\prime})$: indeed, in case
$\Delta(u)\not=\Delta(u^{\prime})$, we can consider
$\operatorname{ext}_{u_{1},v_{1}}=\operatorname{ext}_{u^{\Delta(u^{\prime})},v^{\Delta(u^{\prime})}}$
and
$\operatorname{ext}_{u_{2},v_{2}}=\operatorname{ext}_{(u^{\prime})^{\Delta(u)},(v^{\prime})^{\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\leq_{\mathfrak{J}}y$ whenever there are elements $e,f$ of $O_{L}$
such that $x=e\circ y\circ f$. We write $x\mathrel{\mathfrak{J}}y$ if
$x\leq_{\mathfrak{J}}y$ and $y\leq_{\mathfrak{J}}x$. We finally write
$x<_{\mathfrak{J}}y$ if $x\leq_{\mathfrak{J}}y$ and
$x\not\mathrel{\mathfrak{J}}y$.

  * •

We write $x\leq_{\mathfrak{R}}y$ whenever there is an element $e$ of $O_{L}$
such that $x=y\circ e$. We write $x\mathrel{\mathfrak{R}}y$ if
$x\leq_{\mathfrak{R}}y$ and $y\leq_{\mathfrak{R}}x$.

  * •

We write $x\leq_{\mathfrak{L}}y$ whenever there is an element $e$ of $O_{L}$
such that $x=e\circ y$. We write $x\mathrel{\mathfrak{L}}y$ if
$x\leq_{\mathfrak{L}}y$ and $y\leq_{\mathfrak{L}}x$.

  * •

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

Observe that because $\Delta(u)=\Delta(u^{\prime})$, we have that
$uv^{\prime}\in\Sigma^{\triangle}$ and $u^{\prime}v\in\Sigma^{\triangle}$, so
that we can consider the elements
$\operatorname{ext}_{uuu,vv^{\prime}v}=\operatorname{ext}_{u,v}\circ\operatorname{ext}_{u,v^{\prime}}\circ\operatorname{ext}_{u,v}$
and
$\operatorname{ext}_{uu^{\prime}u,vvv}=\operatorname{ext}_{u,v}\circ\operatorname{ext}_{u^{\prime},v}\circ\operatorname{ext}_{u,v}$
in $\mathcal{O}(\Sigma^{\triangle})$. These elements satisfy
$\psi_{L}(\operatorname{ext}_{uuu,vv^{\prime}v})\leq_{\mathfrak{J}}\psi_{L}(\operatorname{ext}_{u,v})$
and
$\psi_{L}(\operatorname{ext}_{uu^{\prime}u,vvv})\leq_{\mathfrak{J}}\psi_{L}(\operatorname{ext}_{u,v})$.
We claim that we actually have
$\psi_{L}(\operatorname{ext}_{uuu,vv^{\prime}v})<_{\mathfrak{J}}\psi_{L}(\operatorname{ext}_{u,v})$
and
$\psi_{L}(\operatorname{ext}_{uu^{\prime}u,vvv})<_{\mathfrak{J}}\psi_{L}(\operatorname{ext}_{u,v})$.
Indeed, assume we would have
$\psi_{L}(\operatorname{ext}_{uu^{\prime}u,vvv})\mathrel{\mathfrak{J}}\psi_{L}(\operatorname{ext}_{u,v})$.
Set $x=\psi_{L}(\operatorname{ext}_{u,v})$ and
$y=\psi_{L}(\operatorname{ext}_{u^{\prime},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\leq_{\mathfrak{R}}x$ and $x\circ y\circ
x\mathrel{\mathfrak{J}}x$, we would have $x\circ y\circ
x\mathrel{\mathfrak{R}}x$ and dually, since it would hold that $x\circ y\circ
x\leq_{\mathfrak{L}}x$ and $x\circ y\circ x\mathrel{\mathfrak{J}}x$, we would
have $x\circ y\circ x\mathrel{\mathfrak{L}}x$. Therefore, we would have
$x\circ y\circ x\mathrel{\mathfrak{H}}x$. By another classical result on
Green’s relations [26, Chapter 3, Corollary 1.7], as $x$ is an idempotent, its
$\mathrel{\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}(\operatorname{ext}_{(uu^{\prime}u)^{\omega},(vvv)^{\omega}})=\psi_{L}(\operatorname{ext}_{(uuu)^{\omega},(vvv)^{\omega}})$
is a $\varphi_{L}(L)$-reachable idempotent and
$\Delta((uu^{\prime}u)^{\omega})=\Delta((uuu)^{\omega})>0$ but
$\mathopen{}\left|(uu^{\prime}u)^{\omega}\right|\mathclose{}\neq\mathopen{}\left|(uuu)^{\omega}\right|\mathclose{}$,
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}(\operatorname{ext}_{uuu,vv^{\prime}v})\mathrel{\mathfrak{J}}\psi_{L}(\operatorname{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}\leq_{\text{cd}}L_{\psi_{L}(\operatorname{ext}_{u,v})}$, so
that since $L_{\psi_{L}(\operatorname{ext}_{u,v})}\leq_{\text{cd}}L$ (by Lemma
5.3) and by transitivity of $\leq_{\text{cd}}$ we have
$\mathcal{L}_{k,l}\leq_{\text{cd}}L$.

##### Case
$\mathopen{}\left|v\right|\mathclose{}=\mathopen{}\left|v^{\prime}\right|\mathclose{}$.

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

  1. 1.

check if $w=xy$ with
$x\in(ac^{3\mathopen{}\left|u\right|\mathclose{}-1}+ac^{2\mathopen{}\left|u\right|\mathclose{}+\mathopen{}\left|u^{\prime}\right|\mathclose{}-1})^{*}$
and $y\in(b_{1}+b_{2})^{*}$, reject if it’s not the case;

  2. 2.

build $x^{\prime}$ by sending $ac^{3\mathopen{}\left|u\right|\mathclose{}-1}$
to $u^{3}$,
$ac^{2\mathopen{}\left|u\right|\mathclose{}+\mathopen{}\left|u^{\prime}\right|\mathclose{}-1}$
to $uu^{\prime}u$ and $y^{\prime}$ by sending $b_{1}$ to $v^{3}$ and $b_{2}$
to $vv^{\prime}v$;

  3. 3.

accept whenever $x^{\prime}\\#y^{\prime}\in
L_{\psi_{L}(\operatorname{ext}_{u,v})}$.

This forms a valid reduction. Indeed, take a word $w=xy$ with
$x\in(ac^{3\mathopen{}\left|u\right|\mathclose{}-1}+ac^{2\mathopen{}\left|u\right|\mathclose{}+\mathopen{}\left|u^{\prime}\right|\mathclose{}-1})^{n}$
for $n\in\mathbb{N}$ and $y\in(b_{1}+b_{2})^{m}$ for $m\in\mathbb{N}$ and
consider $x^{\prime}\\#y^{\prime}$ produced by the reduction with
$x^{\prime}\in(u^{3}+uu^{\prime}u)^{n}$ and
$y^{\prime}\in(v^{3}+vv^{\prime}v)^{m}$. If
$w\in\mathcal{L}_{3\mathopen{}\left|u\right|\mathclose{},2\mathopen{}\left|u\right|\mathclose{}+\mathopen{}\left|u^{\prime}\right|\mathclose{}}$,
then it easily follows that $x^{\prime}\\#y^{\prime}\in
L_{\psi_{L}(\operatorname{ext}_{u,v})}$. Otherwise, if
$w\notin\mathcal{L}_{3\mathopen{}\left|u\right|\mathclose{},2\mathopen{}\left|u\right|\mathclose{}+\mathopen{}\left|u^{\prime}\right|\mathclose{}}$,
then either $n\neq m$ and thus $x^{\prime}y^{\prime}$ is not well-matched
because $\Delta(x^{\prime})=n\cdot 3\cdot\Delta(u)$ and
$\Delta(y^{\prime})=m\cdot 3\cdot\Delta(v)$, or $n=m$ and thus
$x^{\prime}y^{\prime}$ is well-matched, so
$\operatorname{ext}_{x^{\prime},y^{\prime}}=\operatorname{ext}_{z_{1}^{\prime},t_{1}^{\prime}}\circ\cdots\circ\operatorname{ext}_{z_{n}^{\prime},t_{n}^{\prime}}$
with $z_{1}^{\prime},\ldots,z_{n}^{\prime}\in\\{u^{3},uu^{\prime}u\\}$ and
$t_{1}^{\prime},\ldots,t_{n}^{\prime}\in\\{v^{3},vv^{\prime}v\\}$ such that
there exists $i\in[1,n]$ satisfying
$\operatorname{ext}_{z_{i}^{\prime},t_{i}^{\prime}}\in\\{\operatorname{ext}_{u^{3},vv^{\prime}v},\operatorname{ext}_{uu^{\prime}u,v^{3}}\\}$,
thereby implying

$\psi_{L}(\operatorname{ext}_{x^{\prime},y^{\prime}})\leq_{\mathfrak{J}}\psi_{L}(\operatorname{ext}_{z_{i}^{\prime},t_{i}^{\prime}})<_{\mathfrak{J}}\psi_{L}(\operatorname{ext}_{u,v})\,\,\text{.}$

Our algorithm therefore outputs the pair
$(k,l)=(3k_{0},2k_{0}+k_{0}^{\prime})$.

##### Case
$\mathopen{}\left|u\right|\mathclose{}=\mathopen{}\left|u^{\prime}\right|\mathclose{}$.

This case is symmetric to the previous case. Our algorithm outputs the pair
$(k,l)=(2l_{0}+l_{0}^{\prime},3l_{0})$.

##### Case
$\mathopen{}\left|u\right|\mathclose{}\neq\mathopen{}\left|u^{\prime}\right|\mathclose{}$
and
$\mathopen{}\left|v\right|\mathclose{}\neq\mathopen{}\left|v^{\prime}\right|\mathclose{}$.

Then, we can again exploit the fact that matching $u^{3}$ with $vv^{\prime}v$
or $uu^{\prime}u$ with $v^{3}$ makes us fall down to a smaller
$\mathrel{\mathfrak{J}}$-class to reduce $\mathcal{L}_{A\cdot
B^{\prime},A^{\prime}\cdot B}$ where
$A=3\mathopen{}\left|u\right|\mathclose{}=3k_{0}$,
$A^{\prime}=2\mathopen{}\left|u\right|\mathclose{}+\mathopen{}\left|u^{\prime}\right|\mathclose{}=2k_{0}+k_{0}^{\prime}$,
$B=3\mathopen{}\left|v\right|\mathclose{}=3l_{0}$ and
$B^{\prime}=2\mathopen{}\left|v\right|\mathclose{}+\mathopen{}\left|v^{\prime}\right|\mathclose{}=2l_{0}+l_{0}^{\prime}$
to $L_{\psi_{L}(\operatorname{ext}_{u,v})}$. Indeed, we have $A\cdot
B^{\prime}\neq A^{\prime}\cdot B$ because otherwise we would have

$\displaystyle
3\mathopen{}\left|u\right|\mathclose{}\cdot(2\mathopen{}\left|v\right|\mathclose{}+\mathopen{}\left|v^{\prime}\right|\mathclose{})$
$\displaystyle=(2\mathopen{}\left|u\right|\mathclose{}+\mathopen{}\left|u^{\prime}\right|\mathclose{})\cdot
3\mathopen{}\left|v\right|\mathclose{}$ $\displaystyle
6\mathopen{}\left|u\right|\mathclose{}\mathopen{}\left|v\right|\mathclose{}+3\mathopen{}\left|u\right|\mathclose{}\mathopen{}\left|v^{\prime}\right|\mathclose{}$
$\displaystyle=6\mathopen{}\left|u\right|\mathclose{}\mathopen{}\left|v\right|\mathclose{}+3\mathopen{}\left|u^{\prime}\right|\mathclose{}\mathopen{}\left|v\right|\mathclose{}$
$\displaystyle\mathopen{}\left|u\right|\mathclose{}\mathopen{}\left|v^{\prime}\right|\mathclose{}$
$\displaystyle=\mathopen{}\left|u^{\prime}\right|\mathclose{}\mathopen{}\left|v\right|\mathclose{}\,\,\text{.}$

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

  1. 1.

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

  2. 2.

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

  3. 3.

accept whenever $x^{\prime}\\#y^{\prime}\in
L_{\psi_{L}(\operatorname{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},\ldots,z_{n}\in\\{ac^{A\cdot
B^{\prime}-1},ac^{A^{\prime}\cdot B-1}\\}$ and $y=t_{1}\cdots t_{m}$ where
$m\in\mathbb{N}$ and $t_{1},\ldots,t_{m}\in\\{b_{1},b_{2}\\}$. Consider
$x^{\prime}\\#y^{\prime}$ produced by the reduction with
$x^{\prime}=z_{1}^{\prime}\cdots z_{n}^{\prime}$ where
$z_{1}^{\prime},\ldots,z_{n}^{\prime}\in\\{(u^{3})^{B^{\prime}},(uu^{\prime}u)^{B}\\}$
and $y^{\prime}=t_{1}^{\prime}\cdots t_{m}^{\prime}$ where
$t_{1}^{\prime},\ldots,t_{m}^{\prime}\in\\{(v^{3})^{B^{\prime}},(vv^{\prime}v)^{B}\\}$.
If $w\in\mathcal{L}_{A\cdot B^{\prime},A^{\prime}\cdot B}$, then it easily
follows that $x^{\prime}\\#y^{\prime}\in
L_{\psi_{L}(\operatorname{ext}_{u,v})}$. Otherwise, if
$w\notin\mathcal{L}_{A\cdot B^{\prime},A^{\prime}\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^{\prime},A^{\prime}\cdot
B}$ but it holds that $(z_{i},t_{i})\in\\{(ac^{A\cdot
B^{\prime}-1},b_{2}),(ac^{A^{\prime}\cdot B-1},b_{1})\\}$. Assume first
$(z_{i},t_{i})=(ac^{A^{\prime}\cdot B-1},b_{1})$. In this case, let
$\tilde{x}^{\prime}=(uu^{\prime}u)^{B-1}z_{i+1}^{\prime}\cdots z_{n}^{\prime}$
and $\tilde{y}^{\prime}=t_{n}^{\prime}\cdots
t_{i+1}^{\prime}(v^{3})^{B^{\prime}-1}$. If
$\Delta(\tilde{x}^{\prime}\tilde{y}^{\prime})\neq 0$, then

$\Delta(x^{\prime}y^{\prime})=\Delta(z_{1}^{\prime}\cdots
z_{i-1}^{\prime}(uu^{\prime}u)v^{3}t_{i-1}^{\prime}\cdots
t_{1}^{\prime})+\Delta(\tilde{x}^{\prime}\tilde{y}^{\prime})=\Delta(\tilde{x}^{\prime}\tilde{y}^{\prime})\neq
0\,\,\text{,}$

thus $x^{\prime}y^{\prime}$ is not well-matched. Otherwise, if
$\Delta(\tilde{x}^{\prime}\tilde{y}^{\prime})=0$, we can show that
$\tilde{x}^{\prime}\tilde{y}^{\prime}$ is well-matched. Indeed, since
$uv\in\Sigma^{\triangle}$, for all
$j\in[1,\mathopen{}\left|u\right|\mathclose{}]$, we have $\Delta(u_{1}\cdots
u_{j})\geq 0$ and for all $j\in[1,\mathopen{}\left|v\right|\mathclose{}]$, we
have $\Delta(v_{j}\cdots
v_{\mathopen{}\left|v\right|\mathclose{}})=-\Delta(uv_{1}\cdots v_{j-1})\leq
0$. Similarly, since $u^{\prime}v^{\prime}\in\Sigma^{\triangle}$, for all
$j\in[1,\mathopen{}\left|u^{\prime}\right|\mathclose{}]$, we have
$\Delta(u^{\prime}_{1}\cdots u^{\prime}_{j})\geq 0$ and for all
$j\in[1,\mathopen{}\left|v^{\prime}\right|\mathclose{}]$, we have
$\Delta(v^{\prime}_{j}\cdots
v^{\prime}_{\mathopen{}\left|v^{\prime}\right|\mathclose{}})=-\Delta(u^{\prime}v^{\prime}_{1}\cdots
v^{\prime}_{j-1})\leq 0$. This implies that for all
$j\in[1,\mathopen{}\left|\tilde{x}^{\prime}\right|\mathclose{}]$, we have
$\Delta(\tilde{x}^{\prime}_{1}\cdots\tilde{x}^{\prime}_{j})\geq 0$ and for all
$j\in[1,\mathopen{}\left|\tilde{y}^{\prime}\right|\mathclose{}]$, we have
$\Delta(\tilde{x}^{\prime}\tilde{y}^{\prime}_{1}\cdots\tilde{y}^{\prime}_{j-1})=-\Delta(\tilde{y}^{\prime}_{j}\cdots\tilde{y}^{\prime}_{\mathopen{}\left|\tilde{y}^{\prime}\right|\mathclose{}})\geq
0$. Therefore, $\tilde{x}^{\prime}\tilde{y}^{\prime}\in\Sigma^{\triangle}$.
Hence $x^{\prime}y^{\prime}$ is well-matched and

$\operatorname{ext}_{x^{\prime},y^{\prime}}=\operatorname{ext}_{z_{1}^{\prime}\cdots
z_{i-1}^{\prime},t_{i-1}^{\prime}\cdots
t_{1}^{\prime}}\circ\operatorname{ext}_{z_{i}^{\prime},t_{i}^{\prime}}\circ\operatorname{ext}_{\tilde{x}^{\prime},\tilde{y}^{\prime}}\,\,\text{,}$

so that

$\psi_{L}(\operatorname{ext}_{x^{\prime},y^{\prime}})\leq_{\mathfrak{J}}\psi_{L}(\operatorname{ext}_{z_{i}^{\prime},t_{i}^{\prime}})<_{\mathfrak{J}}\psi_{L}(\operatorname{ext}_{u,v})\,\,\text{.}$

If we assume that $(z_{i},t_{i})=(ac^{A\cdot B^{\prime}-1},b_{2})$, then we
prove in the same way that either $x^{\prime}y^{\prime}$ is not well-matched
or it is well-matched and
$\psi_{L}(\operatorname{ext}_{x^{\prime},y^{\prime}})<_{\mathfrak{J}}\psi_{L}(\operatorname{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^{\prime},A^{\prime}\cdot B}$. This entails that
$\Delta(x^{\prime}t_{n}^{\prime}\cdots
t_{1}^{\prime})=\Delta(z_{1}^{\prime}\cdots z_{n}^{\prime}t_{n}^{\prime}\cdots
t_{1}^{\prime})=0$, so that

$\Delta(x^{\prime}y^{\prime})=\Delta(x^{\prime}t_{n}^{\prime}\cdots
t_{1}^{\prime})+\Delta(t_{m}^{\prime}\cdots
t_{n+1}^{\prime})=\Delta(t_{m}^{\prime}\cdots t_{n+1}^{\prime})<0$

because $m>n$ and $\Delta(v)<0$ as well as $\Delta(v^{\prime})<0$. Therefore,
$x^{\prime}y^{\prime}$ 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^{\prime},A^{\prime}\cdot B}$. Symmetrically to
the previous case, we can also show that then, $x^{\prime}y^{\prime}$ is not
well-matched.

Hence, our algorithm outputs the pair $(k,l)=(A\cdot
B^{\prime},A^{\prime}\cdot
B)=(3k_{0}(2l_{0}+l_{0}^{\prime}),(2k_{0}+k_{0}^{\prime})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^{\prime}$ a DVPA such that
$L(A^{\prime})=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 $\mathsf{AC}^{0}$ or some $m\geq 2$ such
that $\mathrm{MOD}_{m}\leq_{\text{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
$\operatorname{Ext}$-algebra of $L$ along with with its syntactic morphism
$(\varphi_{L},\psi_{L}):(\Sigma^{\triangle},\mathcal{O}(\Sigma^{\triangle}))\rightarrow(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
$\operatorname{ext}_{u,v}\in\mathcal{O}(\Sigma^{\triangle})$ we assign the
triple
$\zeta(\operatorname{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^{\prime}$ where $q^{\prime}\in Q$ is the unique state such that
$q(i)\xrightarrow{u}_{A}q^{\prime}(i+j)$ for all $q\in Q$ and all $i\in[0,m]$,
and

  * •

$g_{i}(q)=q^{\prime}$, where $q^{\prime}\in Q$ is the unique state such that
$q^{\prime}(i+j)\xrightarrow{v}_{A}q^{\prime}(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^{\prime},(f_{i}^{\prime})_{i\in[0,m]},(g_{i}^{\prime})_{i\in[0,m]})$

as

$(\min(j+j^{\prime},m),(f_{\min(i+j,m)}^{\prime}\circ
f_{i})_{i\in[0,m]},(g_{\min(i+j,m)}\circ
g_{\min(i+j+j^{\prime},m)}^{\prime})_{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^{\prime}=(j^{\prime},(f_{i}^{\prime})_{i\in[0,m]},(g_{i}^{\prime})_{i\in[0,m]})\in\mathcal{M}$,
and

  * •

$m^{\prime\prime}=(j^{\prime\prime},(f_{i}^{\prime\prime})_{i\in[0,m]},(g_{i}^{\prime\prime})_{i\in[0,m]})\in\mathcal{M}$.

Let
$\widetilde{m}=m\odot_{\mathcal{M}}m^{\prime}=(\widetilde{j},(\widetilde{f_{i}})_{i\in[0,m]},(\widetilde{g_{i}})_{i\in[0,m]})$
and
$\overline{m}=m^{\prime}\odot_{\mathcal{M}}m^{\prime\prime}=(\overline{j},(\overline{f_{i}})_{i\in[0,m]},(\overline{g_{i}})_{i\in[0,m]})$.
We need to prove
$\widetilde{m}\odot_{\mathcal{M}}m^{\prime\prime}=m\odot_{\mathcal{M}}\overline{m}$.

Since $j,j^{\prime},j^{\prime\prime},m\geq 0$ we have
$\min(\widetilde{j}+j^{\prime\prime},m)=\min(\min(j+j^{\prime},m)+j^{\prime\prime},m)=\min(j+j^{\prime}+j^{\prime\prime},m)=\min(j+\min(j^{\prime}+j^{\prime\prime},m),m))=\min(j+\overline{j},m)$
associativity holds on the first component. For each $i\in[0,m]$ the
$i^{\text{th}}$ component of the second component of
$\widetilde{m}\odot_{\mathcal{M}}m^{\prime\prime}$ is

$\displaystyle
f_{\min(i+\widetilde{j},m)}^{\prime\prime}\circ\widetilde{f}_{i}$
$\displaystyle=$ $\displaystyle
f_{\min(i+\widetilde{j},m)}^{\prime\prime}\circ\left(f_{\min(i+j,m)}^{\prime}\circ
f_{i}\right)$ $\displaystyle=$ $\displaystyle
f_{\min(i+\min(j+j^{\prime},m),m)}^{\prime\prime}\circ\left(f_{\min(i+j,m)}^{\prime}\circ
f_{i}\right)$ $\displaystyle=$ $\displaystyle
f_{\min(i+j+j^{\prime},m)}^{\prime\prime}\circ\left(f_{\min(i+j,m)}^{\prime}\circ
f_{i}\right)$ $\displaystyle=$
$\displaystyle\left(f_{\min(i+j^{\prime}+j^{\prime\prime},m)}^{\prime\prime}\circ
f_{\min(i+j,m)}^{\prime}\right)\circ f_{i}$ $\displaystyle=$
$\displaystyle\left(f_{\min(\min(i+j,m)+j^{\prime},m)}^{\prime\prime}\circ
f_{\min(i+j,m)}^{\prime}\right)\circ f_{i}$ $\displaystyle=$
$\displaystyle\overline{f}_{\min(i+j,m)}\circ f_{i}$

the latter of which is the $i^{\text{th}}$ component of the second component
of $m\odot_{\mathcal{M}}\overline{m}$, as required. For each $i\in[0,m]$ the
$i^{\text{th}}$ component of the third component of
$m\odot_{\mathcal{M}}\overline{m}$ is

$\displaystyle g_{\min(i+j,m)}\circ\overline{g}_{\min(i+j+\overline{j},m))}$
$\displaystyle=$ $\displaystyle
g_{\min(i+j,m)}\circ\overline{g}_{\min(i+j+j^{\prime}+j^{\prime\prime},m)}$
$\displaystyle=$ $\displaystyle
g_{\min(i+j,m)}\circ\overline{g}_{\min(\min(i+j,m)+j^{\prime}+j^{\prime\prime},m)}$
$\displaystyle=$ $\displaystyle
g_{\min(i+j,m)}\circ\left(g_{\min(\min(i+j,m)+j^{\prime})}^{\prime}\circ
g_{\min(\min(i+j,m),j^{\prime}+j^{\prime\prime},m)}^{\prime\prime}\right)$
$\displaystyle=$ $\displaystyle\left(g_{\min(i+j,m)}\circ
g_{\min(\min(i+j,m)+j^{\prime})}^{\prime}\right)\circ
g_{\min(\min(i+j,m),j^{\prime}+j^{\prime\prime},m)}^{\prime\prime}$
$\displaystyle=$ $\displaystyle\left(g_{\min(i+j,m)}\circ
g_{\min(i+j+j^{\prime},m)}^{\prime}\right)\circ
g_{\min(i+\min(j+j^{\prime},m)+j^{\prime\prime},m)}^{\prime\prime}$
$\displaystyle=$ $\displaystyle\widetilde{g}_{i}\circ
g_{\min(i+\widetilde{j}+j^{\prime\prime},m)}^{\prime\prime}$

the latter of which is the $i^{\text{th}}$ component of the third component of
$\widetilde{m}\odot_{\mathcal{M}}m^{\prime\prime}$, as required. Clearly
$(0,(\mathrm{id}_{Q})^{[0,m]},(\mathrm{id}_{Q})^{[0,m]})$ is the identity of
$\mathcal{M}$ with respect to $\odot_{\mathcal{M}}$, hence
$(\mathcal{M},\odot_{\mathcal{M}})$ is a monoid. The following points can
easily be verified.

  1. 1.

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

  2. 2.

For all
$\operatorname{ext}_{u,v},\operatorname{ext}_{u^{\prime},v^{\prime}}\in\mathcal{O}(\Sigma^{\triangle})$
with $\Delta(u)=\Delta(u^{\prime})$ we have

$\zeta(\operatorname{ext}_{u,v})=\zeta(\operatorname{ext}_{u^{\prime},v^{\prime}})\quad\Longrightarrow\quad\zeta(\operatorname{ext}_{u,v})=\zeta(\operatorname{ext}_{u^{\prime},v})=\zeta(\operatorname{ext}_{u,v^{\prime}})=\zeta(\operatorname{ext}_{u^{\prime},v^{\prime}}).$

  3. 3.

For all
$\operatorname{ext}_{u,v},\operatorname{ext}_{u^{\prime},v^{\prime}}\in\mathcal{O}(\Sigma^{\triangle})$
we have

$\zeta(\operatorname{ext}_{u,v})=\zeta(\operatorname{ext}_{u^{\prime},v^{\prime}})\quad\Longrightarrow\quad\psi_{L}(\operatorname{ext}_{u,v})=\psi_{L}(\operatorname{ext}_{u^{\prime},v^{\prime}}).$

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
$\operatorname{ext}_{u,v},\operatorname{ext}_{u^{\prime},v^{\prime}}\in\mathcal{O}(\Sigma^{\triangle})$
such that $\Delta(u),\Delta(u^{\prime})>0$,
$\frac{|u|}{|v|}\not=\frac{|u^{\prime}|}{|v^{\prime}|}$, and
$\psi_{L}(\operatorname{ext}_{u,v})=\psi_{L}(\operatorname{ext}_{u^{\prime},v^{\prime}})=e$.
Without loss of generality we may assume $\Delta(u)=\Delta(u^{\prime})$. Let
$\omega$ denote the idempotent power of $\mathcal{M}$. Consider the elements

$\operatorname{ext}_{x,y}=(\operatorname{ext}_{u,v}^{2\omega}\circ\operatorname{ext}_{u^{\prime},v^{\prime}}^{\omega})^{\omega}\text{~and
}\operatorname{ext}_{x^{\prime},y^{\prime}}=(\operatorname{ext}_{u,v}^{\omega}\circ\operatorname{ext}_{u^{\prime},v^{\prime}}^{2\omega})^{\omega}.$

By definition we have
$\zeta(\operatorname{ext}_{x,y})=\zeta(\operatorname{ext}_{x^{\prime},y^{\prime}})$,
and since $\Delta(x)=\Delta(x^{\prime})$ we obtain
$\zeta(\operatorname{ext}_{x,y})=\zeta(\operatorname{ext}_{x^{\prime},y})=\zeta(\operatorname{ext}_{x,y^{\prime}})=\zeta(\operatorname{ext}_{x^{\prime},y^{\prime}})$
by Point 2. Hence,

$\displaystyle\psi_{L}(\operatorname{ext}_{x,y})=\psi_{L}(\operatorname{ext}_{x^{\prime},y})=\psi_{L}(\operatorname{ext}_{x,y^{\prime}})=\psi_{L}(\operatorname{ext}_{x^{\prime},y^{\prime}})=e$

by Point 3.

We finally make a case distinction on whether $|u|=|u^{\prime}|$ or not.

First, assume $|u|\not=|u^{\prime}|$. Then $|x|\not=|x^{\prime}|$ by
construction. Since
$\psi_{L}(\operatorname{ext}_{x,y})=\psi_{L}(\operatorname{ext}_{x^{\prime},y})=e$,
which is an idempotent of $O_{L}$, we obtain that $L$ is not weakly length-
synchronous.

Now assume $|u|=|u^{\prime}|$. Since
$\frac{|u|}{|v|}\not=\frac{|u^{\prime}|}{|v^{\prime}|}$ by assumption, we
conclude that $|v|\not=|v^{\prime}|$. By construction, the latter implies
$|y|\not=|y^{\prime}|$. Since
$\psi_{L}(\operatorname{ext}_{x,y})=\psi_{L}(\operatorname{ext}_{x,y^{\prime}})=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 $\operatorname{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
$\operatorname{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 $\operatorname{Ext}$-algebra $(R,O)$ it follows from Proposition
3.7 that each morphism
$(\varphi,\psi)\colon(\Sigma^{\triangle},\mathcal{O}(\Sigma^{\triangle}))\rightarrow(R,O)$
has a unique finite presentation: it is given by the tuples

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

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

  1. 1.

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

  2. 2.

$x^{\prime}y^{\prime}=z^{\prime}\Leftrightarrow\alpha^{-1}(x^{\prime})\alpha^{-1}(y^{\prime})=\alpha^{-1}(z^{\prime})$
for all $x^{\prime},y^{\prime},z^{\prime}\in R_{L}$;

  3. 3.

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

  4. 4.

$f^{\prime}(x^{\prime})=y^{\prime}\Leftrightarrow\beta^{-1}(f^{\prime})(\alpha^{-1}(x^{\prime}))=\alpha^{-1}(y^{\prime})$
for all $f^{\prime}\in O_{L}$ and all $x^{\prime},y^{\prime}\in R_{L}$.

For the following claim we avoid the tedious standard algebraic constructions
on $\operatorname{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
$\operatorname{Ext}$-algebras
$(\varphi_{1},\psi_{1})\colon(\Sigma^{\triangle},\mathcal{O}(\Sigma^{\triangle}))\rightarrow(R_{1},O_{1})$
and
$(\varphi_{2},\psi_{2})\colon(\Sigma^{\triangle},\mathcal{O}(\Sigma^{\triangle}))\rightarrow(R_{1},O_{1})$
for $\Sigma$ a visibly pushdown 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})$. ∎

###### Proof of Proposition 6.1.

By Theorem 3.18 we first compute from our DVPA $A$ on the visibly pushdown
alphabet $\Sigma$ an $\operatorname{Ext}$-algebra $(R_{A},O_{A})$, a morphism
$(\varphi_{A},\psi_{A})\colon(\Sigma^{\triangle},\mathcal{O}(\Sigma^{\triangle}))\to(R_{A},O_{A})$,
and a subset $F_{A}\subseteq R_{A}$ such that $L(A)=\varphi_{A}^{-1}(F_{A})$.
For an $\operatorname{Ext}$-algebra $(R,O)$ define
$\\#(R,O)=(\left|R\right|,\left|O\right|)$. Let
$\prec\subseteq(\mathbb{N}\times\mathbb{N})^{2}$ be the lexicographic order on
$\mathbb{N}\times\mathbb{N}$, i.e. $(i,j)\prec(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
$\operatorname{Ext}$-algebra $(R_{L},O_{L})$ of $L$ divides $(R_{A},O_{A})$ by
Proposition 3.17, so that $\\#(R_{L},O_{L})\leq\\#(R_{A},O_{A})$. In fact, we
have that any $\operatorname{Ext}$-algebra $(R,O)$ having $[1,i]$ for
$i\in[1,\left|R_{L}\right|]$ as base set, satisfying
$\\#(R,O)\leq\\#(R_{L},O_{L})$ and recognizing $L$ via a morphism
$(\varphi,\psi)\colon(\Sigma^{\triangle},\mathcal{O}(\Sigma^{\triangle}))\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 $\operatorname{Ext}$-algebra recognizes $L$, by
Proposition 3.17 it is divided by $(R_{L},O_{L})$: this implies that
$\\#(R_{L},O_{L})\leq\\#(R,O)$, but as also $\\#(R,O)\leq\\#(R_{L},O_{L})$, we
have $\\#(R,O)=\\#(R_{L},O_{L})$. The morphism $(\varphi,\psi)$ must be
surjective, otherwise, by Lemma 3.15,
$\bigl{(}\varphi(\Sigma^{\triangle}),{\psi(\mathcal{O}(\Sigma^{\triangle}))|}_{\varphi(\Sigma^{\triangle})}\bigr{)}$
would be a sub-$\operatorname{Ext}$-algebra of $(R,O)$ recognizing $L$ such
that
$\\#\bigl{(}\varphi(\Sigma^{\triangle}),{\psi(\mathcal{O}(\Sigma^{\triangle}))|}_{\varphi(\Sigma^{\triangle})}\bigr{)}<\\#(R,O)=\\#(R_{L},O_{L})$
while $(R_{L},O_{L})$ divides
$\bigl{(}\varphi(\Sigma^{\triangle}),{\psi(\mathcal{O}(\Sigma^{\triangle}))|}_{\varphi(\Sigma^{\triangle})}\bigr{)}$,
which is contradictory. Therefore, by Lemma 3.16, there is a surjective
morphism $(\alpha,\beta)\colon(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 $\operatorname{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
$\operatorname{Ext}$-algebra $(R,O)$, a morphism
$(\varphi,\psi)\colon(\Sigma^{\triangle},\mathcal{O}(\Sigma^{\triangle}))\to(R,O)$
and a subset $F\subseteq R$ such that $R$ has $[1,i]$ for
$i\in[1,\left|R_{A}\right|]$ as base set and $\\#(R,O)\leq\\#(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
$\prec$.

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

  * •

$x\cdot\alpha(1_{R})=\alpha\bigl{(}\alpha^{-1}(x)\alpha^{-1}(\alpha(1_{R}))\bigr{)}=\alpha(\alpha^{-1}(x))=\alpha\bigl{(}\alpha^{-1}(\alpha(1_{R}))\alpha^{-1}(x)\bigr{)}=\alpha(1_{R})\cdot
x$ for all $x\in R$; and

  * •

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

$\displaystyle x\cdot(y\cdot z)$
$\displaystyle=\alpha\biggl{(}\alpha^{-1}(x)\alpha^{-1}\Bigl{(}\alpha\bigl{(}\alpha^{-1}(y)\alpha^{-1}(z)\bigr{)}\Bigr{)}\biggr{)}$
$\displaystyle=\alpha\bigl{(}\alpha^{-1}(x)\alpha^{-1}(y)\alpha^{-1}(z)\bigr{)}$
$\displaystyle=\alpha\biggl{(}\alpha^{-1}\Bigl{(}\alpha\bigl{(}\alpha^{-1}(x)\alpha^{-1}(y)\bigr{)}\Bigr{)}\alpha^{-1}(z)\biggr{)}$
$\displaystyle=(x\cdot y)\cdot z\,\,\text{.}$

Define the function $\beta\colon O_{L}\to R^{R}$ by
$\beta(f^{\prime})(x)=\alpha\bigl{(}f^{\prime}(\alpha^{-1}(x))\bigr{)}$ for
all $f^{\prime}\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\bigl{(}1_{O}(\alpha^{-1}(x))\bigr{)}=x=\mathrm{id}_{R}(x)$
for all $x\in R$; and

  * •

for all $f^{\prime},g^{\prime}\in O_{L}$,

$\beta(f^{\prime})\circ\beta(g^{\prime})(x)=\alpha\Biggl{(}f^{\prime}\biggl{(}\alpha^{-1}\Bigl{(}\alpha\bigl{(}g^{\prime}(\alpha^{-1}(x))\bigr{)}\Bigr{)}\biggr{)}\Biggr{)}=\alpha\bigl{(}f^{\prime}\circ
g^{\prime}(\alpha^{-1}(x))\bigr{)}=\beta(f^{\prime}\circ g^{\prime})(x)$

for all $x\in R$, so that $\beta(f^{\prime})\circ\beta(g^{\prime})\in O$.

Then $(R,O)$ is an $\operatorname{Ext}$-algebra, because for all
$r^{\prime}\in R_{L}$, we have

$\beta(\mathrm{left}_{r^{\prime}})(x)=\alpha\bigl{(}\mathrm{left}_{r^{\prime}}(\alpha^{-1}(x))\bigr{)}=\alpha\bigl{(}\alpha^{-1}(\alpha(r^{\prime}))\alpha^{-1}(x)\bigr{)}=\alpha(r^{\prime})\cdot
x=\mathrm{left}_{\alpha(r^{\prime})}(x)$

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

We now define
$(\varphi,\psi)\colon(\Sigma^{\triangle},\mathcal{O}(\Sigma^{\triangle}))\to(R,O)$
as the unique morphism satisfying $\varphi(c)=\alpha(\varphi_{L}(c))$ for all
$c\in\Sigma_{\text{int}}$ and
$\psi(\operatorname{ext}_{a,b})=\beta(\psi_{L}(\operatorname{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^{\triangle}$ by structural induction on $w$. Hence, by injectivity
of $\alpha$, we have

$\displaystyle\varphi^{-1}\bigl{(}\alpha(\varphi_{L}(L))\bigr{)}$
$\displaystyle=\\{w\in\Sigma^{\triangle}\mid\alpha(\varphi_{L}(w))\in\alpha(\varphi_{L}(L))\\}$
$\displaystyle=\\{w\in\Sigma^{\triangle}\mid\varphi_{L}(w)\in\varphi_{L}(L)\\}=\varphi_{L}^{-1}(\varphi_{L}(L))=L\,\,\text{,}$

thus $(R,O)$ recognizes $L$. ∎

###### 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)\colon(\Sigma^{\triangle},\mathcal{O}(\Sigma^{\triangle}))\to(R,O)$
for $\Sigma$ a visibly pushdown alphabet and $(R,O)$ a finite
$\operatorname{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^{\triangle})^{k,l})$ is not aperiodic.

For the rest of this paragraph, let us fix a morphism
$(\varphi,\psi)\colon(\Sigma^{\triangle},\mathcal{O}(\Sigma^{\triangle}))\to(R,O)$,
where $\Sigma$ is a visibly pushdown alphabet and $(R,O)$ is some finite
$\operatorname{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
$\operatorname{Ext}$-algebra recognizing $L_{e}=\\{u\\#v\mid
uv\in\Sigma^{\triangle}:\psi(\operatorname{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^{\prime}$ be the alphabet that emerges from $\Sigma$ by
additionally declaring $\\#$ as an internal letter. We will construct an
$\operatorname{Ext}$-algebra $(R^{\prime},O^{\prime})$ and a morphism
$(\varphi^{\prime},\psi^{\prime})\colon(\Sigma^{\prime\triangle},\mathcal{O}(\Sigma^{\prime})^{\triangle})\to(R^{\prime},O^{\prime})$
such that for some element $r^{\prime}\in R^{\prime}$ we have
$L_{e}=\varphi^{\prime-1}(r^{\prime})$.

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

  * •

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

  * •

$r\cdot f=\mathrm{left}_{r}\circ f$ and $f\cdot r=\mathrm{right}_{r}\circ f$
for all $r\in R$ and all $f\in O$;

  * •

$\bot$ acts as a zero, i.e. $\bot\cdot r^{\prime}=r^{\prime}\cdot\bot=\bot$
for all $r^{\prime}\in R^{\prime}$;

  * •

$f\cdot g=\bot$ for all $f,g\in O$.

Clearly the identity of $R$ is the identity of $R^{\prime}$. 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

$\displaystyle(r_{1}\cdot f)\cdot r_{2}$
$\displaystyle=(\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$
$\displaystyle=(\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})\,\,\text{.}$

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}\,\,\text{.}$

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

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

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

$\varphi^{\prime}(w)=\begin{cases}\varphi(w)&\text{ if
$w\in\Sigma^{\triangle}$}\\\ \psi(\operatorname{ext}_{u,v})&\text{ if
$w=u\\#v$ for some $uv\in\Sigma^{\triangle}$}\\\ \bot&\text{
otherwise.}\end{cases}$

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

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

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

$\varphi^{\prime}(xy)=\varphi^{\prime}(x)\cdot\varphi^{\prime}(y)=\varphi(x)\cdot\psi(\operatorname{ext}_{u,v})=\mathrm{left}_{\varphi(x)}\circ\psi(\operatorname{ext}_{u,v})=\psi(\operatorname{ext}_{xu,v})$

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

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

as required. ∎

The next goal will be to prove that the set of pairs of word lengths
$(\mathopen{}\left|u\right|\mathclose{},\mathopen{}\left|v\right|\mathclose{})$
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,\bot)$, 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, $\bot\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^{*}\bot$ if $X=\bot$ and
$\alpha\in(\Gamma\setminus\\{\bot\\})^{*}$ otherwise. The relation $\Omega$ is
naturally extended to the relation $\Omega^{*}\subseteq
Q\times\Sigma^{*}\times\Gamma^{*}\bot\times Q\times\Gamma^{*}\bot$, namely as
the smallest relation containing the set
$\\{(p,\varepsilon,\alpha,p,\alpha)\mid p\in Q,\alpha\in\Gamma^{*}\bot\\}$ 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^{*}\bot,\exists q\in
F:(q_{0},w,\bot,q,\alpha)\in\Omega^{*}\\}$. Hence it is clear that one can
compute a PDA $A^{\prime}$ such that $L(A^{\prime})=L(A)$.

######  Lemma 6.5.

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

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

is effectively semilinear.

###### Proof.

We first compute a PDA $A^{\prime}$ accepting the same language as $A$, i.e.
$L(A^{\prime})=L(A)$. Let us assume without loss of generality that
$0,1\not\in\Sigma^{\prime}$. We claim that from
$A^{\prime}=(Q,\Sigma^{\prime},\Gamma,\Omega,q_{0},F,\bot)$ one can compute a
PDA $A^{\prime\prime}$ such that

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

Indeed, the PDA $A^{\prime\prime}$ can simply be computed as follows: we set

$A^{\prime\prime}=(Q\times\\{0,1\\},\\{0,1,\\#\\},\Gamma,\Omega^{\prime},\langle
q_{0},0\rangle,F\times\\{1\\},\bot)\,\,\text{,}$

where $\Omega^{\prime}$ is the union of $\\{(\langle p,i\rangle,i,X,\langle
q,i\rangle,\alpha)\mid i\in\\{0,1\\},\exists
c\in\Sigma^{\prime}\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^{\prime\prime})\\}=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
$\operatorname{Ext}$-algebra recoginizing $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^{\triangle},\psi(\operatorname{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^{\triangle})^{k,l})$ is not aperiodic. ∎

###### 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)\colon(\Sigma^{\triangle},\mathcal{O}(\Sigma^{\triangle}))\to(R,O)$,
for $\Sigma$ a visibly pushdown alphabet and $(R,O)$ a finite
$\operatorname{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^{\prime},l^{\prime})\in\mathbb{N}_{>0}^{4}$ such that that there exist
$uv,u^{\prime}v^{\prime}\in\Sigma^{\triangle}$ and some $F$-reachable
idempotent $e\in O$ such that
$\psi(\operatorname{ext}_{u,v})=\psi(\operatorname{ext}_{u^{\prime},v^{\prime}})=e$,
$k=|u|$, $l=|v|$, $k^{\prime}=|u^{\prime}|$, $l^{\prime}=|v^{\prime}|$ and
$\frac{k}{l}\not=\frac{k^{\prime}}{l^{\prime}}$.

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}\left(\vec{x}_{i,0}+\sum_{j=1}^{t_{i}}\mathbb{N}\vec{x}_{i,j}\right)\subseteq\mathbb{N}_{>0}^{2}$
be a non-empty semilinear set, where $\vec{x}_{i,j}\not=(0,0)$ for all $i\in
I$ and all $j\in[0,t_{i}]$. Then,

$\left|\left\\{\frac{k}{l}\Big{|}(k,l)\in
S\right\\}\right|=1\quad\Longleftrightarrow\quad\forall i,i^{\prime}\in I\
\forall j\in[0,t_{i}]\ \forall
j^{\prime}\in[0,t_{i^{\prime}}]:\vec{x}_{i,j}\text{ and
}\vec{x}_{i^{\prime},j^{\prime}}\text{ are collinear}.$

###### Proof.

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

Conversely assume that there exist two vectors $(k,l)=\vec{x}_{i,j}$ and
$(k^{\prime},l^{\prime})=\vec{x}_{i^{\prime},j^{\prime}}$ that are not
collinear. In case this is possible when $i\not=i^{\prime}$ and
$j=j^{\prime}=0$ we are done, since then $(k,l),(k^{\prime},l^{\prime})\in S$
and thus $\frac{k}{l}\not=\frac{k^{\prime}}{l^{\prime}}$. Otherwise
$\vec{x}_{i,0}$ and $\vec{x}_{i^{\prime},0}$ are collinear for all
$i,i^{\prime}\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^{\prime},l^{\prime})\in S$ that are
not collinear, and therefore $\frac{k}{l}\not=\frac{k^{\prime}}{l^{\prime}}$.
∎

###### Proof of Proposition 6.6.

Let us fix the $\operatorname{Ext}$-algebra morphism
$(\varphi,\psi)\colon(\Sigma^{\triangle},\mathcal{O}(\Sigma^{\triangle}))\to(R,O)$,
where $(R,O)$ is a finite $\operatorname{Ext}$-algebra and where $F\subseteq
R$.

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

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

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

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

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}\mid(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}\mid(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^{\prime},l^{\prime})\in\mathbb{N}_{>0}^{4}$ such that for some
$F$-reachable idempotent $e\in O$ we have $(k,l),(k^{\prime},l^{\prime})\in
P(L_{e\uparrow})$ and $\frac{k}{l}\not=\frac{k^{\prime}}{l^{\prime}}$. ∎

###### 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)\colon(\Sigma^{\triangle},\mathcal{O}(\Sigma^{\triangle}))\to(R,O)$,
for $\Sigma$ a visibly pushdown alphabet and $(R,O)$ a finite
$\operatorname{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)\colon(\Sigma^{\triangle},\mathcal{O}(\Sigma^{\triangle}))\to(R,O)$,
for $\Sigma$ a visibly pushdown alphabet and $(R,O)$ a finite
$\operatorname{Ext}$-algebra, and some $F\subseteq R$.

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

$\overline{w}=\begin{cases}\varepsilon&\text{if $w=\varepsilon$}\\\
\overline{w_{n}}\cdots\overline{w_{1}}&\text{if $w=w_{1}\cdots w_{n}$ for
$n\in\mathbb{N}_{>0}$ and $w_{1},\ldots
w_{n}\in\Sigma$}\,\,\text{.}\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
$\operatorname{Ext}$-algebra recognizing the language of well-matched words
$K_{e}=\\{u\\#\overline{u^{\prime}}\mid u,u^{\prime}\in\Sigma^{*},\exists
v\in\Sigma^{*}:uv\in\Sigma^{\triangle},u^{\prime}v\in\Sigma^{\triangle},\psi(\operatorname{ext}_{u,v})=\psi(\operatorname{ext}_{u^{\prime},v})=e\\}$,
where $\\#$ is a fresh internal letter that does not appear in
$\Sigma\cup\overline{\Sigma}$, along with an associated morphism and subset.

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

$\displaystyle K_{e\uparrow}$
$\displaystyle=\biggl{\\{}u\\#\overline{u^{\prime}}\mathrel{\bigg{|}}\begin{aligned}
&u,u^{\prime}\in\Sigma^{*},\exists v\in\Sigma^{*}:\\\
&uv\in\Sigma^{\triangle},u^{\prime}v\in\Sigma^{\triangle},\Delta(u)>0,\psi(\operatorname{ext}_{u,v})=\psi(\operatorname{ext}_{u^{\prime},v})=e\end{aligned}\biggr{\\}}$
$\displaystyle=K_{e}\cap\\{u\\#u^{\prime}\mid
uu^{\prime}\in(\Sigma\cup\overline{\Sigma})^{\triangle}:\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^{\prime}\mid
uu^{\prime}\in(\Sigma\cup\overline{\Sigma})^{\triangle}:\Delta(u)>0\\}$ is a
VPL and thus conclude that for all $e\in O$, the set

$P(K_{e\uparrow})=\biggl{\\{}(k,l)\in\mathbb{N}\times\mathbb{N}\mathrel{\bigg{|}}\begin{aligned}
&\exists u\in\Sigma^{k},u^{\prime}\in\Sigma^{l},v\in\Sigma^{*}:\\\
&uv\in\Sigma^{\triangle},u^{\prime}v\in\Sigma^{\triangle},\Delta(u)>0,\psi(\operatorname{ext}_{u,v})=\psi(\operatorname{ext}_{u^{\prime},v})=e\end{aligned}\biggr{\\}}$

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^{\prime}$ be the alphabet that emerges from
$\Sigma\cup\overline{\Sigma}$ by additionally declaring $\\#$ as an internal
letter. We will construct an $\operatorname{Ext}$-algebra
$(R^{\prime},O^{\prime})$ and a morphism $(\varphi^{\prime},\psi^{\prime})$
from $(\Sigma^{\prime\triangle},\mathcal{O}(\Sigma^{\prime})^{\triangle})$ to
$(R^{\prime},O^{\prime})$ such that for some subset $F\subseteq R^{\prime}$ we
have $K_{e}=\varphi^{\prime-1}(F)$.

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

  * •

for all $r_{1},r_{2}\in R$,

$\displaystyle r_{1}\cdot r_{2}$ $\displaystyle=r_{1}r_{2}$
$\displaystyle\overline{r_{1}}\cdot r_{2}$ $\displaystyle=\bot$
$\displaystyle\overline{r_{1}}\cdot\overline{r_{2}}$
$\displaystyle=\overline{r_{2}r_{1}}$ $\displaystyle
r_{1}\cdot\overline{r_{2}}$ $\displaystyle=\bot\,\,\text{;}$

  * •

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

$\displaystyle r\cdot E$ $\displaystyle=\\{(\mathrm{left}_{r}\circ
e_{1},e_{2})\mid(e_{1},e_{2})\in E\\}$ $\displaystyle E\cdot r$
$\displaystyle=\bot$ $\displaystyle E\cdot\overline{r}$
$\displaystyle=\\{(e_{1},\mathrm{left}_{r}\circ e_{2})\mid(e_{1},e_{2})\in
E\\}$ $\displaystyle\overline{r}\cdot E$ $\displaystyle=\bot\,\,\text{;}$

  * •

for all $E_{1},E_{2}\in\mathfrak{P}(O^{2})\setminus\emptyset$, we have
$E_{1}\cdot E_{2}=\bot$;

  * •

$\bot$ acts as a zero, i.e. $\bot\cdot r^{\prime}=r^{\prime}\cdot\bot=\bot$
for all $r^{\prime}\in R^{\prime}$;

  * •

$1$ acts as an identity, i.e. $1\cdot r^{\prime}=r^{\prime}\cdot 1=r^{\prime}$
for all $r^{\prime}\in R^{\prime}$.

Associativity is immediate except for products of the form
$\overline{r_{1}}\cdot\overline{r_{2}}\cdot\overline{r_{3}}$, $r_{1}\cdot
E\cdot\overline{r_{2}}$, $r_{1}\cdot r_{2}\cdot E$ and
$E\cdot\overline{r_{1}}\cdot\overline{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

$(\overline{r_{1}}\cdot\overline{r_{2}})\cdot\overline{r_{3}}=\overline{r_{2}r_{1}}\cdot\overline{r_{3}}=\overline{r_{3}r_{2}r_{1}}=\overline{r_{1}}\cdot\overline{r_{3}r_{2}}=\overline{r_{1}}\cdot(\overline{r_{2}}\cdot\overline{r_{3}})\,\,\text{.}$

In the second case we have

$\displaystyle(r_{1}\cdot E)\cdot\overline{r_{2}}$
$\displaystyle=\\{(\mathrm{left}_{r_{1}}\circ e_{1},e_{2})\mid(e_{1},e_{2})\in
E\\}\cdot\overline{r_{2}}$ $\displaystyle=\\{(\mathrm{left}_{r_{1}}\circ
e_{1},\mathrm{left}_{r_{2}}\circ e_{2})\mid(e_{1},e_{2})\in E\\}$
$\displaystyle=r_{1}\cdot\\{(e_{1},\mathrm{left}_{r_{2}}\circ
e_{2})\mid(e_{1},e_{2})\in
E\\}=r_{1}\cdot(E\cdot\overline{r_{2}})\,\,\text{.}$

In the third case we have

$\displaystyle(r_{1}\cdot r_{2})\cdot E$
$\displaystyle=\\{(\mathrm{left}_{r_{1}r_{2}}\circ
e_{1},e_{2})\mid(e_{1},e_{2})\in E\\}$
$\displaystyle=\\{(\mathrm{left}_{r_{1}}\circ\mathrm{left}_{r_{2}}\circ
e_{1},e_{2})\mid(e_{1},e_{2})\in E\\}$
$\displaystyle=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)$

and in the fourth case we have

$\displaystyle E\cdot(\overline{r_{1}}\cdot\overline{r_{2}})$
$\displaystyle=\\{(e_{1},\mathrm{left}_{r_{2}r_{1}}\circ
e_{2})\mid(e_{1},e_{2})\in E\\}$
$\displaystyle=\\{(e_{1},\mathrm{left}_{r_{2}}\circ\mathrm{left}_{r_{1}}\circ
e_{2})\mid(e_{1},e_{2})\in E\\}$
$\displaystyle=\\{(e_{1},\mathrm{right}_{r_{1}}\circ
e_{2})\mid(e_{1},e_{2})\in
E\\}\cdot\overline{r_{2}}=(E\cdot\overline{r_{1}})\cdot\overline{r_{2}}\,\,\text{.}$

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

$\displaystyle\psi^{\prime}(\operatorname{ext}_{a,b})(x)$
$\displaystyle=\begin{cases}\psi(\operatorname{ext}_{a,b})(1_{R})&\text{if
$x=1$}\\\ \psi(\operatorname{ext}_{a,b})(x)&\text{if $x\in R$}\\\
\bot&\text{otherwise}\end{cases}$
$\displaystyle\psi^{\prime}(\operatorname{ext}_{\overline{b^{\prime}},\overline{a^{\prime}}})(x)$
$\displaystyle=\begin{cases}\overline{\psi(\operatorname{ext}_{a^{\prime},b^{\prime}})(1_{R})}&\text{if
$x=1$}\\\
\overline{\psi(\operatorname{ext}_{a^{\prime},b^{\prime}})(x^{\prime})}&\text{if
$x=\overline{x^{\prime}}$ for $x^{\prime}\in R$}\\\
\bot&\text{otherwise}\end{cases}$
$\displaystyle\psi^{\prime}(\operatorname{ext}_{a,\overline{a^{\prime}}})(x)$
$\displaystyle=\begin{cases}\bigcup_{\begin{subarray}{c}b\in\Sigma_{\text{ret}}\\\
z\in\Sigma^{\triangle}\\\ (e_{1},e_{2})\in
x\end{subarray}}\\{(\psi(\operatorname{ext}_{a,bz})\circ
e_{1},\psi(\operatorname{ext}_{a^{\prime},bz})\circ e_{2})\\}&\text{if
$x\in\mathfrak{P}(O^{2})\setminus\emptyset$}\\\
\bot&\text{otherwise}\end{cases}$
$\displaystyle\psi^{\prime}(\operatorname{ext}_{\overline{b^{\prime}},b})(x)$
$\displaystyle=\bot$

for all $x\in R^{\prime}$. Note that $(\varphi^{\prime},\psi^{\prime})$ is
computable because

$\displaystyle\\{(\psi(\operatorname{ext}_{\varepsilon,v}),\psi(\operatorname{ext}_{\varepsilon,v}))\mid
v\in\Sigma^{\triangle}\\}$
$\displaystyle=\\{(\mathrm{right}_{\varphi(v)},\mathrm{right}_{\varphi(v)})\mid
v\in\Sigma^{\triangle}\\}$
$\displaystyle=\\{(\mathrm{right}_{r},\mathrm{right}_{r})\mid r\in R\\}$

and

$\displaystyle\bigcup_{\begin{subarray}{c}b\in\Sigma_{\text{ret}}\\\
z\in\Sigma^{\triangle}\\\ (e_{1},e_{2})\in
x\end{subarray}}\\{(\psi(\operatorname{ext}_{a,bz})\circ
e_{1},\psi(\operatorname{ext}_{a^{\prime},bz})\circ e_{2})\\}$
$\displaystyle=$
$\displaystyle\bigcup_{\begin{subarray}{c}b\in\Sigma_{\text{ret}}\\\
z\in\Sigma^{\triangle}\\\ (e_{1},e_{2})\in
x\end{subarray}}\\{(\mathrm{right}_{\varphi(z)}\circ\psi(\operatorname{ext}_{a,b})\circ
e_{1},\mathrm{right}_{\varphi(z)}\circ\psi(\operatorname{ext}_{a^{\prime},b})\circ
e_{2})\\}$ $\displaystyle=$
$\displaystyle\bigcup_{\begin{subarray}{c}b\in\Sigma_{\text{ret}}\\\ r\in R\\\
(e_{1},e_{2})\in
x\end{subarray}}\\{(\mathrm{right}_{r}\circ\psi(\operatorname{ext}_{a,b})\circ
e_{1},\mathrm{right}_{r}\circ\psi(\operatorname{ext}_{a^{\prime},b})\circ
e_{2})\\}$

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

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

$\displaystyle\varphi^{\prime-1}(\\{E\in\mathfrak{P}(O^{2})\setminus\emptyset\mid(e,e)\in
E\\})$ $\displaystyle=$
$\displaystyle\\{u\\#\overline{u^{\prime}}\mid(u,u^{\prime})\in P,\exists
v\in\Sigma^{*}:uv\in\Sigma^{\triangle},u^{\prime}v\in\Sigma^{\triangle},\psi(\operatorname{ext}_{u,v})=\psi(\operatorname{ext}_{u^{\prime},v})=e\\}$
$\displaystyle=$ $\displaystyle\\{u\\#\overline{u^{\prime}}\mid
u,u^{\prime}\in\Sigma^{*},\exists
v\in\Sigma^{*}:uv\in\Sigma^{\triangle},u^{\prime}v\in\Sigma^{\triangle},\psi(\operatorname{ext}_{u,v})=\psi(\operatorname{ext}_{u^{\prime},v})=e\\}\,\,\text{.}$

For all $w\in\Sigma^{\prime\triangle}$ we have

$\varphi^{\prime}(w)=\begin{cases}1&\text{if $w=\varepsilon$}\\\
\varphi(w)&\text{if $w\in\Sigma^{\triangle}\setminus\\{\varepsilon\\}$}\\\
\overline{\varphi(w^{\prime})}&\text{if $w=\overline{w^{\prime}}$ for
$w^{\prime}\in\Sigma^{\triangle}\setminus\\{\varepsilon\\}$}\\\
\\{(\psi(\operatorname{ext}_{u,v}),\psi(\operatorname{ext}_{u^{\prime},v}))\mid
v\in\Sigma^{*},uv,u^{\prime}v\in\Sigma^{\triangle}\\}&\text{if
$w=u\\#\overline{u^{\prime}}$ for $(u,u^{\prime})\in P$}\\\
\bot&\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=\overline{c}\in\overline{\Sigma}_{\text{int}}$ follow immediately from the
definition of $\varphi^{\prime}$. In case $w=\\#=\varepsilon\\#\varepsilon$,
we have

$\varphi^{\prime}(w)=\\{(\psi(\operatorname{ext}_{\varepsilon,v}),\psi(\operatorname{ext}_{\varepsilon,v}))\mid
v\in\Sigma^{\triangle}\\}=\\{(\psi(\operatorname{ext}_{\varepsilon,v}),\psi(\operatorname{ext}_{\varepsilon,v}))\mid
v\in\Sigma^{*},\varepsilon v\in\Sigma^{\triangle}\\}$

as required.

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

$\displaystyle\varphi^{\prime}(w)$
$\displaystyle=\psi^{\prime}(\operatorname{ext}_{\alpha,\beta})(\varphi^{\prime}(w^{\prime}))$
$\displaystyle=\psi^{\prime}(\operatorname{ext}_{\alpha,\beta})(1)$
$\displaystyle=\begin{cases}\psi(\operatorname{ext}_{\alpha,\beta})(1_{R})=\varphi(w)&\text{if
$\alpha\in\Sigma_{\text{call}}$ and $\beta\in\Sigma_{\text{ret}}$}\\\
\overline{\psi(\operatorname{ext}_{a,b})(1_{R})}=\overline{\varphi(ab)}&\text{if
$\alpha=\overline{b}\in\overline{\Sigma}_{\text{call}}$ and
$\beta=\overline{a}\in\overline{\Sigma}_{\text{ret}}$}\\\
\bot&\text{otherwise}\end{cases}$

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

$\displaystyle\varphi^{\prime}(w)=\psi^{\prime}(\operatorname{ext}_{\alpha,\beta})(\varphi^{\prime}(w^{\prime}))$
$\displaystyle=\psi^{\prime}(\operatorname{ext}_{\alpha,\beta})(\varphi(w^{\prime}))$
$\displaystyle=\begin{cases}\psi(\operatorname{ext}_{\alpha,\beta})(\varphi(w^{\prime}))=\varphi(w)&\text{if
$\alpha\in\Sigma_{\text{call}}$ and $\beta\in\Sigma_{\text{ret}}$}\\\
\bot&\text{otherwise}\end{cases}$

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

$\displaystyle\varphi^{\prime}(w)$
$\displaystyle=\psi^{\prime}(\operatorname{ext}_{\alpha,\beta})(\varphi^{\prime}(w^{\prime}))$
$\displaystyle=\psi^{\prime}(\operatorname{ext}_{\alpha,\beta})(\overline{\varphi(w^{\prime\prime})})$
$\displaystyle=\begin{cases}\overline{\psi(\operatorname{ext}_{a,b})(\varphi(w^{\prime\prime}))}=\overline{\varphi(aw^{\prime\prime}b)}&\text{if
$\alpha=\overline{b}\in\overline{\Sigma}_{\text{call}}$ and
$\beta=\overline{a}\in\overline{\Sigma}_{\text{ret}}$}\\\
\bot&\text{otherwise}\end{cases}$

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

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

by induction hypothesis. Hence, we have

$\displaystyle\varphi^{\prime}(w)$
$\displaystyle=\psi^{\prime}(\operatorname{ext}_{\alpha,\beta})(\varphi^{\prime}(w^{\prime}))$
$\displaystyle=\psi^{\prime}(\operatorname{ext}_{\alpha,\beta})(\\{(\psi(\operatorname{ext}_{u,v^{\prime}}),\psi(\operatorname{ext}_{u^{\prime},v^{\prime}}))\mid
v^{\prime}\in\Sigma^{*},uv^{\prime},u^{\prime}v^{\prime}\in\Sigma^{\triangle}\\})$
$\displaystyle=\bigcup_{\begin{subarray}{c}b\in\Sigma_{\text{ret}}\\\
z\in\Sigma^{\triangle}\end{subarray}}\\{(\psi(\operatorname{ext}_{au,v^{\prime}bz}),\psi(\operatorname{ext}_{a^{\prime}u^{\prime},v^{\prime}bz}))\mid
v^{\prime}\in\Sigma^{*},uv^{\prime},u^{\prime}v^{\prime}\in\Sigma^{\triangle}\\}$
$\displaystyle=\\{(\psi(\operatorname{ext}_{au,v}),\psi(\operatorname{ext}_{a^{\prime}u^{\prime},v}))\mid
v\in\Sigma^{*},auv,a^{\prime}u^{\prime}v\in\Sigma^{\triangle}\\}$

if $\alpha=a\in\Sigma_{\text{call}}$ and
$\beta=\overline{a^{\prime}}\in\overline{\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^{\prime}(w)=\bot$ otherwise, as required.

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

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

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

$\varphi^{\prime}(x)=\begin{cases}\varphi(x)\in R&\text{if
$x\in\Sigma^{\triangle}\setminus\\{\varepsilon\\}$}\\\
\overline{\varphi(x^{\prime})}\in\overline{R}&\text{if
$x=\overline{x^{\prime}}$ for
$x^{\prime}\in\Sigma^{\triangle}\setminus\\{\varepsilon\\}$}\end{cases}$

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

$\displaystyle\varphi^{\prime}(w)$
$\displaystyle=\varphi^{\prime}(x)\cdot\varphi^{\prime}(y)$
$\displaystyle=\varphi(x)\cdot\\{(\psi(\operatorname{ext}_{u,v}),\psi(\operatorname{ext}_{u^{\prime},v}))\mid
v\in\Sigma^{*},uv,u^{\prime}v\in\Sigma^{\triangle}\\}$
$\displaystyle=\\{(\mathrm{left}_{\varphi(x)}\circ\psi(\operatorname{ext}_{u,v}),\psi(\operatorname{ext}_{u^{\prime},v}))\mid
v\in\Sigma^{*},uv,u^{\prime}v\in\Sigma^{\triangle}\\}$
$\displaystyle=\\{(\psi(\operatorname{ext}_{xu,v}),\psi(\operatorname{ext}_{u^{\prime},v}))\mid
v\in\Sigma^{*},xuv,u^{\prime}v\in\Sigma^{\triangle}\\}$

if $x\in\Sigma^{\triangle}\setminus\\{\varepsilon\\}$ and
$\varphi^{\prime}(w)=\overline{\varphi(x^{\prime})}\cdot\\{(\psi(\operatorname{ext}_{u,v}),\psi(\operatorname{ext}_{u^{\prime},v}))\mid
v\in\Sigma^{*},uv,u^{\prime}v\in\Sigma^{\triangle}\\}=\bot$ if
$x=\overline{x^{\prime}}$ for
$x^{\prime}\in\Sigma^{\triangle}\setminus\\{\varepsilon\\}$, as required.
Eventually, let us treat the case when $x=u\\#u^{\prime}$ with
$(u,u^{\prime})\in P$ and
$y\in(\Sigma^{\triangle}\cup\overline{\Sigma}^{\triangle})\setminus\\{\varepsilon\\}$,
hence $w=u\\#\overline{u^{\prime}}y$. The induction hypothesis yields
$\varphi^{\prime}(x)=\\{(\psi(\operatorname{ext}_{u,v}),\psi(\operatorname{ext}_{u^{\prime},v}))\mid
v\in\Sigma^{*},uv,u^{\prime}v\in\Sigma^{\triangle}\\}\in\mathfrak{P}(O^{2})\setminus\emptyset$
and $\varphi^{\prime}(y)=\begin{cases}\varphi(y)\in R&\text{if
$y\in\Sigma^{\triangle}\setminus\\{\varepsilon\\}$}\\\
\overline{\varphi(y^{\prime})}\in\overline{R}&\text{if
$y=\overline{y^{\prime}}$ for
$y^{\prime}\in\Sigma^{\triangle}\setminus\\{\varepsilon\\}$}\end{cases}$. We
obtain

$\displaystyle\varphi^{\prime}(w)$
$\displaystyle=\varphi^{\prime}(x)\cdot\varphi^{\prime}(y)$
$\displaystyle=\\{(\psi(\operatorname{ext}_{u,v}),\psi(\operatorname{ext}_{u^{\prime},v}))\mid
v\in\Sigma^{*},uv,u^{\prime}v\in\Sigma^{\triangle}\\}\cdot\overline{\varphi(y^{\prime})}$
$\displaystyle=\\{(\psi(\operatorname{ext}_{u,v}),\mathrm{left}_{\varphi(y^{\prime})}\circ\psi(\operatorname{ext}_{u^{\prime},v}))\mid
v\in\Sigma^{*},uv,u^{\prime}v\in\Sigma^{\triangle}\\}$
$\displaystyle=\\{(\psi(\operatorname{ext}_{u,v}),\psi(\operatorname{ext}_{y^{\prime}u^{\prime},v}))\mid
v\in\Sigma^{*},uv,y^{\prime}u^{\prime}v\in\Sigma^{\triangle}\\}$

if $y=\overline{y^{\prime}}$ for
$y^{\prime}\in\Sigma^{\triangle}\setminus\\{\varepsilon\\}$ and
$\varphi^{\prime}(w)=\\{(\psi(\operatorname{ext}_{u,v}),\psi(\operatorname{ext}_{u^{\prime},v}))\mid
v\in\Sigma^{*},uv,u^{\prime}v\in\Sigma^{\triangle}\\}\cdot\varphi(y)=\bot$ if
$x\in\Sigma^{\triangle}\setminus\\{\varepsilon\\}$, as required, because
$\overline{y^{\prime}u^{\prime}}=\overline{u^{\prime}}\,\overline{y^{\prime}}$
in the first case. ∎

##  7 Conclusion

In this paper we have studied the question which visibly pushdown languages
lie in the complexity class $\mathsf{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\rightarrow_{G}\varepsilon$ for the start
nonterminal $S$ and whose further productions are all of the form
$T\rightarrow_{G}uT^{\prime}v$, where $uv$ is well-matched,
$u\in(\Sigma_{\text{int}}^{*}\Sigma_{\text{call}}\Sigma_{\text{int}}^{*})^{+}$,
$v\in(\Sigma_{\text{int}}^{*}\Sigma_{\text{ret}}\Sigma_{\text{int}}^{*})^{+}$,
and the set of contexts $\\{(u,v)\in\mathsf{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 $\mathsf{AC}^{0}$
(even in $\mathsf{ACC}^{0}$) or provably not in $\mathsf{AC}^{0}$. We
conjecture that none of the intermediate VPLs are in $\mathsf{ACC}^{0}$ nor
$\mathsf{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 $\mathsf{AC}^{0}$, surely
does not lie in $\mathsf{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 equivalant 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\rightarrow\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 $\mathsf{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 $\mathsf{AC}^{0}$.

As main tools we carefully revisited $\operatorname{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 $\mathsf{ACC}^{0}$, provably not in $\mathsf{AC}^{0}$, or hard for
$\mathsf{TC}^{0}$? Another exciting question is whether one can effectively
compute those visibly pushdown languages that lie in the complexity class
$\mathsf{TC}^{0}$. Is there is a $\mathsf{TC}^{0}$/$\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 $\NC^{1}$-complete
visibly pushdown language whose syntactic $\operatorname{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. 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\rightarrow aSb\mid
a^{\prime}cSb^{\prime}\mid\varepsilon$, where $a,a^{\prime}$ are call letters,
$b,b^{\prime}$ are return letters and $c$ is an internal letter. This rest of
the section makes use of the above.

  2. 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. 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\not\in\\{0,1\\}$: in this case it is
not clear if $\alpha\phi(w)\beta\psi(w^{R})\gamma$ is in $L$ or not.

  4. 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. 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. 6.

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

  7. 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\rightarrow aSb\mid a_{1}cb_{1}\mid
a_{2}ccb_{2}$ is a counter-example.

  8. 8.

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

  9. 9.

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

  10. 10.

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

  11. 11.

The statement of Lemma 125 is wrong. Counter-example: $L=\\{a^{n}b^{n}\mid
n\geq 0\\}^{*}$. Clearly, $\text{cancel}^{|H_{L}|}(w)=\Sigma_{\text{int}}^{*}$
for all $w\in L$ but $L$ does not have the WSHB.

  12. 12.

The statement of Proposition 144 is wrong. Consider the language generated by
the grammar $S\rightarrow aSb\mid a_{1}cb_{1}\mid a_{2}ccb_{2}$ which is a
visibly counter language that does not have the SHB property. However, it is
in $\mathsf{AC}^{0}$.

  13. 13.

Corollary 145 is wrong due to the previous point.

  14. 14.

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

  15. 15.

Statement of Lemma 146 is unclear since $\rightsquigarrow_{L}$ is not clearly
defined.

  16. 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 NC1.  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 nc1.  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 Eigth 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.