# The AC⁰-Complexity Of Visibly Pushdown Languages

Stefan Göller, Nathan Grosshans

► To cite this version:

Stefan Göller, Nathan Grosshans. The AC⁰-Complexity Of Visibly Pushdown Languages. 2023. hal-04005294v2

HAL Id: hal-04005294

https://hal.science/hal-04005294v2

Preprint submitted on 17 Oct 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

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

Distributed under a Creative Commons Attribution 4.0 International License
# The $AC^0$-Complexity Of Visibly Pushdown Languages

Stefan Göller*

stefan.goeller@uni-kassel.de

School of Electrical Engineering and Computer Science, Universität Kassel, Germany

Nathan Grosshans

nathan.grosshans@polytechnique.edu

Independent Scholar, France

## Abstract

We study the question of which visibly pushdown languages (VPLs) are in the complexity class $AC^0$ and how to effectively decide this question. Our contribution is to introduce a particular subclass of one-turn VPLs, called intermediate VPLs, for which the raised question is entirely unclear: to the best of our knowledge our research community is unaware of containment or non-containment in $AC^0$ for any intermediate VPL. Our main result states that there is an algorithm that, given a visibly pushdown automaton, correctly outputs either that its language is in $AC^0$, outputs some $m \ge 2$ such that $\text{MOD}_m$ is constant-depth reducible to $L$ (implying that $L$ is not in $AC^0$), or outputs a finite disjoint union of intermediate VPLs that $L$ is constant-depth equivalent to. In the latter case one can moreover effectively compute $k, l \in \mathbb{N}_{>0}$ with $k \ne l$ such that the concrete intermediate VPL $L(S \to \varepsilon | ac^{k-1}Sb_1 | ac^{l-1}Sb_2)$ is constant-depth reducible to the language $L$. Due to their particular nature we conjecture that either all intermediate VPLs are in $AC^0$ or all are not. As a corollary of our main result we obtain that in case the input language is a visibly counter language our algorithm can effectively determine if it is in $AC^0$ — hence our main result generalizes a result by Krebs et al. stating that it is decidable if a given visibly counter language is in $AC^0$ (when restricted to well-matched words).

For our proofs we revisit so-called Ext-algebras (introduced by Czarnetzki et al.), which are closely related to forest algebras (introduced by Bojańczyk and Walukiewicz), and use Green's relations.

## Contents

<table><tr><td>1</td><td>Introduction</td><td>2</td></tr><tr><td>2</td><td>Preliminaries</td><td>4</td></tr><tr><td>2.1</td><td>Complexity and logic</td><td>6</td></tr><tr><td>2.2</td><td>Main result</td><td>7</td></tr><tr><td>2.3</td><td>Corollary for visibly counter languages</td><td>8</td></tr></table>

<footnote>*The first author was supported by the Agence Nationale de la Recherche grant no. ANR-17-CE40-0010.</footnote>
<table>
  <tbody>
    <tr>
      <td>3</td>
      <td>Language-theoretic and algebraic foundations and Ext-Algebras</td>
      <td>8</td>
    </tr>
    <tr>
      <td>3.1</td>
      <td>Basic algebraic automata theory</td>
      <td>8</td>
    </tr>
    <tr>
      <td>3.2</td>
      <td>Ext-algebras</td>
      <td>9</td>
    </tr>
    <tr>
      <td>4</td>
      <td>(Weak) length-synchronicity, nesting depth, and quasi-aperiodicity</td>
      <td>21</td>
    </tr>
    <tr>
      <td>4.1</td>
      <td>A pumping lemma for Ext-algebra morphisms</td>
      <td>21</td>
    </tr>
    <tr>
      <td>4.2</td>
      <td>Weak length-synchronicity and length-synchronicity</td>
      <td>22</td>
    </tr>
    <tr>
      <td>4.3</td>
      <td>The nesting depth of visibly pushdown languages</td>
      <td>28</td>
    </tr>
    <tr>
      <td>4.4</td>
      <td>Quasi-aperiodicity and its correspondence with quasi-counterfreeness</td>
      <td>30</td>
    </tr>
    <tr>
      <td>5</td>
      <td>Proof of the main theorem</td>
      <td>31</td>
    </tr>
    <tr>
      <td>5.1</td>
      <td>Proof outline for Theorem 2.9</td>
      <td>31</td>
    </tr>
    <tr>
      <td>5.2</td>
      <td>Lower bounds</td>
      <td>32</td>
    </tr>
    <tr>
      <td>5.2.1</td>
      <td>The non-solvable case</td>
      <td>34</td>
    </tr>
    <tr>
      <td>5.3</td>
      <td>In AC<sup>0</sup>: Length-synchronous and quasi-aperiodic</td>
      <td>35</td>
    </tr>
    <tr>
      <td></td>
      <td>Approximate matchings.</td>
      <td>35</td>
    </tr>
    <tr>
      <td></td>
      <td>Horizontal and vertical evaluation languages.</td>
      <td>36</td>
    </tr>
    <tr>
      <td>5.3.1</td>
      <td>Strategy for the proof of Theorem 5.7</td>
      <td>36</td>
    </tr>
    <tr>
      <td>5.3.2</td>
      <td>V<sub>φ<sub>L</sub></sub> and V<sub>ψ<sub>L</sub></sub> are quasi-aperiodic (Proof of Point 1)</td>
      <td>37</td>
    </tr>
    <tr>
      <td>5.3.3</td>
      <td>Quasi-aperiodicity of evaluation languages E<sub>φ<sub>L,r</sub></sub> and E<sub>ψ<sub>L,e</sub></sub> (Proof of Point 2)</td>
      <td>39</td>
    </tr>
    <tr>
      <td>5.3.4</td>
      <td>Approximate matching relation in FO[+] (Proof of Point 3)</td>
      <td>41</td>
    </tr>
    <tr>
      <td></td>
      <td>Building an approximate matching assuming predicates π<sub>e</sub>.</td>
      <td>42</td>
    </tr>
    <tr>
      <td>5.3.5</td>
      <td>Evaluation in FO[+] (Proof of Point 4)</td>
      <td>47</td>
    </tr>
    <tr>
      <td>5.4</td>
      <td>The intermediate case</td>
      <td>51</td>
    </tr>
    <tr>
      <td>5.4.1</td>
      <td>Proof strategy.</td>
      <td>53</td>
    </tr>
    <tr>
      <td>5.4.2</td>
      <td>Computation of k, l.</td>
      <td>61</td>
    </tr>
    <tr>
      <td>5.5</td>
      <td>Proof of Corollary 2.11</td>
      <td>64</td>
    </tr>
    <tr>
      <td>6</td>
      <td>Proof of Proposition 5.1</td>
      <td>66</td>
    </tr>
    <tr>
      <td>7</td>
      <td>Conclusion</td>
      <td>77</td>
    </tr>
    <tr>
      <td>8</td>
      <td>Some errata in previous work</td>
      <td>78</td>
    </tr>
  </tbody>
</table>

# 1 Introduction

This paper studies the circuit complexity of formal word languages. It is well-known that the regular word languages are characterized as the languages recognizable by finite monoids. When restricting the finite monoids to be aperiodic Schützenberger proved that one obtains precisely the star-free regular languages [28]. In terms of logic, these correspond to the languages definable in first-order logic FO[<] by a result of McNaughton and Papert [29]. The more general class of regular languages expressible in FO[arb], i.e. first-order logic with arbitrary numerical predicates, coincides with the regular languages in AC⁰ [16, 19]. These can be characterized algebraically as the regular languages whose syntactic morphism is quasi-aperiodic [5]. The latter algebraic characterization also shows that it is decidable if a regular language is in AC⁰.

Generalizing regular languages, input-driven languages were introduced by Mehlhorn [25]. They are described by pushdown automata whose input alphabet is partitioned into letters that are either of type call, internal, or return. Rediscovered by Alur and Madhusudan in 2004 [2] under the name
of visibly pushdown languages (VPLs), it was shown that they enjoy many of the desirable effective closure properties of the regular languages. For instance, the visibly pushdown languages form an effective Boolean algebra. Algebraically, VPLs were characterized by Alur et al. [1] by congruences on well-matched words of finite index. Extending upon these, Czarnetzki et al. introduced so-called Ext-algebras [10]; these involve pairs of monoids $(R, O)$ where $O$ is a submonoid of $R^R$. Being tailored towards recognizing word languages, Ext-algebras are closely connected to forest algebras, introduced by Bojańczyk and Walukiewicz [7]: in [10] it is shown that a language of well-matched words is visibly pushdown if, and only if, its syntactic Ext-algebra is finite. While context-free languages are generally in $LOGCFL = SAC^1$, the visibly pushdown languages, as the regular languages, are known to be in $NC^1$ [11]. By a famous result of Barrington [4], there already exist regular languages that are $NC^1$-hard. In this paper we study the question of which visibly pushdown languages are in $AC^0$ and how one can effectively decide this question.

**Related work.** Visibly pushdown languages (VPLs) were introduced [2] via deterministic visibly pushdown automata (DVPA for short). Inspired by forest algebras [7] the paper [10] introduces Ext-algebras. Unfortunately, the definition of Ext-algebra morphisms in [10] is incorrect in that it provably does not lead to freeness.

The regular languages that are in $AC^0$ were effectively characterized by Barrington et al. [5]: a regular language is in $AC^0$ if, and only if, its syntactic morphism is quasi-aperiodic. By an automata-theoretic approach, Krebs et al. [22] effectively characterized the visibly counter languages that are in $AC^0$. These are particular VPLs that are essentially accepted by visibly pushdown automata that use only one stack symbol. In his PhD thesis [24] Ludwig already considers the question of which VPLs are in $AC^0$. Yet, his conjectural characterization contains several serious flaws — a detailed discussion of these shortcomings can be found in Section 8.

**Our contribution.** We reintroduce Ext-algebras, fix the notion of Ext-algebra morphisms and define the languages they recognize. We also reintroduce the syntactic Ext-algebra of languages of well-matched words. We rigorously prove classical results like freeness and minimality of syntactic Ext-algebras with respect to recognition. We prove that a language of well-matched words is a VPL if, and only if, it is recognizable by a finite Ext-algebra. While these results essentially revisit the constructions of [10], we use Ext-algebras as a technical tool for studying the complexity of visibly pushdown languages.

Fix a visibly pushdown alphabet $\Sigma$, i.e. $\Sigma$ is partitioned into $\Sigma_{\text{call}}$ (call letters), $\Sigma_{\text{int}}$ (internal letters), and $\Sigma_{\text{ret}}$ (return letters). Denoting $\Delta(u)$ as the difference between the number of occurrences of call and return letters in $u \in \Sigma^*$ a word $w \in \Sigma^*$ is *well-matched* if $\Delta(w) = 0$ and $\Delta(u) \ge 0$ for all prefixes $u$ of $w$. A context is a pair $(u, v)$ such that $uv$ is well-matched — contexts have a natural composition operation: $(u, v) \circ (u', v') = (uu', v'v)$.

We introduce the following notions: a set of contexts $\mathcal{R}$ is *length-synchronous* if $|u|/|v| = |u'|/|v'|$ for all $(u, v), (u', v') \in \mathcal{R}$ with $\Delta(u), \Delta(u') > 0$ and *weakly length-synchronous* if $u = u'$ implies $|v| = |v'|$ and $v = v'$ implies $|u| = |u'|$ for all $(u, v), (u', v') \in \mathcal{R}$ with $\Delta(u), \Delta(u') > 0$. Any language $L$ of well-matched words induces a congruence $\equiv_L$ on contexts: $(u, v) \equiv_L (u', v')$ if $xuwvy \in L \Leftrightarrow xu'wv'y \in L$ for all contexts $(x, y)$ and all well-matched words $w$. We introduce the notion of quasi-counterfreeness: a VPL is *quasi-counterfree* if for all contexts $\sigma \in \Sigma^k \times \Sigma^l$ we have $\sigma^n \equiv_L \sigma^{n+1}$ for some $n \in \mathbb{N}$ or all contexts in $\Sigma^k \times \Sigma^l$ are not $\equiv_L$-equivalent to $\sigma \circ \sigma$. Finally, we introduce our central class of *intermediate VPLs*: a VPL is *intermediate* if it is quasi-counterfree and generated by a context-free grammar containing the production $S \to_G \varepsilon$, where $S$ is the start nonterminal and whose other productions are of the form $T \to_G uT'v$ such that $uv$ is well-matched, $u \in (\Sigma_{\text{int}}^* \Sigma_{\text{call}} \Sigma_{\text{int}}^*)^+$ and $v \in (\Sigma_{\text{int}}^* \Sigma_{\text{ret}} \Sigma_{\text{int}}^*)^+$ such that the set of contexts $\{(u, v) \mid S \Rightarrow_G^* uSv\}$ is weakly length-synchronous but not length-synchronous. Note that intermediate VPLs are particular one-turn visibly pushdown
languages, that is, visibly pushdown languages that are subsets of $(\Sigma \setminus \Sigma_{\text{ret}})^*(\Sigma \setminus \Sigma_{\text{call}})^*$. As an example, for all $k, l \ge 1$ with $k \ne l$ a concrete intermediate VPL, denoted by $\mathcal{L}_{k,l}$ is the one that is generated by the context-free grammar $S \to \varepsilon \mid ac^{k-1}Sb_1 \mid ac^{l-1}Sb_2$: here $a$ is a call letter, $c$ is an internal letter and $b_1$ and $b_2$ are return letters.

As far as we know our community is unaware of whether *at all* there is some intermediate VPL that is *provably in AC<sup>0</sup>* or *provably not in AC<sup>0</sup>* — analogous remarks apply to *ACC<sup>0</sup>*.

Our main result states that there is an algorithm that, given a DVPA $A$ correctly outputs either $L(A) \in AC^0$, outputs some $m \ge 2$ such that $\text{MOD}_m$ is constant-depth reducible to $L$ (thus witnessing that $L(A) \notin AC^0$), or outputs a non-empty disjoint finite union of intermediate VPLs that $L(A)$ is constant-depth equivalent to. In the latter case one can moreover effectively compute $k, l \in \mathbb{N}_{>0}$ with $k \ne l$ such that the above-mentioned $\mathcal{L}_{k,l}$ is constant-depth reducible to $L(A)$. We conjecture that either all intermediate VPLs are in $AC^0$ or all are not: note that together with our main result this conjecture implies the existence of an algorithm that can determine if a given visibly pushdown language is in $AC^0$. As a corollary of our main result we obtain that in case the input language is a visibly counter language our algorithm can determine if it is in $AC^0$, hence our main result generalizes a result by Krebs et al. stating that it is decidable if a given visibly counter lanugage is in $AC^0$ (when restricted to well-matched words).

For our main result we extensively study Ext-algebras, the syntactic morphisms of VPLs, and make use of Green's relations.

**Organization.** Our paper is organized as follows. We introduce notation and give an overview of our main result in Section 2. In Section 3 we first recall general algebraic concepts and then revisit Ext-algebras and their correspondence to visibly pushdown languages. Section 4 introduces central notions like length-synchronicity and weak length-synchronicity for Ext-algebra morphisms and visibly pushdown languages. The proof of our main result is content of Section 5. In Section 6 we concern ourselves with the computability of the syntactic Ext-algebra as well as decidability of quasi-aperiodicity and (weak) length-synchronicity. We conclude in Section 7.

## 2 Preliminaries

By $\mathbb{N}$ we denote the non-negative integers and by $\mathbb{N}_{>0}$ the positive integers. For integers $i, j \in \mathbb{Z}$ we denote by $[i, j]$ the set $\{i, \dots, j\}$. For any function $f : X \to Y$ and any subset $Z \subseteq X$ we denote by $f|_Z : Z \to Y$ the restriction of $f$ to domain $Z$, i.e. $f|_Z(z) = f(z)$ for all $z \in Z$.

For all words $w = w_1 \cdots w_n$, where $w_i \in \Sigma$ for all $i \in [1, n]$, and for subsets $\Gamma \subseteq \Sigma$, let $|w|_\Gamma = |\{i \in [1, |w|] \mid w_i \in \Gamma\}|$ denote the number of occurrences of letters in $\Gamma$. For all $a \in \Gamma$ we write $|w|_a$ to denote $|w|_{\{a\}}$.

We define the languages

$$ \text{EQUALITY} = \{w \in \{0,1\}^* : |w|_0 = |w|_1\} \quad \text{and} \quad \text{MOD}_m = \{w \in \{0,1\}^* : m \text{ divides } |w|_1\} $$

for each $m \ge 2$.

A *visibly pushdown alphabet* is a finite alphabet $\Sigma = \Sigma_{\text{call}} \cup \Sigma_{\text{int}} \cup \Sigma_{\text{ret}}$, where the alphabets $\Sigma_{\text{call}}$, $\Sigma_{\text{int}}$, and $\Sigma_{\text{ret}}$ are pairwise disjoint.

**Definition 2.1.** The set of well-matched words over a visibly pushdown alphabet $\Sigma$, denoted by $\Sigma^\Delta$, is the smallest set satisfying the following:

* $\varepsilon \in \Sigma^\Delta$ and $c \in \Sigma^\Delta$ for all $c \in \Sigma_{\text{int}}$,

* $awb \in \Sigma^\Delta$ for all $w \in \Sigma^\Delta$, $a \in \Sigma_{\text{call}}$ and $b \in \Sigma_{\text{ret}}$, and
• $uv \in \Sigma^\Delta$ for all $u, v \in \Sigma^\Delta \setminus \{\varepsilon\}$.

A well-matched word $w \in \Sigma^\Delta$ is one-turn if $w \in (\Sigma \setminus \Sigma_{\text{ret}})^* (\Sigma \setminus \Sigma_{\text{call}})^*$. A language $L \subseteq \Sigma^\Delta$ is one-turn if it contains only one-turn words. Let $\Sigma$ be a visibly pushdown alphabet. We define $\Delta: \Sigma^* \to \mathbb{Z}$ to be the height monoid morphism such that $\Delta(w) = |w|_{\Sigma_{\text{call}}} - |w|_{\Sigma_{\text{ret}}}$ for all $w \in \Sigma^*$. A context is a pair $(u, v) \in \Sigma^* \times \Sigma^*$ such that $uv \in \Sigma^\Delta$. The composition of two contexts $(u, v), (x, y) \in \text{Con}(\Sigma)$ is defined as $(u, v) \circ (x, y) = (ux, yv)$. For $\sigma \in \text{Con}(\Sigma)$ by $\sigma^k$ we denote the $k$-fold composition $\sigma \circ \dots \circ \sigma$. For any context $(u, v) \in \text{Con}(\Sigma)$ and well-matched word $w \in \Sigma^\Delta$ we define $(u, v)w = uwv$. An equivalence relation $\equiv$ on $\text{Con}(\Sigma)$ is a congruence if for all $\chi, \chi', \sigma, \tau \in \text{Con}(\Sigma)$ we have that $\sigma \equiv \tau$ implies $\chi \circ \sigma \circ \chi' \equiv \chi \circ \tau \circ \chi'$. Given a congruence $\equiv$ over $\text{Con}(\Sigma)$ we denote by $[\sigma]_{\equiv}$ the equivalence class of $\sigma$. Given a language of well-matched words $L \subseteq \Sigma^\Delta$ we write $\sigma \equiv_L \tau$ if for all $\chi \in \text{Con}(\Sigma)$ and all $w \in \Sigma^\Delta$ we have $(\chi \circ \sigma)w \in L$ if, and only if, $(\chi \circ \tau)w \in L$. Clearly, $\equiv_L$ is a congruence.

Let us briefly introduce context-free grammars. A context-free grammar is a tuple $G = (V, \Sigma, P, S)$, where $V$ is a finite set of nonterminals, $\Sigma$ is a non-empty finite alphabet, $P \subseteq V \times (V \cup \Sigma)^*$ is a finite set of productions, and $S \in V$ is the start nonterminal. We write $T \to_G y$ whenever $(T, y) \in P$. The binary relation $\Rightarrow_G$ over $(V \cup \Sigma)^*$ is defined as $u \Rightarrow_G v$ if there exists a production $T \to_G y$ and $x, z \in (V \cup \Sigma)^*$ such that $u = xTz$ and $v = xyz$. By $L(G) = \{w \in \Sigma^* | S \Rightarrow_G^* w\}$ we denote the language of $G$ where $\Rightarrow_G^*$ is the reflexive transitive closure of $\Rightarrow_G$.

In the following we introduce deterministic visibly pushdown automata, remarking that noneterministic visibly pushdown automata are determinizable [2].

**Definition 2.2.** A deterministic visibly pushdown automaton (DVPA) is a tuple $A = (Q, \Sigma, \Gamma, \delta, q_0, F, \perp)$, where

• $Q$ is a finite set of states,

• $\Sigma$ is a visibly pushdown alphabet, the input alphabet,

• $\Gamma$ is a finite alphabet, the stack alphabet,

• $q_0 \in Q$ is the initial state,

• $F \subseteq Q$ is the set of final states,

• $\perp \in \Gamma$ is the bottom-of-stack symbol, and

• $\delta: Q \times \Sigma \times \Gamma \to Q \times (\{\varepsilon\} \cup \Gamma \cup (\Gamma \setminus \{\perp\})\Gamma)$ is the transition function such that for all $q \in Q, a \in \Sigma, \alpha \in \Gamma$:

- if $a \in \Sigma_{\text{call}}$, then $\delta(q, a, \alpha) \in Q \times (\Gamma \setminus \{\perp\})\alpha$,

- if $a \in \Sigma_{\text{ret}}$, then $\delta(q, a, \alpha) \in Q \times \{\varepsilon\}$, and

- if $a \in \Sigma_{\text{int}}$, then $\delta(q, a, \alpha) \in Q \times \{\alpha\}$.

We define the extended transition function $\hat{\delta}: Q \times \Sigma^* \times \Gamma^* \to Q \times \Gamma^*$ inductively as

• $\hat{\delta}(q, \varepsilon, \beta) = (q, \beta)$ for all $q \in Q$ and $\beta \in \Gamma^*$,

• $\hat{\delta}(q, w, \varepsilon) = (q, \varepsilon)$ for all $q \in Q$ and $w \in \Sigma^+$, and

• $\hat{\delta}(q, aw, \alpha\beta) = \hat{\delta}(p, w, \gamma\beta)$, where $\delta(q, a, \alpha) = (p, \gamma)$ for all $q \in Q, a \in \Sigma, w \in \Sigma^*, \alpha \in \Gamma$ and $\beta \in \Gamma^*$.

The language accepted by $A$ is the language $L(A) = \{w \in \Sigma^* | \hat{\delta}(q_0, w, \perp) \in F \times \{\perp\}\}$. We call
such a language a *visibly pushdown language* (VPL). We remark that visibly pushdown languages
are always subsets of $\Sigma^\Delta$.

We refer to [17] for further details on formal language theory.

**Semi-linear sets.** Given $d \in \mathbb{N}_{>0}$, for $\vec{x} = (x_1, \dots, x_d), \vec{y} = (y_1, \dots, y_d) \in \mathbb{N}^d$ we define $\vec{x} + \vec{y} = (x_1 + y_1, \dots, x_d + y_d)$. We define the *norm* of a vector $\vec{x} \in \mathbb{N}^d$ as $\|\vec{x}\| = \max\{x_i \mid i \in [1, d]\}$. For $X, Y \subseteq \mathbb{N}^d$ define $X + Y = \{\vec{x} + \vec{y} \mid \vec{x} \in X, \vec{y} \in Y\}$. For $\vec{x} = (x_1, \dots, x_d) \in \mathbb{N}^d$ and $n \in \mathbb{N}$ we define $n\vec{x} = (nx_1, \dots, nx_d)$ and $\mathbb{N}\vec{x} = \{n\vec{x} \mid n \in \mathbb{N}\}$. A set $X \subseteq \mathbb{N}^d$ is *linear* if $X = \vec{y} + \sum_{i=1}^k \mathbb{N}\vec{x}_i$ for $k \in \mathbb{N}$ and $y, x_1, \dots, x_k \in \mathbb{N}^d$ and it is *semilinear* if $X$ is a finite union of linear sets.

**2.1 Complexity and logic**

We assume familiarity with standard circuit complexity, we refer to [31, 21] for an introduction to
the topic. Recall the following Boolean functions: the AND-function, the OR-function, the majority
function (that outputs 1 if the majority of its inputs are 1s), and the mod<sub>m</sub> function (that outputs
1 if the number of its inputs that are 1s is divisible by m) for all m ≥ 2.

A circuit family $(C_n)_{n \in \mathbb{N}}$ decides a binary language $L \subseteq \{0,1\}^*$ if $C_n$ is a circuit with $n$ inputs such that $L \cap \{0,1\}^n = \{x_1 \dots x_n \in \{0,1\}^n \mid C_n(x_1, \dots, x_n) = 1\}$ for all $n \in \mathbb{N}$. In this paper, we will consider circuits deciding languages over arbitrary finite alphabets: to do this, we just consider implicitly that any language over an arbitrary finite alphabet comes with a fixed binary encoding that encodes each letter as a block of bits of fixed size. By $\leq_{cd}$ we mean constant-depth truth table reducibility (or just constant-depth reducibility) as introduced in [8]. Formally for two languages $K \subseteq \Gamma^*$ and $L \subseteq \Sigma^*$ for finite alphabets $\Sigma, \Gamma$, we write $K \leq_{cd} L$ in case there is a polynomial $p$, a constant $d \in \mathbb{N}$, and circuit family $(C_n)_{n \in \mathbb{N}}$ deciding $L$ such that each circuit $C_n$ satisfies the following: it is of depth at most $d$ and size at most $p(n)$ and its non-input gates are either AND-labeled, OR-labeled, or so-called oracle gates, labeled by $L$, that are gates deciding $L \cap \Sigma^m$, where $m \leq p(n)$, such that there is no path from the output of an oracle gate to an input of another oracle gate. We write $K =_{cd} L$ if $K \leq_{cd} L$ and $L \leq_{cd} K$; we also say that $K$ and $L$ are constant-depth equivalent. We say a language $L$ is hard for a complexity class $C$ (or just C-hard) if $L' \leq_{cd} L$ for all $L' \in C$. We say $L$ is C-complete if $L$ is C-hard and $L \in C$. The following complexity classes are relevant in this paper:

• $AC^0$ is the class of all languages decided by circuit families with NOT gates, AND, OR gates of unbounded fan-in, constant depth and polynomial size;

• ACC$^0$ is the class of all languages decided by circuit families with NOT gates, AND, OR and modular gates (for some fixed $m$) of unbounded fan-in, constant depth and polynomial size;

- TC⁰ is the class of all languages decided by circuit families with NOT gates, AND, OR and majority gates of unbounded fan-in, constant depth and polynomial size;

- $NC^1$ is the class of all languages decided by circuit families with NOT gates, AND, OR gates of bounded fan-in, logarithmic depth and polynomial size.

We also consider the framework of first order logic over finite words. (See [20, 29] for a proper
introduction to the topic.) A *numerical predicate of arity* *r* ∈ N>₀ is a symbol of arity *r* associated
to a subset of N>₀<sup>*r*</sup>. Given a class *C* of numerical predicates and a finite alphabet Σ, we call FO<sub>Σ</sub>[*C*]-
formula a first order formula over finite words using the alphabet Σ and numerical predicates from
the class *C*. On occasions, we might also consider FO<sub>Σ, ...</sub>[*C*]-formulas that in comparison to the
previous ones can use an additional binary predicate ↔ and are interpreted on structures (*w*, *M*)
with $w \in \Sigma^*$ and $M \subseteq [1, |w|]^2$, where everything is interpreted as for FO$_\Sigma[C]$-formulas on $w$ excepted for $\leftrightarrow$ that is interpreted by $M$. Given a class $\mathcal{C}$ of numerical predicates, by FO[$\mathcal{C}$] we denote the class of all languages over any finite alphabet $\Sigma$ defined by a FO$_\Sigma[C]$-sentence. A classical result at the interplay of circuit complexity and logic is that $\mathrm{AC}^0 = \mathrm{FO[arb]}$, where arb denotes the class of all numerical predicates (see [29, Theorem IX.2.1] or [20, Corollary 5.32]). The other numerical predicates that we will encounter in this paper are $<$, $+$ and $\mathrm{MOD}_m$ for all $m \in \mathbb{N}_{>0}$ (gathered together in the set $\mathrm{MOD} = \{\mathrm{MOD}_m \mid m > 0\}$).

## 2.2 Main result

The notion of length-synchronicity and weak length-synchronicity will be a central notion in our main result. In the following $\Sigma$ always denotes a visibly pushdown alphabet.

**Definition 2.3** ((Weak) Length-Synchronicity). Let $\mathcal{R} \subseteq \mathrm{Con}(\Sigma)$ be a set of contexts.

* $\mathcal{R}$ is length-synchronous if $|u|/|v| = |u'|/|v'|$ for all $(u, v)$, $(u', v') \in \mathcal{R}$ with $\Delta(u), \Delta(u') > 0$.

* $\mathcal{R}$ is weakly length-synchronous if $u = u'$ implies $|v| = |v'|$ and $v = v'$ implies $|u| = |u'|$ for all $(u, v)$, $(u', v') \in \mathcal{R}$ with $\Delta(u), \Delta(u') > 0$.

Note that a set of contexts $\mathcal{R}$ is weakly length-synchronous if $\mathcal{R}$ is length-synchronous. Indeed, if, say $(u, v)$, $(u, v') \in \mathcal{R}$, where $|v| \neq |v'|$ and $\Delta(u) > 0$, then $|u|, |v|, |v'| > 0$ and so the quotients $|u|/|v|$ and $|u|/|v|$ are distinct, thus violating length-synchronicity of $\mathcal{R}$.

**Definition 2.4** (Quasi-Counterfree). A VPL $L \subseteq \Sigma^\Delta$ is quasi-counterfree if for all $\sigma = (u, v) \in \mathrm{Con}(\Sigma)$ we have $\sigma^n \equiv_L \sigma^{n+1}$ for some $n \in \mathbb{N}$ or for all $\tau \in \Sigma^{|u|} \times \Sigma^{|v|} \cap \mathrm{Con}(\Sigma)$ we have $\tau \not\equiv_L \sigma \circ \sigma$.

We will later show that quasi-counterfreeness of a VPL $L \subseteq \Sigma^\Delta$ is equivalent to the condition that there is no $k, l \in \mathbb{N}$ such that there is a subset of $\mathrm{Con}(\Sigma) \cap \Sigma^k \times \Sigma^l$ that forms a non-trivial group when considering the associated equivalence classes with respect to $\equiv_L$ (Proposition 4.18).

**Example 2.5.** Consider the visibly pushdown alphabet $\Sigma$, where $\Sigma_{\mathrm{call}} = \{a\}$, $\Sigma_{\mathrm{int}} = \{c\}$ and $\Sigma_{\mathrm{ret}} = \{b_1, b_2\}$. For all $k, l \in \mathbb{N}_{>0}$ satisfying $k \neq l$, consider the language $\mathcal{L}_{k,l}$ generated by the context-free grammar $S \to ac^{k-1}Sb_1 \mid ac^{l-1}Sb_2 \mid \varepsilon$. We have that the set of contexts $\{(u, v) \in \mathrm{Con}(\Sigma) \mid S \Rightarrow_G^* uSv\}$ is weakly length-synchronous since both the relation and its reverse is a partial function — however, it is not length-synchronous. It is also not hard to see that $\mathcal{L}_{k,l}$ is quasi-counterfree.

We say a context-free grammar $G = (V, \Sigma, P, S)$ is vertically visibly pushdown if the underlying alphabet $\Sigma$ is a visibly pushdown alphabet, $S \to_G \varepsilon$, and all other productions of $G$ are of the form $T \to_G uT'v$, where $uv \in \Sigma^\Delta$ is one-turn such that $u \in (\Sigma_{\mathrm{int}}^* \Sigma_{\mathrm{call}} \Sigma_{\mathrm{int}}^*)^+$ and $v \in (\Sigma_{\mathrm{int}}^* \Sigma_{\mathrm{ret}} \Sigma_{\mathrm{int}}^*)^+$. Note that each grammar generating $\mathcal{L}_{k,l}$ in Example 2.5 is vertically visibly pushdown. The following remark is obvious.

**Remark 2.6.** The languages generated by vertically visibly pushdown grammars are one-turn VPLs.

**Definition 2.7** (Intermediate VPL). A VPL $L$ is intermediate if it is quasi-counterfree and $L = L(G)$ for some vertically visibly pushdown grammar $G$ for which $\mathcal{R}(G) = \{(u, v) \in \mathrm{Con}(\Sigma) \mid S \Rightarrow_G^* uSv\}$ is weakly-length synchronous but not length synchronous.

Thus the languages $\mathcal{L}_{k,l}$ from Example 2.5 are all intermediate VPLs. Loosely speaking, they are the simplest intermediate VPLs. We have the following conjecture.
**Conjecture 2.8.** There is no intermediate VPL that is in $\mathbf{ACC}^0$ or $\mathbf{TC}^0$-hard under constant-depth reductions.

In fact, the authors are not even aware of any intermediate VPL that is provably not in $\mathbf{AC}^0$. An indication for the inadequacies of known techniques to prove it is that the *robustness* [21] of intermediate VPLs can be proven to be constant. Further techniques, based for instance on the *switching lemma* [18] or on the *polynomial method* [6] also do not seem to be applicable.

Our main result is the following theorem.

**Theorem 2.9.** There is an algorithm that, given a DVPA A, correctly outputs either

* $L(A) \in \mathbf{AC}^0$,

* $m \ge 2$ such that $\mathrm{MOD}_m \le_{cd} L(A)$ (hence implying $L(A) \notin \mathbf{AC}^0$),

* vertically visibly pushdown grammars $G_1, \dots, G_m$ each generating intermediate VPLs such that $L =_{cd} \bigcup_{i=1}^m L(G_i)$. In this case one can moreover effectively compute $k, l \in \mathbb{N}$ with $k \neq l$ such that $\mathcal{L}_{k,l} \le_{cd} L(A)$.

Theorem 2.9 and the following conjecture imply the existence of an algorithm that decides if a given visibly pushdown language is in $\mathbf{AC}^0$.

**Conjecture 2.10.** Either all intermediate VPLs are in $\mathbf{AC}^0$ or all are not.

## 2.3 Corollary for visibly counter languages

A *visibly counter automaton* with threshold $m$ ($m$-VCA) over a visibly pushdown alphabet $\Sigma$ is a tuple $A = (Q, \Sigma, q_0, F, \delta_0, \dots, \delta_m)$, where $Q$ is a finite set of states, $q_0$ is the *initial state*, $F \subseteq Q$ is a set of final states, $m \ge 0$ is a *threshold*, and $\delta_i : Q \times \Sigma \to Q$ is a *transition function* for each $i \in [0, m]$.

A configuration of $A$ is an element of $Q \times \mathbb{N}$. For any two configurations $(q, n)$, $(q', n')$ and any $x \in \Sigma$ we define $(q, n) \xrightarrow{x} A (q', n')$ if $q' = \delta_{\min(n,m)}(q, x)$ and $n' = n + \Delta(x)$. The relation $\xrightarrow{w} A$ is naturally extended to $\xrightarrow{w} A$ for $w \in \Sigma^*$. By $L(A) = \{w \in \Sigma^\Delta \mid \exists q \in F : (q_0, 0) \xrightarrow{w} A (q, 0)\}$ we denote the *language* (of well-matched words) of $A$. We remark that the language of any $m$-VCA is a visibly pushdown language. We also remark that the languages of $m$-VCAs are defined to be sets of well-matched words as in [3], whereas in [23] the well-matched requirement is not present.

The following corollary implies the main result of [23] when restricted to well-matched words.

**Corollary 2.11.** There is an algorithm that, given an $m$-VCA $A$, correctly outputs either that $L(A)$ is in $\mathbf{AC}^0$ or some $m \ge 2$ such that $\mathrm{MOD}_m \le_{cd} L(A)$ (hence implying $L(A) \notin \mathbf{AC}^0$).

For the proof of Corollary 2.11 we refer to Section 5.5.

# 3 Language-theoretic and algebraic foundations and Ext-Algebras

## 3.1 Basic algebraic automata theory

For a thorough introduction to algebraic automata theory, we refer the reader to the two classical references of the domain by Eilenberg [12, 13] and Pin [26], but also to the following central reference in automata theory [27, Chapter 1].

A *semigroup* is a pair $(M, \cdot)$, where $M$ is a non-empty set and $\cdot$ is a binary operation on $M$ that is associative, i.e. $x \cdot (y \cdot z) = (x \cdot y) \cdot z$ for all $x, y, z \in M$. Usually, when the operation is clear from
the context, we write it multiplicatively and write just $M$ instead of $(M, \cdot)$. The semigroup $M$ is
trivial if $|M| = 1$, and non-trivial otherwise. A subsemigroup of $M$ is a semigroup $N$ such that $N$ is
a subset of $M$ and the operation of $N$ is the restriction of the operation of $M$ to $N$. We often just
write $xy$ to denote $x \cdot y$. An idempotent of a semigroup $M$ is an element $x \in M$ satisfying $x = xx$.
The idempotent power of a finite semigroup $M$ is the smallest positive integer $\omega$ such that $x^\omega$ is an
idempotent for all $x \in M$. The zero of a semigroup $M$ is the unique element $x \in M$ (if it exists)
satisfying $xy = yx = x$ for all $y \in M$. A monoid is a semigroup $M$ with a neutral element, that is,
an element $e \in M$ such that $x \cdot e = e \cdot x = x$ for all $x \in M$. We usually denote the neutral element
of a monoid $M$ by $1_M$. A submonoid of $M$ is a monoid $N$ that is a subsemigroup of $M$ containing
$1_M$ (which is thus also the neutral element of $N$). Consider some monoid $M$. A congruence on $M$
is an equivalence relation $\sim$ on $M$ that satisfies $vxz \sim vyz$ for all $v, z \in M$ and all $x, y \in M$ with
$x \sim y$. We denote by $[x]_\sim$ the equivalence class of $x \in M$. The quotient of $M$ with respect to a
congruence $\equiv$ is the monoid $M/\equiv$ with base set $M/\equiv=\{[m]_\equiv | m \in M\}$ and operation given by
$[x]_\equiv \cdot [y]_\equiv = [xy]_\equiv$ for all $x, y \in M$.

A group is a monoid $M$ in which for all $x \in M$ there exists an inverse, that is, an element $x' \in M$ such that $xx' = x'x = 1_M$. Each element in a group $M$ has a unique inverse, so we denote by $x^{-1}$ the unique inverse of an $x \in M$. A subgroup of a group $M$ is a submonoid of $M$ that is a group. Given a semigroup $M$, a set $S$ and a subsemigroup $N$ of $M$, whenever $N \subseteq S$, $N$ is said to be contained in $S$. A semigroup $M$ is aperiodic if it does not contain any non-trivial group. It is well-known that a finite semigroup $M$ is aperiodic if, and only if, given $\omega$ the idempotent power of $M$, it holds that $x^{\omega} = x^{\omega+1}$ for all $x \in M$ if, and only if, there exists $k \in \mathbb{N}_{>0}$ such that $x^k = x^{k+1}$ for all $x \in M$.

A morphism from a monoid $M$ to a monoid $N$ is a mapping $\varphi: M \to N$ such that $\varphi(1_M) = 1_N$
and $\varphi(xy) = \varphi(x)\varphi(y)$ for all $x, y \in M$. If $M = \Sigma^*$ and $N = \Gamma^*$ where $\Sigma$ and $\Gamma$ are finite alphabets,
we call $\varphi$ length-multiplying whenever there exists $k \in \mathbb{N}$ such that $\varphi(\Sigma) \subseteq \Gamma^k$. Let $\varphi: \Sigma^* \to M$
be a morphism, where $\Sigma$ is a finite alphabet and $M$ is finite. Then there exists $l \in \mathbb{N}_{>0}$ such that
$\varphi(\Sigma^l) = \varphi(\Sigma^{2l})$: this implies that $\varphi(\Sigma^l)$ is a semigroup. The smallest such $l$ is called the stability
index of the morphism $\varphi$. It is easily shown that if $\varphi(\Sigma^n)$ contains a non-trivial group for some
$n \in \mathbb{N}$, then so does $\varphi(\Sigma^l)$. We say that $h$ is quasi-aperiodic if $\varphi(\Sigma^n)$ does not contain any non-
trivial group for all $n \in \mathbb{N}$, which is equivalent to the fact that $\varphi(\Sigma^l)$ is aperiodic. (See [5, 29] for
the original definition and [30] for the definition using the stability index, though it has been only
formulated for surjective morphisms.)

A language $L$ over a finite alphabet $\Sigma$ is *recognized* by a monoid $M$ if there is a morphism
$\varphi: \Sigma^* \to M$ and $F \subseteq M$ such that $L = \varphi^{-1}(F)$. The *syntactic monoid* of a language $L \subseteq \Sigma^*$ is the
quotient of $\Sigma^*$ by the congruence $\sim_L$ (called the *syntactic congruence of* $L$) defined by $x \sim_L y$ for
$x, y \in \Sigma^*$ whenever for all $u, v \in \Sigma^*$, $uxv \in L \Leftrightarrow uyv \in L$. The syntactic monoid of $L$ recognizes $L$
via the *syntactic morphism* of $L$ sending any word $w \in \Sigma^*$ to $[w]_{\sim_L}$. A fundamental and well-known
result is that a language $L$ is regular if, and only if, it is recognized by a finite monoid if, and only
if, its syntactic monoid is finite.

## 3.2 Ext-algebras

This section builds on [10], but identifies an inaccuracy in the definition of Ext-algebra morphisms
to establish freeness.

Let $(M, \cdot, 1_M)$ be a monoid. For each $m \in M$, we shall respectively denote by $\text{left}_m$ and $\text{right}_m$
the left-multiplication map $x \mapsto m \cdot x$ and the right-multiplication map $x \mapsto x \cdot m$.

**Definition 3.1.** An Ext-algebra $(R, O, \cdot, \circ)$ consists of a monoid $(R, \cdot, 1_R)$ and a monoid $(O, \circ, 1_O)$
that is a submonoid of $(R^R, \circ)$ containing the maps $\text{left}_r$ and $\text{right}_r$ for each $r \in R$.
**Definition 3.2.** Let $(R, O)$ and $(S, P)$ be Ext-algebras. An Ext-algebra morphism from $(R, O)$ to $(S, P)$ is a pair $(\varphi, \psi)$ of monoid morphisms $\varphi: R \to S$ and $\psi: O \to P$ such that:

* for all $e \in O$ and $r \in R$ we have $\psi(e)(\varphi(r)) = \varphi(e(r))$;

* for all $r \in R$ we have $\psi(\text{left}_r) = \text{left}_{\varphi(r)}$ and $\psi(\text{right}_r) = \text{right}_{\varphi(r)}$.

We write $(\varphi, \psi): (R, O) \to (S, P)$. The morphism $(\varphi, \psi)$ is called surjective (respectively bijective) if both $\varphi$ and $\psi$ are surjective (respectively bijective).

When it is clear from the context, we shall write *morphism* to mean *Ext-algebra morphism*.

**Remark 3.3.** In the above definition, $\varphi$ is totally determined by $\psi$, because for each $r \in R$, we have $\varphi(r) = \varphi(\text{left}_r(1_R)) = \psi(\text{left}_r)(\varphi(1_R)) = \psi(\text{left}_r)(1_S)$.

**Definition 3.4.** Let $(R, O)$ and $(S, P)$ be Ext-algebras. Then

* $(R, O)$ is a sub-Ext-algebra of $(S, P)$ whenever $R$ is a submonoid of $S$ and there exists a submonoid $O'$ of $P$ such that $O = \{e|_R | e \in O'\}$, so that we may denote $O$ by $O'|_R$.

* $(R, O)$ is a quotient of $(S, P)$ whenever there exists a surjective morphism from $(S, P)$ to $(R, O)$.

* $(R, O)$ divides $(S, P)$ whenever $(R, O)$ is a quotient of a sub-Ext-algebra of $(S, P)$.

For the rest of this section, let us fix some visibly pushdown alphabet $\Sigma$.

**Definition 3.5.** For all $(u, v) \in \text{Con}(\Sigma)$, consider the function $\text{ext}_{u,v}: \Sigma^\Delta \to \Sigma^*$ such that $\text{ext}_{u,v}(x) = u x v$ for all $x \in \Sigma^\Delta$. We call

$$ \text{ext}_{u,v} = \text{ext}_{x_1, y_1} \circ \dots \circ \text{ext}_{x_m, y_m} $$

a factorization of $\text{ext}_{u,v}$. That is, $u = x_1 \dots x_m$, $v = y_m \dots y_1$.

The following lemma states that each $\text{ext}_{u,v}$ has a unique factorization when restricting the $(x_i, y_i)$ to be from $\Sigma^\Delta \times \Sigma^\Delta$ or from $\Sigma_{\text{call}} \times \Sigma_{\text{ret}}$ and minimizing the number of $(x_i, y_i) \in \Sigma^\Delta \times \Sigma^\Delta$: we obtain its so-called *stair factorization*.

**Lemma 3.6.** For all $\text{ext}_{u,v}$ there exists a unique factorization

$$ \text{ext}_{u,v} = \text{ext}_{x_1, y_1} \circ \text{ext}_{a_1, b_1} \circ \dots \circ \text{ext}_{x_{h-1}, y_{h-1}} \circ \text{ext}_{a_{h-1}, b_{h-1}} \circ \text{ext}_{x_h, y_h} $$

satisfying $h \ge 1$, $x_i, y_i \in \Sigma^\Delta$ for all $i \in [1, h]$ and $a_i \in \Sigma_{\text{call}}$ and $b_i \in \Sigma_{\text{ret}}$ for all $i \in [1, h-1]$. In particular, $\text{ext}_{u,v}$ is in fact a function from $\Sigma^\Delta$ to $\Sigma^\Delta$.

*Proof.* We show additionally that the required factorization must satisfy $h = \Delta(u) + 1$. We prove the statement by induction on $|uv|$. In case $|uv| \le 1$, then either $\text{ext}_{u,v} = \text{ext}_{\varepsilon, \varepsilon}$, or there is some $c \in \Sigma_{\text{int}}$ such that $\text{ext}_{u,v} = \text{ext}_{\varepsilon, c}$ or $\text{ext}_{u,v} = \text{ext}_{c, \varepsilon}$. In any of these cases, we uniquely factorize $\text{ext}_{u,v}$ as $\text{ext}_{x_1, y_1}$ with $x_1 = u$ and $y_1 = v$.

Let us consider the case when $|uv| \ge 2$ and let $h = \Delta(u) + 1$. Note that since $uv \in \Sigma^\Delta$ we have $u \in \Sigma^\Delta$ if, and only if, $v \in \Sigma^\Delta$. In case $u, v \in \Sigma^\Delta$ we have $\Delta(u) = 0$, hence the only factorization of the desired form is indeed $\text{ext}_{u,v} = \text{ext}_{x_1, y_1}$, where $x_1 = u$ and $y_1 = v$. Let us finally treat the case when $u, v \notin \Sigma^\Delta$, thus $\Delta(u) \ge 1$ and hence $h \ge 2$. Let $x$ be the maximal prefix of $u$ satisfying $x \in \Sigma^\Delta$ and let $y$ be the maximal suffix of $v$ satisfying $y \in \Sigma^\Delta$. Due to maximality of $x$ and $y$ there
must exist $a \in \Sigma_{\text{call}}, b \in \Sigma_{\text{ret}}$, and $u', v' \in \Sigma^*$ such that $u = xau', v = v'by$ and $u'v' \in \Sigma^\Delta$ with $\Delta(u') = \Delta(u) - 1 = h - 2$. Let $\text{ext}_{x_1,y_1} \circ \text{ext}_{a_1,b_1} \circ \dots \circ \text{ext}_{x_{h-2},y_{h-2}} \circ \text{ext}_{a_{h-2},b_{h-2}} \circ \text{ext}_{x_{h-1},y_{h-1}}$ be the unique factorization of the desired form for $\text{ext}_{u',v'}$ by induction hypothesis. We claim that

$$ \text{ext}_{x,y} \circ \text{ext}_{a,b} \circ \text{ext}_{x_1,y_1} \circ \text{ext}_{a_1,b_1} \circ \dots \circ \text{ext}_{x_{h-2},y_{h-2}} \circ \text{ext}_{a_{h-2},b_{h-2}} \circ \text{ext}_{x_{h-1},y_{h-1}} $$

is the unique factorization of the desired form for $\text{ext}_{u,v}$. Indeed, since $\Delta(u) \ge 1$ any potential factorization of the desired form for $\text{ext}_{u,v}$ must be of the form $\text{ext}_{x',y'} \circ \text{ext}_{a',b'} \circ \pi$, where $x'$ is a prefix of $u$ satisfying $x' \in \Sigma^\Delta$, $y'$ is a suffix of $v$ satisfying $y' \in \Sigma^\Delta$, $a' \in \Sigma_{\text{call}}$, and $b' \in \Sigma_{\text{ret}}$. In particular $x'$ is a prefix of $x$ and $y'$ is suffix of $y$. In case $x' = x$ and $y' = y$ it follows $a' = a$ and $b' = b$ and uniqueness follows from induction hypothesis. It remains to consider the case when $x'$ is a strict prefix of $x$ or $y'$ is a strict suffix of $y$. We only treat the former case. It must hold $x = x'a's$ for some $s \in \Sigma^+$ such that $a's \in \Sigma^\Delta$. But then $\pi$ is a factorization for $\text{ext}_{su',v'z}$ for some $z \in \Sigma^*$ which is a contradiction since $\Delta(s) = -1$ due to $a's \in \Sigma^\Delta$. $\square$

In the following we will denote the unique factorization provided by Lemma 3.6 as the *stair factorization* of $\text{ext}_{u,v}$. Consider now the set $\mathcal{O}(\Sigma^\Delta)$ of all functions $\text{ext}_{u,v}$ for $(u,v) \in \text{Con}(\Sigma)$: it is a subset of $(\Sigma^\Delta)^{\Sigma^\Delta}$ closed under composition. Thus, $(\mathcal{O}(\Sigma^\Delta), \circ)$ is a submonoid of $((\Sigma^\Delta)^{\Sigma^\Delta}, \circ)$. Since for all $w \in \Sigma^\Delta$ we have $\text{left}_w = \text{ext}_{w,\varepsilon}$ and $\text{right}_w = \text{ext}_{\varepsilon,w}$, the set $\mathcal{O}(\Sigma^\Delta)$ contains the functions $\text{left}_w$ and $\text{right}_w$ for all $w \in \Sigma^\Delta$. Hence, $(\Sigma^\Delta, \mathcal{O}(\Sigma^\Delta), \circ, \circ)$ is an Ext-algebra. The following important proposition establishes freeness of $(\Sigma^\Delta, \mathcal{O}(\Sigma^\Delta))$.

**Proposition 3.7.** Let $(R, O)$ be an Ext-algebra and consider two functions $\varphi: \Sigma_{\text{int}} \to R$ and $\psi: \{\text{ext}_{a,b} | a \in \Sigma_{\text{call}}, b \in \Sigma_{\text{ret}}\} \to O$. Then there exists a unique Ext-algebra morphism $(\bar{\varphi}, \bar{\psi})$ from $(\Sigma^\Delta, \mathcal{O}(\Sigma^\Delta))$ to $(R, O)$ satisfying $\bar{\varphi}(c) = \varphi(c)$ for each $c \in \Sigma_{\text{int}}$ and $\bar{\psi}(\text{ext}_{a,b}) = \psi(\text{ext}_{a,b})$ for each $a \in \Sigma_{\text{call}}, b \in \Sigma_{\text{ret}}$.

*Proof.* We define $\bar{\varphi}$ based on a refinement of the structural definition of well-matched words. For each $w \in \Sigma^\Delta$ we inductively define:

$$ \bar{\varphi}(w) = \begin{cases} 1_R & \text{if } w = \varepsilon \text{ (type 1)} \\ \varphi(c) & \text{if } w = c \in \Sigma_{\text{int}} \text{ (type 2)} \\ \psi(\text{ext}_{a,b})(\bar{\varphi}(x)) & \text{if } w = axb \text{ for } a \in \Sigma_{\text{call}}, b \in \Sigma_{\text{ret}} \text{ and } x \in \Sigma^\Delta \text{ (type 3)} \\ \bar{\varphi}(x)\bar{\varphi}(y) & \text{if } w = xy \text{ for } x, y \in \Sigma^\Delta \setminus \{\varepsilon\}, \text{ where } |x| \text{ is minimal (type 4)} \end{cases} $$

Observe that the four above types give unique decompositions. For proving that $\bar{\varphi}$ is indeed a monoid morphism one proves that for all $w, v \in \Sigma^\Delta$ we have $\bar{\varphi}(wv) = \bar{\varphi}(w)\bar{\varphi}(v)$ by structural induction on $w$ given by the four types. The case $v = \varepsilon$ is direct, we only treat the case $v \in \Sigma^\Delta \setminus \{\varepsilon\}$ in the following. If $w$ is of type 1 we have $\bar{\varphi}(wv) = \bar{\varphi}(v) = 1_R \cdot \bar{\varphi}(v) = \bar{\varphi}(w)\bar{\varphi}(v)$. If $w$ is of type 2 or 3, then $wv$ is of type 4 and $w$ is the shortest prefix of $wv$ with $w \in \Sigma^\Delta \setminus \{\varepsilon\}$, hence $\bar{\varphi}(wv) = \bar{\varphi}(w)\bar{\varphi}(v)$. If $w$ is of type 4, then $w = xy$ for some $x, y \in \Sigma^\Delta \setminus \{\varepsilon\}$, where $x$ is of minimal length. Then $wv$ is of type 4, where $wv = x(yv)$ and $x$ is the shortest prefix of $wv$ with $x \in \Sigma^\Delta \setminus \{\varepsilon\}$. Hence $\bar{\varphi}(wv) = \bar{\varphi}(x)\bar{\varphi}(yv) = \bar{\varphi}(x)\bar{\varphi}(y)\bar{\varphi}(v) = \bar{\varphi}(xy)\bar{\varphi}(v) = \bar{\varphi}(w)\bar{\varphi}(v)$, where the first equality follows by definition of $\bar{\varphi}$ and the second and third equality follow from the induction hypothesis. Given any $\text{ext}_{u,v} \in \mathcal{O}(\Sigma^\Delta)$ let

$$ \text{ext}_{u,v} = \text{ext}_{x_1,y_1} \circ \text{ext}_{a_1,b_1} \circ \dots \circ \text{ext}_{x_{h-1},y_{h-1}} \circ \text{ext}_{a_{h-1},b_{h-1}} \circ \text{ext}_{x_h,y_h} $$
be the unique stair factorization given by Lemma 3.6. We define

$$ \bar{\psi}(\mathrm{ext}_{u,v}) = \bigcirc_{i=1}^{h-1} (\mathrm{left}_{\bar{\varphi}(x_i)} \circ \mathrm{right}_{\bar{\varphi}(y_i)} \circ \psi(\mathrm{ext}_{a_i,b_i})) \circ \mathrm{left}_{\bar{\varphi}(x_h)} \circ \mathrm{right}_{\bar{\varphi}(y_h)}. $$

For showing that $\bar{\psi}$ is indeed a monoid morphism, one proves $\bar{\psi}(\mathrm{ext}_{uu',v'v}) = \bar{\psi}(\mathrm{ext}_{u,v}) \circ \bar{\psi}(\mathrm{ext}_{u',v'})$ for all $\mathrm{ext}_{u,v}$, $\mathrm{ext}_{u',v'} \in \mathcal{O}(\Sigma^\Delta)$ by observing simply that the unique stair factorization of $\mathrm{ext}_{uu',v'v}$ is obtained by composing the unique stair factorizations of $\mathrm{ext}_{u,v}$ and $\mathrm{ext}_{u',v'}$.

We now show that $(\bar{\varphi}, \bar{\psi})$ is in fact an Ext-algebra morphism. The discussion above first shows that both $\bar{\varphi}: \Sigma^\Delta \to R$ and $\bar{\psi}: \mathcal{O}(\Sigma^\Delta) \to O$ are monoid morphisms. Next, let us prove that for all $\mathrm{ext}_{u,v} \in \mathcal{O}(\Sigma^\Delta)$ and $w \in \Sigma^\Delta$ we have $\bar{\psi}(\mathrm{ext}_{u,v})(\bar{\varphi}(w)) = \bar{\varphi}(\mathrm{ext}_{u,v}(w))$. Let

$$ \mathrm{ext}_{u,v} = \mathrm{ext}_{x_1, y_1} \circ \mathrm{ext}_{a_1, b_1} \circ \cdots \circ \mathrm{ext}_{x_{h-1}, y_{h-1}} \circ \mathrm{ext}_{a_{h-1}, b_{h-1}} \circ \mathrm{ext}_{x_h, y_h} $$

be the unique stair factorization of $\mathrm{ext}_{u,v}$ provided by Lemma 3.6. If $h = 1$, then

$$ \bar{\psi}(\mathrm{ext}_{u,v})(\bar{\varphi}(w)) = \mathrm{left}_{\bar{\varphi}(x_h)} \circ \mathrm{right}_{\bar{\varphi}(y_h)}(\bar{\varphi}(w)) = \bar{\varphi}(x_h w y_h) = \bar{\varphi}(\mathrm{ext}_{u,v}(w)). $$

Otherwise, we have

$$
\begin{align*}
& \bar{\psi}(\mathrm{ext}_{u,v})(\bar{\varphi}(w)) \\
&= \bigcirc_{i=1}^{h-1} (\mathrm{left}_{\bar{\varphi}(x_i)} \circ \mathrm{right}_{\bar{\varphi}(y_i)} \circ \psi(\mathrm{ext}_{a_i,b_i})) \circ \mathrm{left}_{\bar{\varphi}(x_h)} \circ \mathrm{right}_{\bar{\varphi}(y_h)}(\bar{\varphi}(w)) \\
&= \bigcirc_{i=1}^{h-1} (\mathrm{left}_{\bar{\varphi}(x_i)} \circ \mathrm{right}_{\bar{\varphi}(y_i)} \circ \psi(\mathrm{ext}_{a_i,b_i})) (\bar{\varphi}(x_h w y_h)) \\
&= \bigcirc_{i=1}^{h-2} (\mathrm{left}_{\bar{\varphi}(x_i)} \circ \mathrm{right}_{\bar{\varphi}(y_i)} \circ \psi(\mathrm{ext}_{a_i,b_i})) \circ \\
& \qquad \mathrm{left}_{\bar{\varphi}(x_{h-1})} \circ \mathrm{right}_{\bar{\varphi}(y_{h-1})} \circ \psi(\mathrm{ext}_{a_{h-1},b_{h-1}})(\bar{\varphi}(x_h w y_h)) \\
&= \bigcirc_{i=1}^{h-2} (\mathrm{left}_{\bar{\varphi}(x_i)} \circ \mathrm{right}_{\bar{\varphi}(y_i)} \circ \psi(\mathrm{ext}_{a_i,b_i})) \circ \\
& \qquad \mathrm{left}_{\bar{\varphi}(x_{h-1})} \circ \mathrm{right}_{\bar{\varphi}(y_{h-1})}(\bar{\varphi}(a_{h-1} x_h w y_h b_{h-1})) \\
&= \bigcirc_{i=1}^{h-2} (\mathrm{left}_{\bar{\varphi}(x_i)} \circ \mathrm{right}_{\bar{\varphi}(y_i)} \circ \psi(\mathrm{ext}_{a_i,b_i})) (\bar{\varphi}(x_{h-1} a_{h-1} x_h w y_h b_{h-1} y_{h-1})) \\
&= \cdots \\
&= \bar{\varphi}(x_1 a_1 \cdots x_{h-1} a_{h-1} x_h w y_h b_{h-1} y_{h-1} \cdots b_1 y_1) \\
&= \bar{\varphi}(\mathrm{ext}_{u,v}(w)).
\end{align*}
$$

Let us prove that for all $w \in \Sigma^\Delta$ we have $\bar{\psi}(\mathrm{left}_w) = \mathrm{left}_{\bar{\varphi}(w)}$. Noting that the unique stair factorization of $\mathrm{left}_w$ is $\mathrm{ext}_{w,\varepsilon}$ we obtain

$$ \bar{\psi}(\mathrm{left}_w) = \bar{\psi}(\mathrm{ext}_{w,\varepsilon}) = \mathrm{left}_{\bar{\varphi}(w)} \circ \mathrm{right}_{\bar{\varphi}(\varepsilon)} = \mathrm{left}_{\bar{\varphi}(w)} \circ \mathrm{right}_{1_R} = \mathrm{left}_{\bar{\varphi}(w)} \circ 1_O = \mathrm{left}_{\bar{\varphi}(w)}. $$

One proves $\bar{\psi}(\mathrm{right}_w) = \mathrm{right}_{\bar{\varphi}(w)}$ for all $w \in \Sigma^\Delta$ analogously.

Therefore, $(\bar{\varphi}, \bar{\psi})$ is an Ext-algebra morphism and it is the unique one satisfying $\bar{\varphi}(c) = \varphi(c)$ for each $c \in \Sigma_{\mathrm{int}}$ and $\bar{\psi}(\mathrm{ext}_{a,b}) = \psi(\mathrm{ext}_{a,b})$ for each $a \in \Sigma_{\mathrm{call}}$, $b \in \Sigma_{\mathrm{ret}}$. Take indeed any such Ext-algebra morphism $(\varphi', \psi')$: using the properties of Ext-algebra morphisms, it is straightforward to prove that then $\bar{\varphi}(w) = \varphi'(w)$ for all $w \in \Sigma^\Delta$ by structural induction on $w$ and then to prove that $\bar{\psi}(\mathrm{ext}_{u,v}) = \psi'(\mathrm{ext}_{u,v})$ for all $\mathrm{ext}_{u,v} \in \mathcal{O}(\Sigma^\Delta)$ by using the unique stair factorization of $\mathrm{ext}_{u,v}$ provided by Lemma 3.6. $\square$

**Remark 3.8.** The second condition in Definition 3.2, i.e. for all $r \in R$ we have $\psi(\mathrm{left}_r) = \mathrm{left}_{\varphi(r)}$ and $\psi(\mathrm{right}_r) = \mathrm{right}_{\varphi(r)}$, does not appear in the definition of Ext-algebra morphisms given in [10].
But this is actually problematic, because then Proposition 3.7 would not hold in general.

Indeed, consider for instance the visibly pushdown alphabet $\Gamma$ where $\Gamma_{call} = \{a\}$, $\Gamma_{int} = \emptyset$ and $\Gamma_{ret} = \{b\}$, where $R$ is the semi-lattice on two elements $\{0, 1\}$ such that $1 \cdot 1 = 1$ and $0 \cdot 1 = 1 \cdot 0 = 0 \cdot 0 = 0$; and moreover $O$ is defined as $\{\text{id}, \mathbf{0}, \mathbf{1}\}$ with $\mathbf{0}(0) = \mathbf{0}(1) = 0$ and $\mathbf{1}(0) = \mathbf{1}(1) = 1$. Then $(R, O)$ is an Ext-algebra. Let us define the function $\varphi: \Gamma^\Delta \to R$ by $\varphi(w) = 1$ for all $w \in \Gamma^\Delta$ and the function $\psi: \mathcal{O}(\Gamma^\Delta) \to O$ by $\psi(\text{ext}_{a^n, b^n}) = \text{id}$ for all $n \in \mathbb{N}$ and $\psi(\text{ext}_{u, v}) = \mathbf{1}$ for all $u, v \in \Gamma^*$ with $uv \in \Gamma^\Delta$ and $(u \in a^*b\Gamma^*$ or $v \in \Gamma^*a\Gamma^*b)$. The pair $(\varphi, \psi)$ forms a morphism from $(\Gamma^\Delta, \mathcal{O}(\Gamma^\Delta))$ to $(R, O)$, but it is not the only one sending $\text{ext}_{a,b}$ to id, because we could also take $\psi$ to send all elements of $\mathcal{O}(\Gamma^\Delta)$ to id.

**Definition 3.9.** A language $L \subseteq \Sigma^\Delta$ is recognized by an Ext-algebra $(R, O)$ whenever there exists a morphism $(\varphi, \psi): (\Sigma^\Delta, \mathcal{O}(\Sigma^\Delta)) \to (R, O)$ such that $L = \varphi^{-1}(F)$ for some $F \subseteq R$.

**Example 3.10.** Consider the language $\mathcal{L}_{1,2} = L(S \to aSb_1 | acSb_2 | \varepsilon)$ from Example 2.5 over the visibly pushdown alphabet $\Gamma$, where $\Gamma_{int} = \{c\}$, $\Gamma_{call} = \{a\}$ and $\Gamma_{ret} = \{b_1, b_2\}$. Consider the Ext-algebra $(R, O)$ defined as follows. We set $R = \{acb_1, \varepsilon, c, cab_1, ab_1\}$ with multiplication given by the following table:

<table><thead><tr><th>.</th><th>acb<sub>1</sub></th><th>ε</th><th>c</th><th>cab<sub>1</sub></th><th>ab<sub>1</sub></th></tr></thead><tbody><tr><th>acb<sub>1</sub></th><td>acb<sub>1</sub></td><td>acb<sub>1</sub></td><td>acb<sub>1</sub></td><td>acb<sub>1</sub></td><td>acb<sub>1</sub></td></tr><tr><th>ε</th><td>acb<sub>1</sub></td><td>ε</td><td>c</td><td>cab<sub>1</sub></td><td>ab<sub>1</sub></td></tr><tr><th>c</th><td>acb<sub>1</sub></td><td>c</td><td>acb<sub>1</sub></td><td>acb<sub>1</sub></td><td>cab<sub>1</sub></td></tr><tr><th>cab<sub>1</sub></th><td>acb<sub>1</sub></td><td>cab<sub>1</sub></td><td>acb<sub>1</sub></td><td>acb<sub>1</sub></td><td>acb<sub>1</sub></td></tr><tr><th>ab<sub>1</sub></th><td>acb<sub>1</sub></td><td>ab<sub>1</sub></td><td>acb<sub>1</sub></td><td>acb<sub>1</sub></td><td>acb<sub>1</sub></td></tr></tbody></table>

Thus, observe that $\varepsilon = 1_R$ and $acb_1$ is the zero of $R$. Omitting its multiplication table, we set the monoid $O$ to be the following

$$O = \{(acb_1, \varepsilon), (\varepsilon, \varepsilon), (c, \varepsilon), (\varepsilon, c), (ab_1, \varepsilon), (\varepsilon, ab_1), (cab_1, \varepsilon)\} \cup \{(a, b_2), (ca, b_2), (ca, ab_1b_2), (ca, b_1), (a, ab_1b_2), (a, b_1)\},$$

where the elements in the first set comprise $\{\text{left}_r, \text{right}_r | r \in R\}$, more precisely

* $(acb_1, \varepsilon) = \text{left}_{acb_1} = \text{right}_{acb_1}$,

* $(\varepsilon, \varepsilon) = \text{left}_\varepsilon = \text{right}_\varepsilon = 1_O$,

* $(c, \varepsilon) = \text{left}_c$,

* $(\varepsilon, c) = \text{right}_c$,

* $(ab_1, \varepsilon) = \text{left}_{ab_1}$,

* $(\varepsilon, ab_1) = \text{right}_{ab_1}$,

* $(cab_1, \varepsilon) = \text{left}_{cab_1} = \text{right}_{cab_1}$,

and where the elements from the second set are the following functions from $R$ to $R$, respectively:

* $(a, b_2)$:

$$\begin{array}{c||c|c|c|c|c}
r & acb_1 & \varepsilon & c & cab_1 & ab_1 \\
(a, b_2)(r) & acb_1 & acb_1 & ab_1 & ab_1 & acb_1
\end{array}$$

* $(ca, b_2)$:

$$\begin{array}{c||c|c|c|c|c}
r & acb_1 & \varepsilon & c & cab_1 & ab_1 \\
(ca, b_2)(r) & acb_1 & acb_1 & cab_1 & cab_1 & acb_1
\end{array}$$
• $(ca, ab_1b_2):$

$$ \begin{array}{c||cccccc} r & acb_1 & \varepsilon & c & cab_1 & ab_1 \\ \hline (ca, ab_1b_2)(r) & acb_1 & acb_1 & cab_1 & acb_1 & acb_1 \end{array} $$

• $(ca, b_1):$

$$ \begin{array}{c||cccccc} r & acb_1 & \varepsilon & c & cab_1 & ab_1 \\ \hline (ca, b_1)(r) & acb_1 & cab_1 & acb_1 & acb_1 & cab_1 \end{array} $$

• $(a, ab_1b_2):$

$$ \begin{array}{c||cccccc} r & acb_1 & \varepsilon & c & cab_1 & ab_1 \\ \hline (a, ab_1b_2)(r) & acb_1 & acb_1 & ab_1 & acb_1 & acb_1 \end{array} $$

• $(a, b_1):$

$$ \begin{array}{c||cccccc} r & acb_1 & \varepsilon & c & cab_1 & ab_1 \\ \hline (a, b_1)(r) & acb_1 & ab_1 & acb_1 & acb_1 & ab_1 \end{array} $$

Consider the unique morphism $(\varphi, \psi): (\Gamma^{\Delta}, \mathcal{O}(\Gamma^{\Delta})) \to (R, O)$ that (thanks to Proposition 3.7) satisfies $\varphi(c) = c$, $\psi(\mathrm{ext}_{a,b_1}) = (a, b_1)$ and $\psi(\mathrm{ext}_{a,b_2}) = (a, b_2)$. We have $L = \varphi^{-1}(\{\varepsilon, ab_1\})$.

**Definition 3.11.** Let $(R, O)$ be an Ext-algebra. An equivalence relation on $(R, O)$ is an equivalence relation $\sim$ on $R$. We say an equivalence relation $\sim$ is a congruence on $(R, O)$ whenever for all $e \in O$ and for all $x, y \in R$ we have that $x \sim y$ implies $e(x) \sim e(y)$. In case $\sim$ is a congruence we denote by $(R, O)/\sim$ the pair $(R/\sim, O')$, where

$$ O' = \{e' \in (R/\sim)^{R/\sim} \mid \exists e \in O \ \forall x \in R: e'([x]_{\sim}) = [e(x)]_{\sim}\}. $$

The following lemma actually shows that $(R, O)/\sim$ is again an Ext-algebra, that we call the quotient of $(R, O)$ by $\sim$.

**Lemma 3.12.** Let $(R, O)$ be an Ext-algebra and $\sim$ be a congruence on $(R, O)$. Then $(R/\sim, O')$, with

$$ O' = \{e' \in (R/\sim)^{R/\sim} \mid \exists e \in O \ \forall x \in R: e'([x]_{\sim}) = [e(x)]_{\sim}\} $$

a submonoid of $(R/\sim)^{R/\sim}$, is an Ext-algebra and the pair $(\varphi, \psi)$ of functions $\varphi: R \to R/\sim$ and $\psi: O \to O'$ satisfying $\varphi(r) = [r]_{\sim}$ for all $r \in R$ and $\psi(e)([r]_{\sim}) = [e(r)]_{\sim}$ for all $e \in O$ and $r \in R$ is a surjective morphism from $(R, O)$ to $(R/\sim, O')$.

*Proof.* Let $u, v \in R$ such that $u \sim v$. Take any $x, y \in R$: we have that

$$ xuy = \mathrm{right}_y \circ \mathrm{left}_x(u) \sim \mathrm{right}_y \circ \mathrm{left}_x(v) = xvy $$

by definition of congruence. Thus, $\sim$ is a congruence on $R$. This implies that $R/\sim$ is a monoid.

Let $e', f' \in O'$: this means there exist $e, f \in O$ such that $e'([r]_{\sim}) = [e(r)]_{\sim}$ and $f'([r]_{\sim}) = [f(r)]_{\sim}$ for all $r \in R$. Given any $r \in R$, we thus have

$$ e' \circ f'([r]_{\sim}) = e'([f(r)]_{\sim}) = [e(f(r))]_{\sim} = [e \circ f(r)]_{\sim}, $$

so that $e' \circ f' \in O'$. Therefore, $O'$ is a submonoid of $(R/\sim)^{R/\sim}$ that contains the functions $\mathrm{left}_{[r]_{\sim}}$ and $\mathrm{right}_{[r]_{\sim}}$ for all $[r]_{\sim} \in R/\sim$. Thus, $(R/\sim, O')$ is an Ext-algebra.

Now define the functions $\varphi: R \to R/\sim$ and $\psi: O \to O'$ by respectively $\varphi(r) = [r]_{\sim}$ for all $r \in R$ and $\psi(e) = e'$ with $e' \in O'$ such that $e'([r]_{\sim}) = [e(r)]_{\sim}$ for all $r \in R$: this is well-defined because
~ is a congruence on $(R, O)$. Since ~ is a congruence on $R$, $\phi$ is a surjective monoid morphism. Further, let $e, f \in O$. We have

$$ 
\begin{align*}
\psi(e) \circ \psi(f)([r]_{\sim}) &= \psi(e)([f(r)]_{\sim}) \\
&= [e(f(r))]_{\sim} \\
&= [e \circ f(r)]_{\sim} \\
&= \psi(e \circ f)([r]_{\sim})
\end{align*}
$$

for all $r \in R$, so that $\psi(e) \circ \psi(f) = \psi(e \circ f)$. Therefore, as $\psi(1_O)([r]_{\sim}) = [1_O(r)]_{\sim} = [r]_{\sim}$ for all $r \in R$, it follows that $\psi$ is also a monoid morphism, that is obviously surjective. By construction, we do of course have that

$$ \psi(e)(\varphi(r)) = \psi(e)([r]_{\sim}) = [e(r)]_{\sim} = \varphi(e(r)) $$

for all $e \in O$ and $r \in R$. Moreover, for all $r \in R$, it holds that

$$ \psi(\text{left}_r)([x]_{\sim}) = [\text{left}_r(x)]_{\sim} = [rx]_{\sim} = [r]_{\sim}[x]_{\sim} = \text{left}_{\varphi(r)}([x]_{\sim}) $$

for all $x \in R$, so that $\psi(\text{left}_r) = \text{left}_{\varphi(r)}$. Similarly, we can prove that $\psi(\text{right}_r) = \text{right}_{\varphi(r)}$ for all $r \in R$. Thus, $(\varphi, \psi)$ is a surjective morphism from $(R, O)$ to $(R/\sim, O')$. $\square$

The lemma also proves that the pair $(\varphi, \psi)$ of functions $\varphi: R \to R/\sim$ and $\psi: O \to O'$ satisfying $\varphi(r) = [r]_{\sim}$ for all $r \in R$ and $\psi(e)([r]_{\sim}) = [e(r)]_{\sim}$ for all $e \in O$ and $r \in R$ is a surjective morphism from $(R, O)$ to $(R, O)/\sim$. We also call this pair $(\varphi, \psi)$ the *morphism associated to the congruence* $\sim$.

**Definition 3.13.** The syntactic congruence of a language $L \subseteq \Sigma^\Delta$ is the congruence $\sim_L$ on $(\Sigma^\Delta, \mathcal{O}(\Sigma^\Delta))$ defined by $u \sim_L v$ for $u, v \in \Sigma^\Delta$ whenever $e(u) \in L \Leftrightarrow e(v) \in L$ for all $e \in \mathcal{O}(\Sigma^\Delta)$. We define the syntactic Ext-algebra of $L$ to be $(R_L, O_L) = (\Sigma^\Delta, \mathcal{O}(\Sigma^\Delta))/\sim_L$ and the syntactic morphism of $L$ to be the morphism $(\varphi_L, \psi_L)$ associated to $\sim_L$.

Note that the syntactic Ext-algebra $(R_L, O_L)$ of $L$ recognizes $L$ via the syntactic morphism $(\varphi_L, \psi_L)$. Indeed, for all $u, v \in \Sigma^\Delta$, we have that if $u \sim_L v$, then $u \in L \Leftrightarrow v \in L$. This implies that $L = \varphi_L^{-1}(\varphi_L(L))$. For instance, it can be proven that the Ext-algebra recognizing the language $\mathcal{L}_{1,2}$ in Example 3.10 is in fact a certain presentation of the syntactic Ext-algebra of $\mathcal{L}_{1,2}$.

The next lemma states that all languages recognized by an Ext-algebra are also recognized by the Ext-algebras it divides.

**Lemma 3.14.** Let $(R, O)$ and $(S, P)$ be two Ext-algebras such that $(R, O)$ divides $(S, P)$. Then any language $L \subseteq \Sigma^\Delta$ recognized by $(R, O)$ is also recognized by $(S, P)$.

*Proof.* Let $L \subseteq \Sigma^\Delta$ be a language recognized by $(R, O)$. This means that there exists a morphism $(\varphi, \psi): (\Sigma^\Delta, \mathcal{O}(\Sigma^\Delta)) \to (R, O)$ such that $L = \varphi^{-1}(F)$ for some $F \subseteq R$. We will prove the lemma by combining the following two points:

(1) if $(R, O)$ is a sub-Ext-algebra of $(S, P)$, then so does $(S, P)$ recognize $L$, and

(2) if $(R, O)$ is a quotient of $(S, P)$, then so does $(S, P)$ recognize $L$.

For Point (1), assume that $(R, O)$ is a sub-Ext-algebra of $(S, P)$. This means that $R$ is a submonoid of $S$ and that there exists a submonoid $O'$ of $P$ satisfying $O = O'|_R$. Take an arbitrary
function $\sigma: O \to P$ such that $\sigma(e)|_R = e$ for all $e \in O$. Let us consider the unique morphism $(\varphi', \psi'):(\Sigma^\Delta, \mathcal{O}(\Sigma^\Delta)) \to (S, P)$ such that $\varphi'(c) = \varphi(c)$ for all $c \in \Sigma_{\text{int}}$ and $\psi'(\text{ext}_{a,b}) = \sigma(\psi(\text{ext}_{a,b}))$ for all $a \in \Sigma_{\text{call}}, b \in \Sigma_{\text{ret}}$, given to us by Proposition 3.7. We can prove by induction on $w$ that $\varphi'(w) = \varphi(w)$ for all $w \in \Sigma^\Delta$:

* $w = \varepsilon$. Then $\varphi'(w) = 1_S = 1_R = \varphi(w)$.

* $w = c$ for some $c \in \Sigma_{\text{int}}$. Then $\varphi'(w) = \varphi'(c) = \varphi(c) = \varphi(w)$.

* $w = aw'b$ for some $a \in \Sigma_{\text{call}}, b \in \Sigma_{\text{ret}}$ and $w' \in \Sigma^\Delta$. Then

$$ 
\begin{align*}
\varphi'(w) &= \varphi'(\text{ext}_{a,b}(w')) \\
&= \psi'(\text{ext}_{a,b})(\varphi'(w')) \\
&\stackrel{\text{IH}}{=} \sigma(\psi(\text{ext}_{a,b}))(\varphi(w')) \\
&= \sigma(\psi(\text{ext}_{a,b}))|_R(\varphi(w')) \\
&= \psi(\text{ext}_{a,b})(\varphi(w')) \\
&= \varphi(\text{ext}_{a,b}(w')) \\
&= \varphi(w) .
\end{align*}
$$

* $w = uv$ for some $u, v \in \Sigma^\Delta \setminus \{\varepsilon\}$. Then

$$ \varphi'(w) = \varphi'(u)\varphi'(v) \stackrel{\text{IH}}{=} \varphi(u)\varphi(v) = \varphi(w) . $$

Thus, $\varphi'^{-1}(F) = L$, which implies that $(S, P)$ recognizes $L$.

For Point (2), assume that $(R, O)$ is a quotient of $(S, P)$. This means that there exists a surjective morphism $(\alpha, \beta):(S, P) \to (R, O)$. Let us define an arbitrary function $\rho: \Sigma_{\text{int}} \to S$ such that $\rho(c) \in \alpha^{-1}(\varphi(c))$ for all $c \in \Sigma_{\text{int}}$ as well as an arbitrary function $\sigma: \{\text{ext}_{a,b} | a \in \Sigma_{\text{call}}, b \in \Sigma_{\text{ret}}\} \to P$ such that $\sigma(\text{ext}_{a,b}) \in \beta^{-1}(\psi(\text{ext}_{a,b}))$ for all $a \in \Sigma_{\text{call}}, b \in \Sigma_{\text{ret}}$. Now, take the unique morphism $(\varphi', \psi'):(\Sigma^\Delta, \mathcal{O}(\Sigma^\Delta)) \to (S, P)$ given by Proposition 3.7 for $\rho$ and $\sigma$: we claim that it is such that $\alpha(\varphi'(w)) = \varphi(w)$ for all $w \in \Sigma^\Delta$. We can prove it by induction on $w$:

* $w = \varepsilon$. Then $\alpha(\varphi'(w)) = \alpha(1_S) = 1_R = \varphi(w)$.

* $w = c$ for some $c \in \Sigma_{\text{int}}$. Then $\alpha(\varphi'(w)) = \alpha(\rho(c)) = \varphi(c) = \varphi(w)$.

* $w = aw'b$ for some $a \in \Sigma_{\text{call}}, b \in \Sigma_{\text{ret}}$ and $w' \in \Sigma^\Delta$. Then

$$ 
\begin{align*}
\alpha(\varphi'(w)) &= \alpha(\varphi'(\text{ext}_{a,b}(w'))) \\
&= \alpha(\psi'(\text{ext}_{a,b})(\varphi'(w'))) \\
&= \beta(\psi'(\text{ext}_{a,b}))(\alpha(\varphi'(w'))) \\
&\stackrel{\text{IH}}{=} \beta(\sigma(\text{ext}_{a,b}))(\varphi(w')) \\
&= \psi(\text{ext}_{a,b})(\varphi(w')) \\
&= \varphi(\text{ext}_{a,b}(w')) \\
&= \varphi(w) .
\end{align*}
$$

* $w = uv$ for some $u, v \in \Sigma^\Delta \setminus \{\varepsilon\}$. Then

$$ \alpha(\varphi'(w)) = \alpha(\varphi'(u))\alpha(\varphi'(v)) \stackrel{\text{IH}}{=} \varphi(u)\varphi(v) = \varphi(w) . $$
Therefore, $\varphi'^{-1}(\alpha^{-1}(F)) = L$, which implies that $(S, P)$ recognizes $L$. $\square$

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

Next, we show that any language recognized by an Ext-algebra is also recognized by one of its sub-Ext-algebras via a surjective morphism.

**Lemma 3.15.** Let $(\varphi, \psi): (\Sigma^\Delta, \mathcal{O}(\Sigma^\Delta)) \to (R, O)$ be a morphism and let $L \subseteq \Sigma^\Delta$ be a language recognized by $(R, O)$ via $(\varphi, \psi)$. Then $(\varphi(\Sigma^\Delta), \psi(\mathcal{O}(\Sigma^\Delta))|_{\varphi(\Sigma^\Delta)})$ is a sub-Ext-algebra of $(R, O)$ recognizing $L$ via the surjective morphism $(\varphi, \psi')$ where $\psi'(\mathrm{ext}_{u,v}) = \psi(\mathrm{ext}_{u,v})|_{\varphi(\Sigma^\Delta)}$ for all $\mathrm{ext}_{u,v} \in \mathcal{O}(\Sigma^\Delta)$.

*Proof.* Since $(R, O)$ recognizes $L$ via $(\varphi, \psi)$, this means that there exists $F \subseteq R$ such that $\varphi^{-1}(F) = L$. We have that $\varphi(\Sigma^\Delta)$ is a submonoid of $R$ and $\psi(\mathcal{O}(\Sigma^\Delta))$ is a submonoid of $O$. Observe that for all $e \in \psi(\mathcal{O}(\Sigma^\Delta))$ and $r \in \varphi(\Sigma^\Delta)$, we have

$$e(r) = \psi(\mathrm{ext}_{u,v})(\varphi(w)) = \varphi(uwv) \in \varphi(\Sigma^\Delta)$$

because $\psi(\mathrm{ext}_{u,v}) = e$ for $\mathrm{ext}_{u,v} \in \mathcal{O}(\Sigma^\Delta)$ and $r = \varphi(w)$ for $w \in \Sigma^\Delta$. Moreover, for all $e, f \in \psi(\mathcal{O}(\Sigma^\Delta))$, it holds that $e|_{\varphi(\Sigma^\Delta)} \circ f|_{\varphi(\Sigma^\Delta)} = (e \circ f)|_{\varphi(\Sigma^\Delta)}$. Therefore, $\psi(\mathcal{O}(\Sigma^\Delta))|_{\varphi(\Sigma^\Delta)}$ is a sub-monoid of $\varphi(\Sigma^\Delta)\varphi(\Sigma^\Delta)$. In addition, for each $r \in \varphi(\Sigma^\Delta)$, we have that $r = \varphi(w)$ for some $w \in \Sigma^\Delta$ and thus that

$$\mathrm{left}_r = \mathrm{left}_{\varphi(w)} = \psi(\mathrm{left}_w)|_{\varphi(\Sigma^\Delta)} = \psi(\mathrm{ext}_{w,\varepsilon})|_{\varphi(\Sigma^\Delta)}$$

as well as right$_r = \psi(\mathrm{ext}_{\varepsilon,w})|_{\varphi(\Sigma^\Delta)}$. Thus, $(\varphi(\Sigma^\Delta), \psi(\mathcal{O}(\Sigma^\Delta))|_{\varphi(\Sigma^\Delta)})$ is a sub-Ext-algebra of $(R, O)$. It is clear that $\varphi$ is a surjective monoid morphism from $\Sigma^\Delta$ to $\varphi(\Sigma^\Delta)$. Further,

$$\begin{align*}
\psi'(\mathrm{ext}_{u,v}) \circ \psi'(\mathrm{ext}_{u',v'}) &= \psi(\mathrm{ext}_{u,v})|_{\varphi(\Sigma^\Delta)} \circ \psi(\mathrm{ext}_{u',v'})|_{\varphi(\Sigma^\Delta)} \\
&= (\psi(\mathrm{ext}_{u,v}) \circ \psi(\mathrm{ext}_{u',v'}))|_{\varphi(\Sigma^\Delta)} \\
&= \psi(\mathrm{ext}_{u,v} \circ \mathrm{ext}_{u',v'})|_{\varphi(\Sigma^\Delta)} \\
&= \psi'(\mathrm{ext}_{u,v} \circ \mathrm{ext}_{u',v'})
\end{align*}$$

for all $\mathrm{ext}_{u,v}, \mathrm{ext}_{u',v'} \in \mathcal{O}(\Sigma^\Delta)$, hence since $\psi'(\mathrm{ext}_{\varepsilon,\varepsilon}) = 1_O|_{\varphi(\Sigma^\Delta)}$, it follows that $\psi'$ is a surjective monoid morphism from $\mathcal{O}(\Sigma^\Delta)$ to $\psi(\mathcal{O}(\Sigma^\Delta))|_{\varphi(\Sigma^\Delta)}$. Moreover, we have

* $\psi'(\mathrm{ext}_{u,v})(\varphi(w)) = \psi(\mathrm{ext}_{u,v})|_{\varphi(\Sigma^\Delta)}(\varphi(w)) = \psi(\mathrm{ext}_{u,v})(\varphi(w)) = \varphi(\mathrm{ext}_{u,v}(w))$ for all $\mathrm{ext}_{u,v} \in \mathcal{O}(\Sigma^\Delta)$ and $w \in \Sigma^\Delta$;

* $\psi'(\mathrm{left}_w) = \psi(\mathrm{ext}_{w,\varepsilon})|_{\varphi(\Sigma^\Delta)} = \mathrm{left}_{\varphi(w)}$ and $\psi'(\mathrm{right}_w) = \mathrm{right}_{\varphi(w)}$ for all $w \in \Sigma^\Delta$.

Therefore, $(\varphi, \psi')$ is a surjective morphism recognizing $L$. $\square$

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

The following lemma states that a language is recognized by an Ext-algebra via a surjective morphism if, and only if, the syntactic morphism of the language factors through the former morphism.

**Lemma 3.16.** Let $(\varphi, \psi): (\Sigma^\Delta, \mathcal{O}(\Sigma^\Delta)) \to (R, O)$ be a surjective morphism, let $L \subseteq \Sigma^\Delta$ and let $(\varphi_L, \psi_L): (\Sigma^\Delta, \mathcal{O}(\Sigma^\Delta)) \to (R_L, O_L)$ be the syntactic morphism of $L$. Then $(R, O)$ recognizes $L$ via $(\varphi, \psi)$ if and only if there is a surjective morphism $(\alpha, \beta): (R, O) \to (R_L, O_L)$ such that $\varphi_L = \alpha \circ \varphi$ (we say that $(\varphi_L, \psi_L)$ factors through $(\varphi, \psi)$).
Proof. Assume first that there is a surjective morphism $(\alpha, \beta): (R, O) \to (R_L, O_L)$ such that $\varphi_L = \alpha \circ \varphi$. Then

$$ \varphi^{-1}(\alpha^{-1}(\varphi(L))) = (\alpha \circ \varphi)^{-1}(\varphi_L(L)) = \varphi_L^{-1}(\varphi_L(L)) = L, $$

hence $(R, O)$ recognizes $L$ via $(\varphi, \psi)$.

Assume now that $(R, O)$ recognizes $L$ via $(\varphi, \psi)$. This means that there exists $F \subseteq R$ satisfying $\varphi^{-1}(F) = L$. Take $w, w' \in \Sigma^\Delta$ such that $\varphi(w) = \varphi(w')$. Then, given any $e \in \mathcal{O}(\Sigma^\Delta)$, we have that

$$ \varphi(e(w)) = \psi(e)(\varphi(w)) = \psi(e)(\varphi(w')) = \varphi(e(w')). $$

Therefore, since $\varphi^{-1}(F) = L$, it holds that $w \sim_L w'$, that is, $\varphi_L(w) = \varphi_L(w')$.

Take $\mathrm{ext}_{u,v}, \mathrm{ext}_{u',v'} \in \mathcal{O}(\Sigma^\Delta)$ such that $\psi(\mathrm{ext}_{u,v}) = \psi(\mathrm{ext}_{u',v'})$. Then, for each $w \in \Sigma^\Delta$, we have that

$$ \varphi(\mathrm{ext}_{u,v}(w)) = \psi(\mathrm{ext}_{u,v})(\varphi(w)) = \psi(\mathrm{ext}_{u',v'})(\varphi(w)) = \varphi(\mathrm{ext}_{u',v'}(w)), $$

that is, $\mathrm{ext}_{u,v}(w) \sim_L \mathrm{ext}_{u',v'}(w)$. Hence, $\psi_L(\mathrm{ext}_{u,v}) = \psi_L(\mathrm{ext}_{u',v'})$.

We can now define the functions $\alpha: R \to R_L$ and $\beta: O \to O_L$ such that $\alpha(\varphi(w)) = \varphi_L(w)$ for all $w \in \Sigma^\Delta$ and $\beta(\psi(\mathrm{ext}_{u,v})) = \psi_L(\mathrm{ext}_{u,v})$ for all $\mathrm{ext}_{u,v} \in \mathcal{O}(\Sigma^\Delta)$: those are well-defined by surjectivity of $(\varphi, \psi)$ and what we have proven just above. Since $(\varphi_L, \psi_L)$ is a surjective morphism from $(\Sigma^\Delta, \mathcal{O}(\Sigma^\Delta))$ to $(R_L, O_L)$, we can easily prove that $(\alpha, \beta)$ is a surjective morphism from $(R, O)$ to $(R_L, O_L)$ that does of course satisfy $\varphi_L = \alpha \circ \varphi$. $\square$

The following proposition shows that the syntactic Ext-algebra of a given language of well-matched words is the least Ext-algebra recognizing this language.

**Proposition 3.17.** An Ext-algebra $(R, O)$ recognizes a language $L \subseteq \Sigma^\Delta$ if, and only if, its syntactic Ext-algebra $(R_L, O_L)$ divides $(R, O)$.

Proof. Let $(R, O)$ be an Ext-algebra and let $L \subseteq \Sigma^\Delta$ be a language. Consider also its syntactic Ext-algebra $(R_L, O_L)$ and its syntactic morphism $(\varphi_L, \psi_L)$.

**Implication from right to left.** Assume that the syntactic Ext-algebra $(R_L, O_L)$ of $L$ divides $(R, O)$. We have that $(R_L, O_L)$ recognizes $L$ and we then use Lemma 3.14 to conclude that $(R, O)$ does also recognize $L$.

**Implication from left to right.** Assume that $(R, O)$ recognizes $L$ through a morphism $(\varphi, \psi): (\Sigma^\Delta, \mathcal{O}(\Sigma^\Delta)) \to (R, O)$. By Lemma 3.15, we have that $(\varphi(\Sigma^\Delta), \psi(\mathcal{O}(\Sigma^\Delta))|_{\varphi(\Sigma^\Delta)}) = (R', O')$ is a sub-Ext-algebra of $(R, O)$ recognizing $L$ via the surjective morphism $(\varphi, \psi')$ where $\psi'(\mathrm{ext}_{u,v}) = \psi(\mathrm{ext}_{u,v})|_{\varphi(\Sigma^\Delta)}$ for all $\mathrm{ext}_{u,v} \in \mathcal{O}(\Sigma^\Delta)$. Then, by Lemma 3.16, there exists a surjective morphism $(\alpha, \beta): (R', O') \to (R_L, O_L)$ such that $\varphi_L = \alpha \circ \varphi$. Thus, we have that $(R_L, O_L)$ divides $(R, O)$. $\square$

We say that an Ext-algebra $(R, O)$ is *finite* whenever $R$ is finite (which is the case if and only if $O$ is finite). The following theorem establishes the equivalence between visibly pushdown languages and languages recognizable by finite Ext-algebras. Its proof provides effective translations from DVPAs to Ext-algebras and vice versa.

**Theorem 3.18.** A language $L \subseteq \Sigma^\Delta$ is a VPL if, and only if, it is recognized by a finite Ext-algebra.

Proof. Let $L \subseteq \Sigma^\Delta$ be a language. Before we prove the theorem we have the following claim, which can be easily proven by induction on $|u|$ and structural induction on $w$, respectively.
**Claim.** Let $A = (Q, \Sigma, \Gamma, \delta, q_0, F, \perp)$ be a DVPA. We denote by $\pi_Q$ the projection of $Q \times \Gamma^*$ on $Q$ and by $\pi_{\Gamma^*}$ the projection of $Q \times \Gamma^*$ on $\Gamma^*$. It holds that $L(A) \subseteq \Sigma^\Delta$ and additionally we have that

$$ \hat{\delta}(q, uv, \sigma) = \hat{\delta}(\pi_Q(\hat{\delta}(q, u, \sigma)), v, \pi_{\Gamma^*}(\hat{\delta}(q, u, \sigma))) $$

and

$$ \hat{\delta}(q, w, \alpha\sigma) = (\pi_Q(\hat{\delta}(q, w, \alpha)), \alpha\sigma) $$

for all $q \in Q$, $u, v \in \Sigma^*$, $\sigma \in \Gamma^*$, $w \in \Sigma^\Delta$ and $\alpha \in \Gamma$.

**Implication from left to right.** Assume that $L$ is a VPL. This means there exists a DVPA $A = (Q, \Sigma, \Gamma, \delta, q_0, F, \perp)$ such that $L(A) = L$. Consider the operation $*$ on $R = Q^{Q \times \Gamma}$ defined so that for all $f, g \in R$, we have $f * g(q, \alpha) = g(f(q, \alpha), \alpha)$ for all $q \in Q$ and $\alpha \in \Gamma$. Observe that for all $f, g, h \in Q^{Q \times \Gamma}$, we have

$$ (f * g) * h(q, \alpha) = h(f * g(q, \alpha), \alpha) = h(g(f(q, \alpha), \alpha), \alpha) = g * h(f(q, \alpha), \alpha) = f * (g * h)(q, \alpha) $$

for all $q \in Q$ and $\alpha \in \Gamma$. Thus $*$ is associative and since it also has $i \in R$ with $i(q, \alpha) = q$ for all $q \in Q$ and $\alpha \in \Gamma$ as an identity, we have that $R = Q^{Q \times \Gamma}$ with operation $*$ forms a monoid. Take $O$ to be the monoid $R^R$ (for composition). Since $O$ clearly contains the functions left$_r$ and right$_r$, for all $r \in R$, it follows that $(R, O)$ is a finite Ext-algebra. We now prove that it recognizes $L$. For each $w \in \Sigma^\Delta$, define $f_w \in R$ by $f_w(q, \alpha) = \pi_Q(\hat{\delta}(q, w, \alpha))$ for all $q \in Q$ and $\alpha \in \Gamma$. Let us consider the unique morphism $(\varphi, \psi): (\Sigma^\Delta, \mathcal{O}(\Sigma^\Delta)) \to (R, O)$, given by Proposition 3.7, such that for each $c \in \Sigma_{\text{int}}$, we have $\varphi(c) = f_c$ and for each $a \in \Sigma_{\text{call}}$, $b \in \Sigma_{\text{ret}}$, we have that $\psi(\text{ext}_{a,b})$ sends any $f \in R$ to $g \in R$ satisfying that $g(q, \alpha) = \pi_Q(\delta(f(p, \beta), b, \beta))$ with $\delta(q, a, \alpha) = (p, \beta\alpha)$ for all $q \in Q$ and $\alpha \in \Gamma$. We claim that for all $w \in \Sigma^\Delta$, we have that $\varphi(w) = f_w$. We prove it by induction on $w$.

* $w = \varepsilon$. Then $\varphi(w) = i = f_w$.

* $w = c$ for some $c \in \Sigma_{\text{int}}$. Then $\varphi(w) = f_c = f_w$.

* $w = aw'b$ for some $a \in \Sigma_{\text{call}}$, $b \in \Sigma_{\text{ret}}$ and $w' \in \Sigma^\Delta$. Then

$$ \varphi(w) = \varphi(\text{ext}_{a,b}(w')) = \psi(\text{ext}_{a,b})(\varphi(w')) \stackrel{\text{IIH}}{=} \psi(\text{ext}_{a,b})(f_{w'}) . $$

So $\varphi(w) = g$ such that for all $q \in Q$ and $\alpha \in \Gamma$, if we set $\delta(q, a, \alpha) = (p, \beta\alpha)$, we have, recalling that $\hat{\delta}$ extends $\delta$,

$$ \begin{aligned} g(q, \alpha) &= \pi_Q(\delta(f_{w'}(p, \beta), b, \beta)) \\ &= \pi_Q(\delta(\pi_Q(\hat{\delta}(p, w', \beta)), b, \beta)) \\ &= \pi_Q(\hat{\delta}(\pi_Q(\hat{\delta}(p, w', \beta)), b, \beta)) \\ &= \pi_Q(\hat{\delta}(\pi_Q(\hat{\delta}(q, aw', \alpha)), b, \pi_{\Gamma^*}(\hat{\delta}(q, aw', \alpha)))) \\ &= \pi_Q(\hat{\delta}(q, aw'b, \alpha)) \\ &= f_{aw'b}(q, \alpha) \\ &= f_w(q, \alpha) . \end{aligned} $$

Thus $\varphi(w) = f_w$.
• $w = uv$ for some $u, v \in \Sigma^\Delta \setminus \{\varepsilon\}$. Then $\varphi(w) = \varphi(u) * \varphi(v) \stackrel{\text{IH}}{=} f_u * f_v$. But

$$
\begin{align*}
f_u * f_v(q, \alpha) &= f_v(f_u(q, \alpha), \alpha) \\
&= f_v(\pi_Q(\hat{\delta}(q, u, \alpha)), \alpha) \\
&= \pi_Q(\hat{\delta}(\pi_Q(\hat{\delta}(q, u, \alpha)), v, \alpha)) \\
&= \pi_Q(\hat{\delta}(\pi_Q(\hat{\delta}(q, u, \alpha)), v, \pi_{\Gamma^*}(\hat{\delta}(q, u, \alpha)))) \\
&= \pi_Q(\hat{\delta}(q, uv, \alpha)) \\
&= f_{uv}(q, \alpha)
\end{align*}
$$

for all $q \in Q$ and $\alpha \in \Gamma$. Therefore $\varphi(w) = f_w$.

Finally, set $P = \{f \in R \mid f(q_0, \perp) \in F\}$. It holds that

$$
\begin{align*}
\varphi^{-1}(P) &= \{w \in \Sigma^{\Delta} \mid f_w(q_0, \perp) \in F\} \\
&= \{w \in \Sigma^{\Delta} \mid \pi_Q(\hat{\delta}(q_0, w, \perp)) \in F\} \\
&= \{w \in \Sigma^{\Delta} \mid \hat{\delta}(q_0, w, \perp) \in F \times \{\perp\}\} \\
&= L(A) \\
&= L.
\end{align*}
$$

Therefore, $(R, O)$ recognizes $L$.

**Implication from right to left.** Assume there exists a finite Ext-algebra $(R, O)$ that recognizes $L$. This means that there exists a morphism $(\varphi, \psi): (\Sigma^\Delta, \mathcal{O}(\Sigma^\Delta)) \to (R, O)$ such that $L = \varphi^{-1}(F)$ for some $F \subseteq R$. Let us now define the DVPA

$A = (Q, \Sigma, \Gamma, \delta, 1, F, \perp),$

where $Q = R$, $1 = 1_R$, $\Gamma = R \times \Sigma_{\text{call}} \cup \{\perp\}$, and

$$
\delta(r, a, \alpha) = \begin{cases} (1, (r, a)\alpha) & \text{if } a \in \Sigma_{\text{call}} \\ (s\psi(\text{ext}_{b,a})(r), \varepsilon) & \text{if } a \in \Sigma_{\text{ret}} \text{ and } \alpha = (s, b) \in R \times \Sigma_{\text{call}} \\ (r, \varepsilon) & \text{if } a \in \Sigma_{\text{ret}} \text{ and } \alpha = \perp \\ (r\varphi(c), \alpha) & \text{if } a \in \Sigma_{\text{int}} \end{cases}
$$

for all $r \in R$, $a \in \Sigma$ and $\alpha \in \Gamma$. We prove that $\hat{\delta}(r, w, \sigma) = (r\varphi(w), \sigma)$ for all $r \in R$, $w \in \Sigma^\Delta$ and $\sigma \in \Gamma^* \perp$ by induction on $w$.

• $w = \varepsilon$. Then $\hat{\delta}(r, w, \sigma) = (r, \sigma) = (r\varphi(w), \sigma)$.

• $w = c$ for some $c \in \Sigma_{\text{int}}$. Then $\hat{\delta}(r, w, \sigma) = (r\varphi(c), \sigma) = (r\varphi(w), \sigma)$.
• $w = aw'b$ for some $a \in \Sigma_{\text{call}}$, $b \in \Sigma_{\text{ret}}$ and $w' \in \Sigma^{\Delta}$. Then

$$
\begin{align*}
\hat{\delta}(r, w, \sigma) &= \hat{\delta}(1, w'b, (r, a)\sigma) \\
&= \hat{\delta}(\pi_Q(1, w', (r, a)\sigma), b, \pi_{\Gamma^*}(1, w', (r, a)\sigma)) \\
&\stackrel{\text{IH}}{=} \hat{\delta}(\varphi(w'), b, (r, a)\sigma) \\
&= (r\psi(\text{ext}_{a,b})(\varphi(w'))), \sigma) \\
&= (r\varphi(w), \sigma).
\end{align*}
$$

• $w = uv$ for some $u, v \in \Sigma^{\Delta} \setminus \{\epsilon\}$. Then

$$
\begin{align*}
\hat{\delta}(r, w, \sigma) &= \hat{\delta}(\pi_Q(\hat{\delta}(r, u, \sigma)), v, \pi_{\Gamma^*}(\hat{\delta}(r, u, \sigma))) \\
&\stackrel{\text{IH}}{=} \hat{\delta}(r\varphi(u), v, \sigma) \\
&\stackrel{\text{IH}}{=} (r\varphi(u)\varphi(v), \sigma) \\
&= (r\varphi(w), \sigma).
\end{align*}
$$

Hence,

$$
\begin{align*}
L(A) &= \{w \in \Sigma^{\Delta} \mid \hat{\delta}(1, w, \perp) \in F \times \{\perp\}\} \\
&= \{w \in \Sigma^{\Delta} \mid \pi_Q(\hat{\delta}(1, w, \perp)) \in F\} \\
&= \{w \in \Sigma^{\Delta} \mid \varphi(w) \in F\} \\
&= \varphi^{-1}(F) = L.
\end{align*}
$$

Therefore, $L$ is a VPL.

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

4 (Weak) length-synchronicity, nesting depth, and quasi-aperiodicity

For the rest of this section let us fix a visibly pushdown alphabet $\Sigma$, a finite Ext-algebra $(R, O)$ and consider a morphism $(\varphi, \psi) : (\Sigma^\Delta, \mathcal{O}(\Sigma^\Delta)) \to (R, O)$. Suitably adjusting the pumping lemma for context-free language we introduce a pumping lemma for Ext-algebra morphisms in Section 4.1. In Section 4.2 we extend the notions of weak length-synchronicity and length-synchronicity to Ext-algebras morphisms and to visibly pushdown languages. It is shown that for languages generated by vertically visibly pushdown grammars, (weak) length-synchronicity of the relation of the generating grammar coincides with (weak) length-synchronicity of language. We concern ourselves with the nesting depth of visibly pushdown languages in Section 4.3. Finally in Section 4.4 we introduce quasi-aperiodicity of Ext-algebra morphisms and prove that a VPL is quasi-counterfree if, and only if, its syntactic morphism is quasi-aperiodic.

4.1 A pumping lemma for Ext-algebra morphisms

The following is an adaption of the pumping lemma for context-free languages to Ext-algebra
morphisms. It states that if $uv \in \Sigma^\Delta$ and $u$ (resp. $v$) contains a well-matched factor that is
sufficiently long, we can pump certain infixes of $u$ (resp. $v$): thus, one can find longer and longer
words $u_1, u_2, \dots$ (resp. $v_1, v_2, \dots$) such that $u_1v, u_2v, \dots \in \Sigma^\Delta$ (resp. $uv_1, uv_2, \dots \in \Sigma^\Delta$) and the
morphism $\psi$ sends $\text{ext}_{u,v}$ to the same element in $O$ as $\text{ext}_{u_i,v_i}$ (resp. as $\text{ext}_{u,v_i}$).
**Lemma 4.1** (Pumping Lemma). There exists $n \in \mathbb{N}_{>0}$ such that for all $\text{ext}_{u,v} \in \mathcal{O}(\Sigma^\Delta)$ we have:

* If there exists a factor $w \in \Sigma^\Delta$ of $u$ satisfying $|w| \ge n$, then $u = \text{sxzyt}$ with $s, x, z, y, t \in \Sigma^*$ such that $|xy| \ge 1$, $|xzy| \le n$ and for all $i \in \mathbb{N}$, $sx^i zy^i tv \in \Sigma^\Delta$ and $\psi(\text{ext}_{u,v}) = \psi(\text{ext}_{sx^i zy^i t, v})$.

* If there exists a factor $w \in \Sigma^\Delta$ of $v$ satisfying $|w| \ge n$, then $v = \text{sxzyt}$ with $s, x, z, y, t \in \Sigma^*$ such that $|xy| \ge 1$, $|xzy| \le n$ and for all $i \in \mathbb{N}$, $usx^i zy^i t \in \Sigma^\Delta$ and $\psi(\text{ext}_{u,v}) = \psi(\text{ext}_{u, sx^i zy^i t})$.

*Proof.* For each $r \in \mathbb{R}$, let $n_r \in \mathbb{N}_{>0}$ be the pumping constant for the context-free language $\varphi^{-1}(r)$: it is a VPL and hence a context-free language by Theorem 3.18. We set $n = \max_{r \in \mathbb{R}} n_r$. Let $\text{ext}_{u,v} \in \mathcal{O}(\Sigma^\Delta)$ be such that there exists a factor $w \in \Sigma^\Delta$ of $u$ satisfying $|w| \ge n$. Let

$$ \text{ext}_{u,v} = \text{ext}_{x_1, y_1} \circ \text{ext}_{a_1, b_1} \circ \dots \circ \text{ext}_{x_{h-1}, y_{h-1}} \circ \text{ext}_{a_{h-1}, b_{h-1}} \circ \text{ext}_{x_h, y_h} $$

be the stair factorization of $\text{ext}_{u,v}$ provided by Lemma 3.6. Since no factor of $u$ spanning one of the $a_j$'s in the factorization can be well-matched, there must exist some $j \in [1, h]$ satisfying $|x_j| \ge n$, so that if we set $u' = x_1 a_1 \cdots x_{j-1} a_{j-1}$, $v' = b_{j-1} y_{j-1} \cdots b_1 y_1$, $u'' = a_j x_{j+1} \cdots a_{h-1} x_h$ and $v'' = y_h b_{h-1} \cdots y_{j+1} b_j y_j$, we have $u'v', u''v'' \in \Sigma^\Delta$ and $\text{ext}_{u,v} = \text{ext}_{u',v'} \circ \text{ext}_{x_j, \varepsilon} \circ \text{ext}_{u'',v''}$. By the pumping lemma for context-free languages we have $x_j = x'xzyy'$ with $x', x, z, y, y' \in \Sigma^*$ such that $|xy| \ge 1$, $|xzy| \le n$ and for all $i \in \mathbb{N}$, $x'x^i zy^i y' \in \Sigma^\Delta$ and $\varphi(x_j) = \varphi(x'x^i zy^i y')$. This implies that if we set $s = u'x'$ and $t = y'u''$, then for all $i \in \mathbb{N}$, we have $sx^i zy^i tv = \text{ext}_{u',v'} \circ \text{ext}_{x'x^i zy^i y', \varepsilon} \circ \text{ext}_{u'',v''}(\varepsilon) \in \Sigma^\Delta$ and

$$ \begin{aligned} \psi(\text{ext}_{u,v}) &= \psi(\text{ext}_{u',v'}) \circ \text{left}_{\varphi(x_j)} \circ \psi(\text{ext}_{u'',v''}) \\ &= \psi(\text{ext}_{u',v'}) \circ \text{left}_{\varphi(x'x^i zy^i y')} \circ \psi(\text{ext}_{u'',v''}) \\ &= \psi(\text{ext}_{u',v'}) \circ \psi(\text{ext}_{x'x^i zy^i y', \varepsilon}) \circ \psi(\text{ext}_{u'',v''}) \\ &= \psi(\text{ext}_{sx^i zy^i t, v}) . \end{aligned} $$

We handle the case where for $\text{ext}_{u,v} \in \mathcal{O}(\Sigma^\Delta)$ there exists a factor $w \in \Sigma^\Delta$ of $v$ such that $|w| \ge n$ symmetrically. $\square$

## 4.2 Weak length-synchronicity and length-synchronicity

In this section we introduce the notions of weak length-synchronicity and length-synchronicity for Ext-algebra morphisms and visibly pushdown languages. Before we do that, let us give some motivation how TC$^0$-hardness can be proven if the syntactic morphism maps certain $\text{ext}_{u,v}$, $\text{ext}_{u',v}$ with $|u| \ne |u'|$ to particular idempotents. For these we require the following notion of reachability.

For $F \subseteq \mathbb{R}$ we say that an element $r \in \mathbb{R}$ is F-reachable if $e(r) \in F$ for some $e \in O$. We say $e \in O$ is F-reachable if $e(r)$ is F-reachable for some $r \in \mathbb{R}$. Although we will mainly study F-reachable elements over finite Ext-algebras we remark that the notion of F-reachability is defined over any Ext-algebra, in particular over $(\Sigma^\Delta, \mathcal{O}(\Sigma^\Delta))$. Fix any VPL $L$, its syntactic Ext-algebra $(R_L, O_L)$ along with its syntactic morphism $(\varphi_L, \psi_L)$. Assume some idempotent $e \in O_L$ that is $\varphi(L)$-reachable.

We claim that if $\psi_L(\text{ext}_{u,v}) = \psi_L(\text{ext}_{u',v}) = e$ and $\Delta(u), \Delta(u') > 0$ for some $\text{ext}_{u,v}, \text{ext}_{u',v} \in \mathcal{O}(\Sigma^\Delta)$ with $|u| \ne |u'|$, then $L$ is TC$^0$-hard. We remark that we must have $\Delta(u) = \Delta(u')$. Exploiting the fact that $|u| \ne |u'|$ we give a constant-depth reduction from the TC$^0$-complete language EQUALITY to $L$.

Since $\psi_L(\text{ext}_{u,v})$ is $\varphi_L(L)$-reachable, we can fix some $x, y, z \in \Sigma^*$ such that $xuyvz \in L$. Given a word $w \in \{0, 1\}^*$ of length $2n$ (binary words of odd length can directly be rejected) we map it to
$xh(w)zv^{n \cdot (|u|+|u'|)}y$, where $h: \{0,1\}^* \to \Sigma^*$ is the length-multiplying morphism satisfying $h(0) = u^{|u'|}$ and $h(1) = u^{|u|}$: one can prove that $w \in \text{EQUALITY}$ if, and only if, $h(w)v^{n \cdot (|u|+|u'|)} \in \Sigma^\Delta$ if, and only if, $xh(w)zv^{n \cdot (|u|+|u'|)}y \in L$.

Dually, one can show that $L$ is $\mathcal{TC}^0$-hard in case $\psi_L(\text{ext}_{u,v}) = \psi_L(\text{ext}_{u,v'}) = e$ and $\Delta(u) > 0$ for some $\text{ext}_{u,v}$, $\text{ext}_{u,v'} \in \mathcal{O}(\Sigma^\Delta)$ with $|v| \neq |v'|$.

The following definition of weak length-synchronicity captures the situation when such idempotents do not exist — it adapts the notion of weak length-synchronicity of sets of contexts, given in Definition 2.3, to morphisms and VPLs, respectively. Recall that $\mathcal{R} \subseteq \text{Con}(\Sigma)$ is defined to be weakly length-synchronous if $u = u'$ implies $|v| = |v'|$ and $v = v'$ implies $|u| = |u'|$ for all $(u, v), (u', v') \in \mathcal{R}$ satisfying $\Delta(u), \Delta(u') > 0$.

**Definition 4.2.** For all $e \in O$ define the sets of contexts $\mathcal{R}_e$ and $\mathcal{U}_e$ as follows:

$$ \mathcal{R}_e = \{(u, v) \in \text{Con}(\Sigma) \mid \psi(\text{ext}_{u,v}) = e\} \quad \text{and} \quad \mathcal{U}_e = \{(u, v) \in \text{Con}(\Sigma) \mid e \circ \psi(\text{ext}_{u,v}) = e\} $$

**Definition 4.3 (Weak Length-Synchronicity).** The morphism $(\varphi, \psi): (\Sigma^\Delta, \mathcal{O}(\Sigma^\Delta)) \to (R, O)$ is $F$-weakly-length-synchronous (where $F \subseteq R$) if for all $F$-reachable idempotents $e \in O$ the set of contexts $\mathcal{R}_e$ is weakly length-synchronous. We call a VPL $L \subseteq \Sigma^\Delta$ weakly length-synchronous if its syntactic morphism $(\varphi_L, \psi_L)$ is $\varphi_L(L)$-weakly-length-synchronous.

In fact, $F$-weak-length-synchronicity actually implies weak length-synchronicity of the set of contexts associated to any subsemigroup of $F$-reachable elements.

**Lemma 4.4.** For all $F \subseteq R$ and subsemigroup $P$ of $O$, if all elements in $P$ are $F$-reachable and $(\varphi, \psi)$ is $F$-weakly-length-synchronous, then $\bigcup_{e \in P} \mathcal{R}_e$ is weakly length-synchronous.

*Proof.* Let $F \subseteq R$ and $P$ be a subsemigroup of $O$. Assume all elements in $P$ are $F$-reachable and $(\varphi, \psi)$ is $F$-weakly-length-synchronous.

Let $(u, v), (u', v) \in \text{Con}(\Sigma)$ be such that $\Delta(u), \Delta(u') > 0$ and $\psi(\text{ext}_{u,v}), \psi(\text{ext}_{u',v}) \in P$. Set $e = \psi(\text{ext}_{u,v})$ and $f = \psi(\text{ext}_{u',v})$. By hypothesis, given $\omega \in \mathbb{N}_{>0}$ the idempotent power of $O$, we have $(e^\omega f^\omega)^\omega \in P$, hence $(e^\omega f^\omega)^\omega$ is an $F$-reachable idempotent and thus $\mathcal{R}_{(e^\omega f^\omega)^\omega}$ is weakly length-synchronous. But

$$ \psi(\text{ext}_{(u^{2 \cdot \omega} u'^{\omega})\omega, v^{3 \cdot \omega} 2}) = (e^\omega f^\omega)^\omega = \psi(\text{ext}_{(u^\omega u'^{2 \cdot \omega})\omega, v^{3 \cdot \omega} 2}) $$

so since $\Delta((u^{2 \cdot \omega} u'^{\omega})\omega) = \Delta((u^\omega u'^{2 \cdot \omega})\omega) > 0$, we obtain

$$ \omega \cdot (2 \cdot \omega \cdot |u| + \omega \cdot |u'|) = \omega \cdot (\omega \cdot |u| + 2 \cdot \omega \cdot |u'|) $$

$$ \iff 2 \cdot |u| + |u'| = |u| + 2 \cdot |u'| $$

$$ \iff |u| = |u'|. $$

In the same way, one can prove that for all $(u, v), (u, v') \in \text{Con}(\Sigma)$ such that $\Delta(u) > 0$ and $\psi(\text{ext}_{u,v}), \psi(\text{ext}_{u,v'}) \in P$, we have $|v| = |v'|$.

Therefore, $\bigcup_{e \in P} \mathcal{R}_e$ is weakly length-synchronous. $\square$

Instead of considering those pairs $(u, v)$ such that $\text{ext}_{u,v}$ is being mapped to an $F$-reachable idempotent, the following characterization of weak length-synchronicity consider pairs $(u, v)$ such that $\text{ext}_{u,v}$ is being mapped to an element that behaves neutrally with respect to right multiplication with an $F$-reachable element that is not necessarily idempotent.
**Proposition 4.5.** For all $F \subseteq R$ we have that $(\varphi, \psi)$ is $F$-weakly-length-synchronous if, and only if, for all $F$-reachable $e \in O$ the set of contexts $\mathcal{U}_e$ is weakly length-synchronous.

*Proof.* Let $F \subseteq R$.

If $\mathcal{U}_e = \{(u, v) \in \text{Con}(\Sigma) \mid e \circ \psi(\text{ext}_{u,v}) = e\}$ is weakly length-synchronous for all $F$-reachable $e \in O$, then in particular the set of contexts $\mathcal{R}_e = \{(u, v) \in \text{Con}(\Sigma) \mid \psi(\text{ext}_{u,v}) = e\}$ is weakly length-synchronous for all $F$-reachable idempotents $e \in O$.

Conversely, assume that $(\varphi, \psi)$ is $F$-weakly-length-synchronous. Fix any $F$-reachable $e \in O$. We need to prove that $\mathcal{U}_e$ is weakly length-synchronous. It is clear that $P = \{f \in O \mid e \circ f = e\}$ forms a subsemigroup of $O$ whose elements are all $F$-reachable, by $F$-reachability of $e$. Therefore, by Lemma 4.4, $\bigcup_{f \in P} \mathcal{R}_f = \mathcal{U}_e$ is weakly length-synchronous. $\square$

Using Lemma 4.1 and Proposition 4.5, the following proposition follows immediately.

**Proposition 4.6.** Let $n$ be the pumping constant from Lemma 4.1, let $F \subseteq R$, let $e \in O$ be $F$-reachable, and let $\text{ext}_{u,v}$ be such that $\Delta(u) > 0$ and $e \circ \psi(\text{ext}_{u,v}) = e$. If $(\varphi, \psi)$ is $F$-weakly-length-synchronous, then the stair factorization

$$ \text{ext}_{u,v} = \text{ext}_{x_1,y_1} \circ \text{ext}_{a_1,b_1} \circ \dots \circ \text{ext}_{x_{h-1},y_{h-1}} \circ \text{ext}_{a_{h-1},b_{h-1}} \circ \text{ext}_{x_h,y_h} $$

satisfies $|x_i|, |y_i| \le n$ for all $i \in [1, h]$,

As above, the following definition adapts the notion of length-synchronicity of sets of contexts, given in Definition 2.3, to Ext-algebra morphisms and VPLs, respectively.

**Definition 4.7 (Length-Synchronicity).** The morphism $(\varphi, \psi): (\Sigma^\Delta, \mathcal{O}(\Sigma^\Delta)) \to (R, O)$ is $F$-length-synchronous (where $F \subseteq R$) if for all $F$-reachable idempotents $e \in O$ the set of contexts $\mathcal{R}_e$ is length-synchronous. We call a VPL $L \subseteq \Sigma^\Delta$ length-synchronous if its syntactic morphism $(\varphi_L, \psi_L)$ is $\varphi_L(L)$-length-synchronous.

**Example 4.8.** Consider our running example $\mathcal{L}_{1,2} = L(S \to aSb_1 \mid acSb_2 \mid \varepsilon)$. Recall that the monoid $O_{\mathcal{L}_{1,2}}$ of the syntactic Ext-algebra $(R_{\mathcal{L}_{1,2}}, O_{\mathcal{L}_{1,2}})$ and syntactic morphism $(\varphi_{\mathcal{L}_{1,2}}, \psi_{\mathcal{L}_{1,2}})$ of $\mathcal{L}_{1,2}$, given in Example 3.10, has the idempotents $(\varepsilon, \varepsilon)$, $(acb_1, \varepsilon)$ and $(a, b_1)$. Also recall that $\varphi_{\mathcal{L}_{1,2}}(\mathcal{L}_{1,2}) = \{\varepsilon, ab_1\}$. Since $\psi_{\mathcal{L}_{1,2}}^{-1}((\varepsilon, \varepsilon)) = \{\text{ext}_{\varepsilon,\varepsilon}\}$ and $(acb_1, \varepsilon)$ is a zero we have that $O_{\mathcal{L}_{1,2}}$'s only idempotent that is $\{\varepsilon, ab_1\}$-reachable and whose pre-image under $\psi_{\mathcal{L}_{1,2}}$ contains at least one $\text{ext}_{u,v}$ with $\Delta(u) > 0$ is the idempotent $(a, b_1)$. However, both $\text{ext}_{a,b_1}$ and $\text{ext}_{ac,b_2}$, where $\Delta(a) = \Delta(ac) = 1 > 0$, are sent to the idempotent $(a, b_1) = (a, b_2) \circ (c, \varepsilon)$. Since $|a|/|b_1| = 1 \neq 2 = |ac|/|b_2|$, we have that $\mathcal{L}_{1,2}$ is not length-synchronous. On the other hand, note that if any $\text{ext}_{u,v}$ and $\text{ext}_{u',v}$ (resp. $\text{ext}_{u,v}$ and $\text{ext}_{u',v'}$) are sent to $(a, b_1)$ then $u = u'$ and thus $|u| = |u'|$ (resp. $v = v'$ and thus $|v| = |v'|$). Hence, $\mathcal{L}_{1,2}$ is weakly length-synchronous.

As above, $F$-length-synchronicity actually implies length-synchronicity of the set of contexts associated to any subsemigroup of $F$-reachable elements.

**Lemma 4.9.** For all $F \subseteq R$ and subsemigroup $P$ of $O$, if all elements in $P$ are $F$-reachable and $(\varphi, \psi)$ is $F$-length-synchronous, then $\bigcup_{e \in P} \mathcal{R}_e$ is length-synchronous.

*Proof.* Let $F \subseteq R$ and $P$ be a subsemigroup of $O$. Assume all elements in $P$ are $F$-reachable and $(\varphi, \psi)$ is $F$-length-synchronous.

Let $(u, v), (u', v') \in \text{Con}(\Sigma)$ be such that $\Delta(u), \Delta(u') > 0$ and $\psi(\text{ext}_{u,v}), \psi(\text{ext}_{u',v'}) \in P$. Set $e = \psi(\text{ext}_{u,v})$ and $f = \psi(\text{ext}_{u',v'})$. By hypothesis, given $\omega \in \mathbb{N}_{>0}$ the idempotent power of $O$,
we have $(e^\omega f^\omega)^\omega \in P$, hence $(e^\omega f^\omega)^\omega$ is an $F$-reachable idempotent and thus $\mathcal{R}_{(e^\omega f^\omega)^\omega}$ is length-synchronous. But

$$ \psi(\mathrm{ext}_{(u^{2\cdot\omega}u'^{\omega})^\omega, (v'^{\omega}v^{2\cdot\omega})^\omega}) = (e^\omega f^\omega)^\omega = \psi(\mathrm{ext}_{(u^\omega u'^{2\cdot\omega})^\omega, (v'^{2\cdot\omega}v^\omega)^\omega}) $$

so since $\Delta((u^{2\cdot\omega}u'^{\omega})^\omega), \Delta((u^\omega u'^{2\cdot\omega})^\omega) > 0$, setting $(x, y) = ((u^{2\cdot\omega}u'^{\omega})^\omega, (v'^{\omega}v^{2\cdot\omega})^\omega)$ and $(x', y') = ((u^\omega u'^{2\cdot\omega})^\omega, (v'^{2\cdot\omega}v^\omega)^\omega)$, we obtain (using that for $a, b, c, d > 0$ we have that $\frac{a}{b} = \frac{c}{d}$ implies $\frac{a}{b} = \frac{c}{d} = \frac{a+c}{b+d}$ and, if additionally $a > c$, it implies $\frac{a}{b} = \frac{c}{d} = \frac{a-c}{b-d}$)

$$ \begin{align*} \frac{|x|}{|y|} = \frac{|x'|}{|y'|} &\implies \frac{|x|}{|y|} = \frac{|x'|}{|y'|} = \frac{|x| + |x'|}{|y| + |y'|} = \frac{\omega^2 \cdot (|u| + |u'|)}{\omega^2 \cdot (|v| + |v'|)} \\ &\implies \frac{|x| - \omega^2 \cdot (|u| + |u'|)}{|y| - \omega^2 \cdot (|v| + |v'|)} = \frac{|x'| - \omega^2 \cdot (|u| + |u'|)}{|y'| - \omega^2 \cdot (|v| + |v'|)} \tag{1} \\ &\implies \frac{|u|}{|v|} = \frac{\omega^2 \cdot |u|}{\omega^2 \cdot |v|} \stackrel{(1)}{=} \frac{\omega^2 \cdot |u'|}{\omega^2 \cdot |v'|} = \frac{|u'|}{|v'|}. \end{align*} $$

Therefore, $\bigcup_{e \in P} \mathcal{R}_e$ is length-synchronous. $\square$

The two following propositions characterize length-synchronicity of Ext-algebra morphisms, which will be of particular importance when approximating the matching relation of a length-synchronous VPL in terms of FO$[+]$. This will be an important ingredient to proving that VPLs that both are length-synchronous and have a quasi-aperiodic syntactic morphism (a notion to be defined in Subsection 4.4) are in FO$[+]$ and thus in AC$^0$.

**Proposition 4.10.** For all $F \subseteq R$, we have that $(\varphi, \psi)$ is $F$-length-synchronous if, and only if, for all $F$-reachable $e \in O$ the set of contexts $\mathcal{U}_e$ is length-synchronous.

*Proof.* Let $F \subseteq R$.

If $\mathcal{U}_e = \{(u, v) \in \mathrm{Con}(\Sigma) \mid e \circ \psi(\mathrm{ext}_{u,v}) = e\}$ is length-synchronous for all $F$-reachable $e \in O$, then in particular the set of contexts $\mathcal{R}_e = \{(u, v) \in \mathrm{Con}(\Sigma) \mid \psi(\mathrm{ext}_{u,v}) = e\}$ is length-synchronous for all $F$-reachable idempotents $e \in O$.

Conversely, assume that $(\varphi, \psi)$ is $F$-length-synchronous. Fix any $F$-reachable $e \in O$. We need to prove that $\mathcal{U}_e$ is length-synchronous. It is clear that $P = \{f \in O \mid e \circ f = e\}$ forms a subsemigroup of $O$ whose elements are all $F$-reachable, by $F$-reachability of $e$. Therefore, by Lemma 4.9, $\bigcup_{f \in P} \mathcal{R}_f = \mathcal{U}_e$ is length-synchronous. $\square$

**Proposition 4.11.** Let $F \subseteq R$ and assume $(\varphi, \psi)$ is $F$-weakly-length-synchronous. Then for all $F$-reachable $e \in O$ the following two statements are equivalent.

1. The set of contexts $\mathcal{U}_e$ is length-synchronous.

2. There exist $\alpha \in \mathbb{Q}_{>0}$, $\beta \in \mathbb{N}$, $\gamma \in \mathbb{N}_{>0}$ such that for all $(u, v) \in \mathcal{U}_e$ with $\Delta(u) > 0$ we have:

(a) $\frac{|u|}{|v|} = \alpha$.

(b) For all $u', v' \in \Sigma^+$ with $u'$ prefix of $u$ and $v'$ suffix of $v$ such that $\frac{|u'|}{|v'|} = \alpha$, we have that $-\Delta(v') - \beta \le \Delta(u') \le -\Delta(v') + \beta$.

(c) For all factors $u' \in \Sigma^*$ of $u$ such that $|u'| = \gamma$, we have $\Delta(u') \ge 1$.

(d) For all factors $v' \in \Sigma^*$ of $v$ such that $|v'| = \gamma$, we have $\Delta(v') \le -1$.
*Proof.* The implication from Point 2 to Point 1 is trivial since Point 2 (a) implies Point 1.

Let us now prove that Point 1 implies Point 2. Fix any $e \in O$ that is $F$-reachable and assume that $\mathcal{U}_e$ is length-synchronous. Point 2 (a) follows immediately from length-synchronicity of $\mathcal{U}_e$. We can hence write $\alpha = \frac{A}{B}$ for some $A, B \in \mathbb{N}_{>0}$.

For proving Point 2 (b), we define $\beta = (n+1) \cdot (|O| + \max(A, B) + 1)$, where $n$ is the constant taken from Lemma 4.1. Let $(u, v) \in \mathcal{U}_e$ with $\Delta(u) > 0$ and let

$$ \mathrm{ext}_{u,v} = \mathrm{ext}_{x_1, y_1} \circ \mathrm{ext}_{a_1, b_1} \circ \dots \circ \mathrm{ext}_{x_{h-1}, y_{h-1}} \circ \mathrm{ext}_{a_{h-1}, b_{h-1}} \circ \mathrm{ext}_{x_h, y_h} $$

be the stair factorization of $\mathrm{ext}_{u,v}$ according to Lemma 3.6. Since our morphism $(\varphi, \psi)$ is $F$-weakly-length-synchronous by assumption, we have $|x_i|, |y_i| \le n$ by Lemma 4.6. Let $u' \in \Sigma^*$ be a prefix of $u$ and $v'$ be a suffix of $v$ such that $\frac{|u'|}{|v'|} = \alpha$. If $(u', v') = (u, v)$ we are done since then $\Delta(u') = -\Delta(v')$. Thus, it remains to consider the case when $u'$ is a strict prefix of $u$ and $v'$ is a strict suffix of $v$: indeed, due to $\frac{|u|}{|v|} = \frac{|u'|}{|v'|} = \alpha$ we have that $u'$ is a strict prefix of $u$ if, and only if, $v'$ is a strict suffix of $v$.

Let $j \in [1, h]$ be maximal such that $x_1 \cdots a_{j-1}x_j$ is a prefix of $u'$ and $y_j b_{j-1} \cdots y_1$ is a suffix of $v'$. If $j = 1$ we are done, since then $\min\{|u'|, |v'|\} \le n$, so that $|\Delta(u') + \Delta(v')| \le |u'| + |v'| \le n + n \cdot \max(A, B) \le \beta$. So assume now that $j > 1$, which implies that $\Delta(u'') > 0$. Note that $j < h$ since $(u', v') \ne (u, v)$. Hence there exist unique words $s, t \in \Sigma^*$ such that $u' = u''s$ and $v' = tv''$, where $u'' = x_1 \cdots a_{j-1}x_j$ and $v'' = y_j b_{j-1} \cdots y_1$. By maximality of $j$ we have $\min\{|s|, |t|\} \le n$. Setting $f = \psi(\mathrm{ext}_{u'', v''})$ and $g = \psi(\mathrm{ext}_{a_j x_{j+1} \cdots a_{h-1} x_h, y_h b_{h-1} \cdots y_{j+1} b_j})$ we have $\psi(\mathrm{ext}_{u,v}) = f \circ g$. We claim that there exist $\mathrm{ext}_{x_g, y_g} \in \mathcal{O}(\Sigma^\Delta)$ such that $\psi(\mathrm{ext}_{x_g, y_g}) = g$ and $|x_g|, |y_g| \le |O| \cdot (n+1)$: indeed, by the pigeonhole principle and Lemma 4.6 (as $e \circ f \circ g = e$ and $\Delta(u'') > 0$), any $\mathrm{ext}_{x,y} \in \mathcal{O}(\Sigma^\Delta)$ such that $\psi(\mathrm{ext}_{x,y}) = g$ and $\max(|x|, |y|) > |O|(n+1)$ must have a stair factorization according to Lemma 3.6 with an $h > |O|$ and can thus be factorized as $\mathrm{ext}_{x,y} = \mathrm{ext}_{x', y'} \circ \mathrm{ext}_{x'', y''} \circ \mathrm{ext}_{x'''', y'''}$ such that $\psi(\mathrm{ext}_{x,y}) = \psi(\mathrm{ext}_{x', y'}) \circ \psi(\mathrm{ext}_{x'''', y'''}),$ where moreover $(x'', y'') \in \Sigma^+ \times \Sigma^+$. Thus, $\psi(\mathrm{ext}_{u''x_g, y_g v''}) = \psi(\mathrm{ext}_{u,v})$ and therefore $(u''x_g, y_g v'') \in \mathcal{U}_e$ with $\Delta(u''x_g) > 0$. It follows $\alpha = \frac{|u''x_g|}{|y_g v''|} = \frac{|u'|-|s|+|x_g|}{|y_g|+|v'|-|t|}$, or equivalently, using $\frac{|u'|}{|v'|} = \alpha$:

$$ |s| = |u'| + |x_g| + \alpha(|t| - |y_g| - |v'|) = |x_g| + \alpha(|t| - |y_g|) \quad (2) $$

$$ |t| = \frac{|s| - |u'| - |x_g|}{\alpha} + |y_g| + |v'| = \frac{|s| - |x_g|}{\alpha} + |y_g|. \quad (3) $$

Finally, we obtain

$$
\begin{align*}
|\Delta(u') + \Delta(v')| &= |\Delta(u''s) + \Delta(tv'')| \\
\Delta(u'') = -\Delta(v'') &= |\Delta(s) + \Delta(t)| \\
&\le |s| + |t| \\
&= \min(|s|, |t|) + \max(|s|, |t|) \\
&\le n + \max(|s|, |t|) \\
(2),(3) \le n + \max & \left( |x_g| + \alpha(n - |y_g|), \frac{n - |x_g|}{\alpha} + |y_g| \right) \\
&\le n + |O| \cdot (n+1) + n \cdot \max(A, B) \\
&\le (n+1) \cdot (|O| + \max(A, B) + 1) \\
&= \beta.
\end{align*}
$$
This proves Point 2 (b).

For Point 2 (c) and Point 2 (d) we set $\gamma = (\lceil \frac{n}{2} \rceil + 1) \cdot (n + 1) + n$ and remark that $\gamma$ does not depend on $u$ nor $v$. We only prove Point 2 (c), the proof of Point 2 (d) is analogous. As above, let

$$ \mathrm{ext}_{u,v} = \mathrm{ext}_{x_1,y_1} \circ \mathrm{ext}_{a_1,b_1} \circ \cdots \circ \mathrm{ext}_{x_{h-1},y_{h-1}} \circ \mathrm{ext}_{a_{h-1},b_{h-1}} \circ \mathrm{ext}_{x_h,y_h} $$

be the stair factorization of $\mathrm{ext}_{u,v}$ according to Lemma 3.6. Let $u'$ with $|u'| \ge \gamma$ be a factor of $u$ and hence of $x_1a_1x_2 \cdots x_{h-1}a_{h-1}x_h$. By definition of stair factorization we have $\Delta(x_i) = 0$ for all $i \in [1, h]$ and $\Delta(a_i) = 1$ for all $i \in [1, h - 1]$. Let $w$ be the longest prefix of $u'$ such that $\Delta(w) = \min\{\Delta(x) \mid x$ is a prefix of $u'\}$. Since $|x_1|, |y_1|, \dots, |x_h|, |y_h| \le n$, it immediately follows $\Delta(w) \ge -\frac{n}{2}$ and $|w| \le n$. By the same reason, every prefix of the form $ws$ of $u'$ satisfies $\Deltalearners(w) \ge \Delta(w) + \frac{|s|}{n+1}$. Thus we have

$$ \Delta(u') \ge \Delta(w) + \frac{|u' - w|}{n+1} \ge -\frac{n}{2} + \frac{((\lceil \frac{n}{2} \rceil + 1) \cdot (n+1) + n) - n}{n+1} \ge 1. \quad \square $$

The following proposition relates, for languages $L$ generated by vertically visibly pushdown grammars $G$, (weak) length-synchronicity of $L$ with (weak) length-synchronicity of $\mathcal{R}(G)$.

**Proposition 4.12.** Let $L = L(G)$ for some vertically visibly pushdown grammar $G = (V, \Sigma, P, S)$. Moreover, let $\mathcal{R}(G) = \{(u, v) \in \mathrm{Con}(\Sigma) \mid S \Rightarrow_G^* uSv\}$. Then the following equivalences hold:

1. $L(G)$ is length-synchronous if, and only if, $\mathcal{R}(G)$ is length-synchronous.

2. $L(G)$ is weakly length-synchronous if, and only if, $\mathcal{R}(G)$ is weakly length-synchronous.

*Proof.* Let $L = L(G)$ for a vertically visibly pushdown grammar $G = (V, \Sigma, P, S)$. Moreover, let $(\varphi_L, \psi_L) : (\mathcal{O}(\Sigma), \Sigma^\Delta) \to (R_L, O_L)$ be the syntactic morphism. For all $e \in O_L$ recall the set of contexts $\mathcal{R}_e = \{(u, v) \in \mathrm{Con}(\Sigma) \mid \psi_L(\mathrm{ext}_{u,v}) = e\}$.

Let $F = \{e \in O_L \mid \exists \mathrm{ext}_{u,v} \in \psi_L^{-1}(e) : (u, v) \in \mathcal{R}(G)\}$. Observe that $F$ is a submonoid of $O_L$ all of whose elements are $\varphi_L(L)$-reachable since $G$ is vertically visibly pushdown. Also observe that $\mathcal{R}(G) = \bigcup_{f \in F} \mathcal{R}_f$. We claim that since $G$ is vertically visibly pushdown, there exists a constant $C > 0$ such that $\frac{1}{C} \le \frac{|x|}{|y|} \le C$ for all $(x, y) \in \mathcal{R}(G) \setminus \{(\varepsilon, \varepsilon)\}$: indeed, one can take $C = \frac{A}{B}$ where $A = \max\{\max\{|u|, |v|\} \mid T \to_G uT'v\}$ and $B = \min\{\min\{|u|, |v|\} \mid T \to_G uT'v\}$ since whenever $T \Rightarrow_G^* xT'y$ thanks to a derivation comprising $k \in \mathbb{N}_{>0}$ steps, we have

$$ \frac{1}{C} = \frac{k \cdot B}{k \cdot A} \le \frac{|x|}{|y|} \le \frac{k \cdot A}{k \cdot B} = C. $$

Next, we prove that for all $\varphi_L(L)$-reachable idempotents $e \in O_L$ there exist $g, h \in O_L$ such that $g \circ e \circ h \in F$. Fix any such $\varphi_L(L)$-reachable idempotent $e \in O_L$. Without loss of generality let us assume that $e$ is not the identity in $O_L$ (indeed, if $e$ is the identity in $O_L$, then we are done since we can then choose $g = h = e \in F$). Thus there exist $g \in O_L$ and $r \in R_L$ such that $(g \circ e)(r) \in \varphi_L(L)$. Moreover, let $\mathrm{ext}_{u',v'} \in \psi_L^{-1}(g), \mathrm{ext}_{u,v} \in \psi_L^{-1}(e)$, and $w \in \varphi_L^{-1}(r)$. Observe that we must have $(u, v) \ne (\varepsilon, \varepsilon)$ since $\psi_L(\mathrm{ext}_{\varepsilon,\varepsilon})$ is the identity in $O_L$. Since $e$ is an idempotent we have that $u'u^nwv^nv' \in L$ for all $n \ge 1$. Fix a sufficiently large $N \ge 1$ such that $\frac{|u'|+|u|}{(N-1)|u|+|w|+N|v|+|v'|} \le \frac{1}{C}$ and $\frac{|u'|+N|u|+|w|+(N-1)|v|}{|v|+|v'|} \ge C$, which exists due to $(u, v) \ne (\varepsilon, \varepsilon)$. Since $u'u^nwv^nv' \in L$ there exists $(x, y) \in \mathcal{R}(G) \setminus \{(\varepsilon, \varepsilon)\}$ such that $xy = u'u^N wv^N v'$, $S \Rightarrow_G^* xSy$, $|x| \ge |u'u|$, and $|y| \ge |vv'|$. Let $(x', y') \in \Sigma^* \times \Sigma^*$ be such that $(x, y) = (u'ux', y'vv')$. As $(u', v'), (u, v), (x, y) \in \mathrm{Con}(\Sigma)$,
$x' \in (\Sigma \setminus \Sigma_{\text{ret}})^*$, and $y' \in (\Sigma \setminus \Sigma_{\text{call}})^*$, we can conclude $(x', y') \in \text{Con}(\Sigma)$. That is, $(x, y) = (u', v') \circ (u, v) \circ (x', y') \in \mathcal{R}(G)$. Hence,

$$g \circ e \circ \psi_L(\text{ext}_{x', y'}) = \psi_L(\text{ext}_{u'ux', y'vv'}) = \psi_L(\text{ext}_{x,y}) \in F.$$

We are now ready to prove Point 1. For the first direction, let us assume that $L(G)$ is length-synchronous. Recalling that $F$ is a submonoid of $O_L$ all of whose elements are $\varphi_L(L)$-reachable, we obtain that $R(G) = \bigcup_{f \in F} \mathcal{R}_f$ is length-synchronous by Lemma 4.9.

Conversely, let us assume that $\mathcal{R}(G)$ is length-synchronous. Assume by contradiction that $L(G)$ is not length-synchronous. Hence $\mathcal{R}_e$ is not length-synchronous for some $\varphi_L(L)$-reachable idempotent $e \in O_L$, i.e. $\psi_L(\text{ext}_{u,v}) = \psi_L(\text{ext}_{u',v'}) = e$ for some $\text{ext}_{u,v}, \text{ext}_{u',v'} \in \mathcal{O}(\Sigma^\Delta)$ such that $\Delta(u), \Delta(u') > 0$ and $\frac{|u|}{|v|} \neq \frac{|u'|}{|v'|}$. Without loss of generality we may assume that $|v| = |v'|$ (indeed, if $|v| \neq |v'|$, then $\text{ext}_{u|v'|,v|v'|}, \text{ext}_{(u')|v|,(v')|v|}$ satisfies the desired property). As a consequence we have $|u| \neq |u'|$, say $|u| < |u'|$ without loss of generality. Since $e$ is a $\varphi_L(L)$-reachable idempotent, as argued above, there exist $g, h \in O_L$ such that $g \circ e \circ h = f'$ for some $f' \in F$. Let us fix $\text{ext}_{x_h, y_h} \in \psi_L^{-1}(h)$ and $\text{ext}_{x_g, y_g} \in \psi_L^{-1}(g)$. We have $\psi_L(\text{ext}_{x_g u x_h, y_h v y_g}) = f' = \psi_L(\text{ext}_{x_g u' x_h, y_h v' y_g})$. Since $|x_g u x_h| < |x_g u' x_h|$ and $|y_h v y_g| = |y_h v' y_g|$ it follows that $\mathcal{R}_f'$ is not length-synchronous, contradicting our assumption that $R(G) = \bigcup_{f \in F} \mathcal{R}_f$ is length-synchronous.

Let us next prove Point 2.

Let us first assume that $L(G)$ is weakly length-synchronous. Again, since $F$ is a submonoid of $O_L$ all of whose elements are $\varphi_L(L)$-reachable, we obtain that $R(G) = \bigcup_{f \in F} \mathcal{R}_f$ is weakly length-synchronous by Lemma 4.4.

Conversely, assume $\mathcal{R}(G)$ is weakly length-synchronous. Assume by contradiction that $\mathcal{R}_e$ is not weakly length-synchronous for some $\varphi_L(L)$-reachable idempotent $e \in O_L$. Thus, $\psi_L(\text{ext}_{u,v}) = \psi_L(\text{ext}_{u',v'}) = e$ for some $\text{ext}_{u,v}, \text{ext}_{u',v'} \in \mathcal{O}(\Sigma^\Delta)$ such that $\Delta(u), \Delta(u') > 0$ and moreover either $u = u'$ and $|v| \neq |v'|$ or $v = v'$ and $|u| \neq |u'|$. Without loss of generality let us assume that $u = u'$ and $|v| \neq |v'|$. As mentioned above, there exist $g, h \in O_L$ such that $g \circ e \circ h = f'$ for some $f' \in F$. Fix some $\text{ext}_{x_g, y_g} \in \psi_L^{-1}(g)$ and some $\text{ext}_{x_h, y_h} \in \psi_L^{-1}(h)$. Analogously, as argued above, we have $\psi_L(\text{ext}_{x_g u x_h, y_h v y_g}) = \psi_L(\text{ext}_{x_g u x_h, y_h v' y_g}) = f'$, $\Delta(x_g u x_h) > 0$, and $|y_h v y_g| \neq |y_h v' y_g|$, implying that $\mathcal{R}_f'$ is not weakly length-synchronous, a contradiction to our assumption that $R(G) = \bigcup_{f \in F} \mathcal{R}_f$ is weakly length-synchronous. $\square$

## 4.3 The nesting depth of visibly pushdown languages

Another central notion is the nesting depth of well-matched words, which is the Horton-Strahler number [15] of the underlying trees.

**Definition 4.13.** The nesting depth of well-matched words is given by the function nd: $\Sigma^\Delta \to \mathbb{N}$ defined inductively as follows:

* nd($\varepsilon$) = 0;

* nd(c) = 0 for all $c \in \Sigma_{\text{int}}$;

* nd(uv) = max{nd(u), nd(v)} for all $u \in \Sigma_{\text{call}} \Sigma^\Delta \Sigma_{\text{ret}} \cup \Sigma_{\text{int}}$ and $v \in \Sigma^\Delta \setminus \{\varepsilon\}$;

* nd(awb) = 
  $$ \begin{cases} 
    \text{nd}(w) + 1 & \text{if } w = uv \text{ with } u, v \in \Sigma^\Delta \text{ and } \text{nd}(w) = \text{nd}(u) = \text{nd}(v) \\
    \text{nd}(w) & \text{otherwise}
  \end{cases} $$
  for all $a \in \Sigma_{\text{call}}, b \in \Sigma_{\text{ret}}$ and $w \in \Sigma^\Delta$.
An important property of weakly length-synchronous VPLs is that their words have bounded nesting depth.

**Proposition 4.14.** For each weakly length-synchronous VPL $L \subseteq \Sigma^\Delta$ there exists a constant $d \in \mathbb{N}$ such that $L \subseteq \{w \in \Sigma^\Delta | \text{nd}(w) \le d\}$.

Proposition 4.14 is proved in several steps. For these we introduce a factorization that can be seen as one that witnesses the nesting depth of a word.

**Definition 4.15.** A nesting-maximal stair factorization of $w \in \Sigma^\Delta$ with $\text{nd}(w) \ge 1$ is a factorization of $w$ as

$$w = \text{ext}_{x_1, y_1} \circ \text{ext}_{a_1, b_1} \circ \dots \circ \text{ext}_{x_k, y_k} \circ \text{ext}_{a_k, b_k}(w')$$

such that $k \ge 0$, $x_i, y_i \in \Sigma^\Delta$, $a_i \in \Sigma_{\text{call}}$, and $b_i \in \Sigma_{\text{ret}}$ for all $i \in [1, l]$, and $w' \in \Sigma_{\text{int}}^*$ satisfying that for all $i \in [1, k]$ we have

$$\text{nd}(\text{ext}_{x_i, y_i}(w_i)) = \text{nd}(w_i),$$

where $w_i = \text{ext}_{a_i, b_i} \circ \text{ext}_{x_{i+1}, y_{i+1}} \circ \dots \circ \text{ext}_{a_k, b_k}(w')$.

**Lemma 4.16.** All words $w \in \Sigma^\Delta$ have a nesting-maximal stair factorization.

*Proof.* The proof goes by structural induction on $w$.

* $w = \varepsilon$. Then we are done because $w$ contains only internal letters.

* $w = c$ for a $c \in \Sigma_{\text{int}}$. Then we are again done because $w$ contains only internal letters.

* $w = aw'b$ for $a \in \Sigma_{\text{call}}$, $b \in \Sigma_{\text{ret}}$ and $w' \in \Sigma^\Delta$. By using the inductive hypothesis, $w'$ has a nesting-maximal stair factorization $\text{ext}_{x_1, y_1} \circ \text{ext}_{a_1, b_1} \circ \dots \circ \text{ext}_{x_k, y_k} \circ \text{ext}_{a_k, b_k}(w'')$. It directly follows that $\text{ext}_{a,b} \circ \text{ext}_{x_1, y_1} \circ \text{ext}_{a_1, b_1} \circ \dots \circ \text{ext}_{x_k, y_k} \circ \text{ext}_{a_k, b_k}(w'')$ is a nesting-maximal stair factorization of $w$.

* $w = uv$ for $u, v \in \Sigma^\Delta \setminus \{\varepsilon\}$. Then $w$ can be decomposed as $z_1 \cdots z_m$ with $z_1, \dots, z_m \in \Sigma_{\text{call}}\Sigma^\Delta\Sigma_{\text{ret}} \cup \Sigma_{\text{int}}$ and $m \in \mathbb{N}, m \ge 2$. In this case, either $z_i \in \Sigma_{\text{int}}$ for all $i \in [1, m]$ and thus we are done because $w$ contains only internal letters, or there exists some $i \in [1, m]$ such that $z_i \in \Sigma_{\text{call}}\Sigma^\Delta\Sigma_{\text{ret}}$ and has maximal nesting depth, i.e. $\text{nd}(w) = \text{nd}(z_i)$. In this second subcase, we have that $z_i = az'_i b$ with $a \in \Sigma_{\text{call}}$, $b \in \Sigma_{\text{ret}}$ and $z'_i \in \Sigma^\Delta$. By using the inductive hypothesis, $z'_i$ has a nesting-maximal stair factorization $\text{ext}_{x_1, y_1} \circ \text{ext}_{a_1, b_1} \circ \dots \circ \text{ext}_{x_k, y_k} \circ \text{ext}_{a_k, b_k}(w'')$. Therefore,

$$\text{ext}_{z_1 \cdots z_{i-1}, z_{i+1} \cdots z_k} \circ \text{ext}_{a, b} \circ \text{ext}_{x_1, y_1} \circ \text{ext}_{a_1, b_1} \circ \dots \text{ext}_{x_k, y_k} \circ \text{ext}_{a_k, b_k}(w'')$$

is a nesting-maximal stair factorization of $w$. $\square$

The following lemma will be a useful tool for proofs by induction on the nesting depth of well-matched words.

**Lemma 4.17.** Let $u = a_1vb_1 \in \Sigma^\Delta$ for some $a_1 \in \Sigma_{\text{call}}$, $b_1 \in \Sigma_{\text{ret}}$, and $v \in \Sigma^\Delta$ such that $\text{nd}(u) = d > 0$. Moreover, let $u = \text{ext}_{x_1, y_1} \circ \text{ext}_{a_1, b_1} \circ \dots \circ \text{ext}_{x_k, y_k} \circ \text{ext}_{a_k, b_k}(u')$ be a nesting-maximal stair factorization of $u$ (i.e. $x_1 = y_1 = \varepsilon$). Then there exists $h \in [1, k]$ such that, setting $u_i = \text{ext}_{a_i, b_i} \circ \text{ext}_{x_{i+1}, y_{i+1}} \circ \dots \circ \text{ext}_{a_k, b_k}(u')$ for all $i \in [1, k]$ and $u_{k+1} = u'$, we have

1. $\text{nd}(u) = \text{nd}(u_h) = d$,

2. $\text{nd}(u_{h+1}) = d-1$, and

3. $\text{nd}(x_1), \text{nd}(y_1), \dots, \text{nd}(x_h), \text{nd}(y_h) < d$.
Proof. Let $u_j = \text{ext}_{a_j,b_j} \circ \text{ext}_{x_{j+1},y_{j+1}} \circ \dots \circ \text{ext}_{a_k,b_k}(u')$ for all $j \in [1, k]$. Note that we have $\text{nd}(u) = \text{nd}(u_1) = d > 0$ by assumption. Moreover, $\text{nd}(u_j) \ge \text{nd}(u_{j+1})$ for all $j \in [1, k-1]$ by definition of nesting depth. Thus, since $\text{nd}(u_k) = 1 > 0 = \text{nd}(u_{k+1})$, it follows that

$$h = \min\{j \in [1, k] \mid \text{nd}(u_j) > \text{nd}(u_{j+1})\}$$

is well-defined and $\text{nd}(u) = \text{nd}(u_1) = \text{nd}(u_h) = d$, thus showing Point 1. Since

$$d = \text{nd}(u_h) \le \text{nd}(u_{h+1}) + 1$$

and $\text{nd}(u_{h+1}) < \text{nd}(u_h) = d$ it follows $\text{nd}(u_{h+1}) = d-1$, thus showing Point 2. To prove Point 3, assume by contradiction that $\text{nd}(x_j) \ge d$ or $\text{nd}(y_j) \ge d$ for some $j \in [1, h]$. Without loss of generality assume $\text{nd}(x_j) \ge d$. Since $x_1 = y_1 = \varepsilon$ and $d > 0$ we must have $j \in [2, h]$. It follows

$$\text{nd}(u) \ge \text{nd}(u_{j-1}) = \text{nd}(a_{j-1}x_j u_j y_j b_{j-1}) \ge \min(\text{nd}(x_j), \text{nd}(u_j)) + 1 \ge d + 1 > d = \text{nd}(u),$$

which is a contradiction. $\square$

We are now ready to prove Proposition 4.14.

Proof of Proposition 4.14. Let $L \subseteq \Sigma^\Delta$ be a weakly length-synchronous VPL. We claim that $\text{nd}(L) \le n+1$, where $n$ is the pumping constant from Lemma 4.1. Assume by contradiction that $\text{nd}(u) = d$ for some $u \in L$ and some $d > n+1$. Let $u = \text{ext}_{x_1,y_1} \circ \text{ext}_{a_1,b_1} \circ \dots \circ \text{ext}_{x_k,y_k} \circ \text{ext}_{a_k,b_k}(u')$ be a nesting-maximal stair factorization of $u$ according to Lemma 4.16. According to Lemma 4.17 there exists $i \in [1, k]$ such that, setting $u_j = \text{ext}_{a_j,b_j} \circ \text{ext}_{x_{j+1},y_{j+1}} \circ \dots \circ \text{ext}_{a_k,b_k}(u')$ for all $j \in [1, k]$ and $u_{k+1} = u'$, we have $\text{nd}(u) = \text{nd}(u_i) = d$ and $\text{nd}(u_{i+1}) = d-1$. Since $d-1 > n > 0$, we must have $i+1 \le k$, so that $u_i = a_i x_{i+1} u_{i+1} y_{i+1} b_i$ with $u_{i+1} \in \Sigma_{\text{call}} \Sigma^\Delta \Sigma_{\text{ret}}$ and $\text{nd}(x_{i+1} u_{i+1} y_{i+1}) = \text{nd}(u_{i+1}) = d-1$. Hence it follows that $\text{nd}(x_{i+1}) = d-1$ or $\text{nd}(y_{i+1}) = d-1$. Without loss of generality let us assume $\text{nd}(y_{i+1}) = d-1 > n$. A simple induction shows that $|x| \ge 2^{\text{nd}(x)} - 1 \ge \text{nd}(x)$ for all $x \in \Sigma^\Delta$. Thus, we have $|y_{i+1}| \ge \text{nd}(y_{i+1}) > n$, contradicting Proposition 4.6. $\square$

## 4.4 Quasi-aperiodicity and its correspondence with quasi-counterfreeness

Let us revisit the notion of quasi-aperiodicity. It has already been defined for visibly pushdown languages in [24]. Let us define $\mathcal{O}(\Sigma^\Delta)^{k,l} = \{\text{ext}_{u,v} \in \mathcal{O}(\Sigma^\Delta) : |u| = k, |v| = l\}$ for all $k, l \in \mathbb{N}$. We say the morphism $(\varphi, \psi) : (\Sigma^\Delta, \mathcal{O}(\Sigma^\Delta)) \to (R, O)$ is quasi-aperiodic if all semigroups contained in the set $\psi(\mathcal{O}(\Sigma^\Delta)^{k,l})$ are aperiodic for all $k, l \in \mathbb{N}$.

The following proposition relates quasi-counterfreeness of a VPL with quasi-aperiodicity of its syntactic morphism.

**Proposition 4.18.** A VPL $L \subseteq \Sigma^\Delta$ is quasi-counterfree if, and only if, its syntactic morphism is quasi-aperiodic.

Proof. Recall that $(R_L, O_L) = (\Sigma^\Delta, \mathcal{O}(\Sigma^\Delta))/\sim_L$ by Definition 3.13. Hence for all $(u, v), (u', v') \in \text{Con}(\Sigma)$ we have $(u, v) \equiv_L (u', v')$ if, and only if, $\psi_L(\text{ext}_{u,v}) = \psi_L(\text{ext}_{u',v'})$.

First, let us assume that $(\varphi_L, \psi_L) : (\Sigma^\Delta, \mathcal{O}(\Sigma^\Delta)) \to (R_L, O_L)$ is quasi-aperiodic. Assume by contradiction that $L$ is not quasi-counterfree. Thus, there exists some $\sigma = (u, v) \in \text{Con}(\Sigma)$ such that $\sigma^n \not\equiv_L \sigma^{n+1}$ for all $n \in \mathbb{N}$ and $\tau \equiv_L \sigma \circ \sigma$ for some $\tau = (x, y) \in \text{Con}(\Sigma) \cap \Sigma^{|u|} \times \Sigma^{|v|}$. The latter can equivalently be rephrased as $\psi_L(\text{ext}_{x,y}) = \psi_L(\text{ext}_{u^2,v^2})$. By choice of $\sigma$ and the fact that $\equiv_L$ has finite index there exist $s \ge 1$ and $t \ge 2$ such that $\sigma^{s+i} \equiv_L \sigma^{s+i+t}$ for all $i \ge 0$ and $\sigma^{s+i} \not\equiv_L \sigma^{s+j}$ for all $i, j \in [0, t-1]$ with $i \ne j$. It follows that the set $G = \psi_L(\{\text{ext}_{u^{s+i},v^{s+i}} | i \in [0, t-1]\})$ is a non-trivial
group with identity $g_0 = \psi_L(\mathrm{ext}_{u^s+k, vs^s+k}) \in \psi_L(\mathcal{O}(\Sigma^\Delta)^{(s+k)|u|, (s+k)|v|})$, where $k$ is the unique integer in $[0, t-1]$ such that $s+k$ is divisible by $t$. Also observe that $G$ is a cyclic group that is generated by $g_1 = \psi_L(\mathrm{ext}_{u^s+k+1, vs^s+k+1})$. That is $G = \{g_0, g_1, \dots, g_{t-1}\}$, where $g_i = g_1^i$ for all $i \in [2, t-1]$. But note that due to $\psi_L(\mathrm{ext}_{x, y}) = \psi_L(\mathrm{ext}_{u^2, v^2})$ we obtain $g_1 = \psi_L(\mathrm{ext}_{u^{s+k+1}, vs^s+k+1}) = \psi_L(\mathrm{ext}_{xu^{s+k-1}, vs^{s+k-1}y})$ and thus $g_0, g_1 \in \psi_L(\mathcal{O}(\Sigma^\Delta)^{(s+k)|u|, (s+k)|v|})$ due to $|x| = |u|$ and $|y| = |v|$. Since $g_i = g_0^{t-1-i}g_1^i$ for all $i \in [0, t-1]$ we obtain that $G = \{g_0, g_1, \dots, g_{t-1}\}$ is contained in $\psi_L(\mathcal{O}(\Sigma^\Delta)^{(t-1)(s+k)|u|, (t-1)(s+k)|v|})$, hereby contradicting quasi-aperiodicity of $(\varphi_L, \psi_L)$.

For the converse direction, let us assume that $L$ is quasi-counterfree. Assume by contradiction that $(\varphi_L, \psi_L)$ is not quasi-aperiodic. That is, for some $k, l \in \mathbb{N}$ the set $\psi_L(\mathcal{O}(\Sigma^\Delta)^{k,l})$ contains a non-trivial group $G$. Let $g_0 \in G$ be the identity of $G$. Fix some $g \in G$ with $g \neq g_0$ and some $\mathrm{ext}_{u,v} \in \mathcal{O}(\Sigma^\Delta)^{k,l}$ such that $\psi_L(\mathrm{ext}_{u,v}) = g$. Let $\sigma = (u, v) \in \mathrm{Con}(\Sigma) \cap \Sigma^k \times \Sigma^l$. Since $g$ is not the identity in $G$ we have that $\psi_L(\mathrm{ext}_{u^n, u^n}) \neq \psi_L(\mathrm{ext}_{u^{n+1}, u^{n+1}})$ for all $n \in \mathbb{N}$, equivalently $\sigma^n \not\equiv_L \sigma^{n+1}$ for all $n \in \mathbb{N}$. But since moreover $\psi_L(\mathrm{ext}_{u^n, u^n})$ is in $G$ and thus in $\psi_L(\mathcal{O}(\Sigma^\Delta)^{k,l})$ for all $n \in \mathbb{N}$ it follows that $\sigma \circ \sigma \equiv_L \tau$ for some $\tau \in \mathrm{Con}(\Sigma) \cap \Sigma^k \times \Sigma^l$. We thus obtain a contradiction to our assumption that $L$ is quasi-counterfree. $\square$

# 5 Proof of the main theorem

Before giving an overview of the proof of Theorem 2.9 we will state a proposition saying that the syntactic Ext-algebra and the syntactic morphism of a given visibly pushdown language $L$ is computable and that it is decidable if $L$ is quasi-aperiodic, length-synchronous, and weakly length-synchronous, respectively. Its proof is subject of Section 6.

**Proposition 5.1.** The following computability and decidability results hold:

1. Given a DVPA $A$, one can effectively compute the syntactic Ext-algebra of $L = L(A)$, its syntactic morphism $(\varphi_L, \psi_L)$ and $\varphi_L(L)$.

2. Given a morphism $(\varphi, \psi) : (\Sigma^\Delta, \mathcal{O}(\Sigma^\Delta)) \to (R, O)$ for a visibly pushdown alphabet $\Sigma$ and a finite Ext-algebra $(R, O)$, all of the following are decidable for $(\varphi, \psi)$:

(a) Quasi-aperiodicity. In case $(\varphi, \psi)$ is not quasi-aperiodic, one can effectively compute $k, l \in \mathbb{N}$ such that $\psi(\mathcal{O}(\Sigma^\Delta)^{k,l})$ is not aperiodic.

(b) F-length-synchronicity for a given $F \subseteq R$. In case $(\varphi, \psi)$ is not F-length-synchronous, one can effectively compute a quadruple $(k, l, k', l') \in \mathbb{N}^4_{>0}$ such that there exist $uv, u'v'$ in $\Sigma^\Delta$ and some F-reachable idempotent $e \in O$ such that $\psi(\mathrm{ext}_{u,v}) = \psi(\mathrm{ext}_{u',v'}) = e$, $\Delta(u) > 0$, $\Delta(u') > 0$, $k = |u|, l = |v|$, $k' = |u'|, l' = |v'|$, and $\frac{k}{l} \neq \frac{k'}{l'}$.

(c) F-weakly-length-synchronicity for a given $F \subseteq R$.

## 5.1 Proof outline for Theorem 2.9

Towards proving our main result (Theorem 2.9), given a DVPA $A$, where $L = L(A)$ is a VPL over a visibly pushdown alphabet $\Sigma$, we apply Proposition 5.1 and compute its syntactic Ext-algebra $(R_L, O_L)$ along with its syntactic morphism $(\varphi_L, \psi_L)$ and the subset $\varphi_L(L)$. Then we make the following effective case distinction which immediately implies Theorem 2.9.

1. If $L$ is not weakly length-synchronous, then $L$ is $\mathrm{TC}^0$-hard and hence not in $\mathrm{AC}^0$ (Proposition 5.4 in Section 5.2). Thus, we can output any $m > 1$ since $\mathrm{MOD}_m \leq_{cd} \mathrm{EQUALITY} \leq_{cd} L$ for any $m > 1$.
2. If $L$ is not quasi-aperiodic, then one can effectively compute some $m \ge 2$ such that $\mathrm{MOD}_m \le \mathrm{cd} L$ (Proposition 5.5 in Section 5.2).

3. If $L$ is length-synchronous and $(\varphi_L, \psi_L)$ is quasi-aperiodic, then $L \in \mathrm{AC}^0$ (Theorem 5.7 in Section 5.3).

4. If $L$ is weakly length-synchronous but not length-synchronous, and its syntactic morphism $(\varphi_L, \psi_L)$ is quasi-aperiodic, one can effectively compute vertically visibly pushdown grammars $G_1, \dots, G_m$ generating intermediate VPLs such that $L = \mathrm{cd} \bigcup_{i=1}^m L(G_i)$ (Theorem 5.17 in Section 5.4). Moreover, already if a VPL $L$ is weakly length-synchronous but not length-synchronous, one can effectively compute $k, l \in \mathbb{N}_{>0}$ with $k \ne l$ such that $\mathcal{L}_{k,l} \le \mathrm{cd} L$ (Proposition 5.24 in Section 5.4).

We refer to Section 5.5 for the proof of Corollary 2.11.

## 5.2 Lower bounds

The following visibly pushdown languages are helpful for proving lower bounds.

**Definition 5.2.** Let $L \subseteq \Sigma^\Delta$ be a VPL. For each $e \in O_L$ and for $\# \notin \Sigma$ a fresh internal letter we define

$$L_e = \{u \# v \mid (u, v) \in \mathrm{Con}(\Sigma) : \psi_L(\mathrm{ext}_{u,v}) = e\}$$

and

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

The next lemma shows that both $\varphi_L^{-1}(r)$ and $L_e$ are constant-depth reducible to $L$ in case $r \in R_L$ and $e \in O_L$ are $\varphi_L(L)$-reachable, respectively.

**Lemma 5.3.** Let $L \subseteq \Sigma^\Delta$ be a VPL. Then

* $\varphi_L^{-1}(r) \le \mathrm{cd} L$ for all $\varphi_L(L)$-reachable $r \in R_L$, and

* $L_e \le \mathrm{cd} L$ for all $\varphi_L(L)$-reachable $e \in O_L$.

*Proof.* To show the first point, let us fix some $\varphi_L(L)$-reachable $r \in R_L$. Thus, there exist $w_r \in \Sigma^\Delta$ and $(u_r, v_r) \in \mathrm{Con}(\Sigma)$ such that $\varphi_L(w_r) = r$ and $\varphi_L(u_r w_r v_r) \in \varphi_L(L)$. By definition of the syntactic morphism of $L$ (Definition 3.13) for all $r_1, r_2 \in R_L$ with $r_1 \ne r_2$ there exists some $e_{r_1, r_2} \in O_L$ such that $e_{r_1, r_2}(r_1) \in \varphi_L(L) \Leftrightarrow e_{r_1, r_2}(r_2) \notin \varphi_L(L)$. For each such $e_{r_1, r_2} \in O_L$ fix $(u_{r_1, r_2}, v_{r_1, r_2}) \in \mathrm{Con}(\Sigma)$ with $\psi_L(\mathrm{ext}_{u_{r_1, r_2}, v_{r_1, r_2}}) = e_{r_1, r_2}$.

Hence, for all $w \in \Sigma^*$ we have

$$w \in \varphi_L^{-1}(r) \iff u_r w v_r \in L \wedge \bigwedge_{\substack{r' \in R_L \\ r \ne r'}} u_{r, r'} w v_{r, r'} \in L \leftrightarrow u_{r, r'} w_r v_{r, r'} \in L,$$

thus showing $\varphi_L^{-1}(r) \le \mathrm{cd} L$.

For the second point, let us fix some $\varphi_L(L)$-reachable $e \in O_L$. Fix some $(u_e, v_e) \in \mathrm{Con}(\Sigma)$ such that $\psi_L(\mathrm{ext}_{u_e, v_e}) = e$. Thus, again, there exist $w_e \in \Sigma^\Delta$ and $(u'_e, v'_e) \in \mathrm{Con}(\Sigma)$ such that $\varphi_L(u'_e w_e v_e v'_e) \in \varphi_L(L)$. Again by definition of the syntactic morphism of $L$ (Definition 3.13), for all $e_1, e_2 \in O_L$ with $e_1 \ne e_2$ there exist some $f_{e_1, e_2} \in O_L$ and some $r_{e_1, e_2} \in R_L$ such that
$f_{e_1,e_2}(e_1(r_{e_1,e_2})) \in \varphi_L(L) \Leftrightarrow f_{e_1,e_2}(e_2(r_{e_1,e_2})) \notin \varphi_L(L)$. For each such $f_{e_1,e_2}$ and $r_{e_1,e_2}$ fix, respectively, $(u_{e_1,e_2}, v_{e_1,e_2}) \in \text{Con}(\Sigma)$ and $w_{e_1,e_2} \in \Sigma^\Delta$ such that $\psi_L(\text{ext}_{u_{e_1,e_2},v_{e_1,e_2}}) = f_{e_1,e_2}$ and $\varphi_L(w_{e_1,e_2}) = r_{e_1,e_2}$, respectively. Hence, for all $u \# v \in \Sigma^* \# \Sigma^*$ we have

$$ u\#v \in L_e \iff u'_e u w_e v v'_e \in L \wedge \bigwedge_{\substack{e' \in O_L \\ e \neq e'}} u_{e,e'} u w_{e,e'} v v_{e,e'} \in L \iff u_{e,e'} u_e w_{e,e'} v v_{e,e'} \in L, $$

thus showing $L_e \leq_{cd} L$.

□

The following lower bound has already been sketched in Section 4.

**Proposition 5.4.** If $L$ is not weakly length-synchronous, then $L$ is TC$^0$-hard.

*Proof.* Recall that $(R_L, O_L)$ is the syntactic Ext-algebra of $L$ and $(\varphi_L, \psi_L) : (\Sigma^\Delta, \mathcal{O}(\Sigma^\Delta)) \to (R_L, O_L)$ is its syntactic morphism. Assume that $(\varphi_L, \psi_L)$ is not $\varphi_L(L)$-weakly-length-synchronous.

Assume first there exist $\text{ext}_{u,v}, \text{ext}_{u',v} \in \mathcal{O}(\Sigma^\Delta)$ satisfying that $\psi_L(\text{ext}_{u,v}) = \psi_L(\text{ext}_{u',v})$ that is a $\varphi_L(L)$-reachable idempotent such that $\Delta(u), \Delta(u') > 0$, but $|u| \neq |u'|$. We exploit the fact that $|u| \neq |u'|$ to reduce EQUALITY $= \{w \in \{0,1\}^* : |w|_0 = |w|_1\}$ to $L_{\psi_L(\text{ext}_{u,v})}$. The constant-depth reduction works as follows on input $w \in \{0,1\}^*$:

1. Check if $|w| = 2n$ for some $n \in \mathbb{N}$, reject if it is not the case.

2. Compute $w' = \alpha(w)$, where $\alpha\alpha\{0,1\}^* \to \Sigma^*$ is the length-multiplying morphism satisfying $\alpha(1) = u^{|u'|}$ and $\alpha(0) = u^{|u|}$.

3. Accept whenever $w'\#v^{n(|u|+|u'|)} \in L_{\psi(\text{ext}_{u,v})}$.

Bearing in mind that $0 < \Delta(u) = -\Delta(v) = \Delta(u')$, the latter forms a valid reduction, because given a word $w \in \{0,1\}^*$ of length $2n$ for an $n \in \mathbb{N}$ that contains $k \in [0,2n]$ many 1's, for $w'\#v^{n(|u|+|u'|)}$ to be in $L_{\psi_L(\text{ext}_{u,v})}$, it is in particular required that $w'\#v^{n(|u|+|u'|)}$ is well-matched, so it is necessary and sufficient that

$$ \begin{align*} k \cdot \Delta(u) \cdot |u'| + (2n-k) \cdot \Delta(u') \cdot |u| &= -n \cdot \Delta(v) \cdot (|u| + |u'|) \\ \iff (k-n) \cdot \Delta(u) \cdot |u'| + (n-k) \cdot \Delta(u') \cdot |u| &= 0 \\ \iff (k-n) \cdot \Delta(u) \cdot (|u'| - |u|) &= 0 \\ \iff k &= n. \end{align*} $$

Additionally applying Lemma 5.3 we obtain EQUALITY $\leq_{cd} L_{\psi_L(\text{ext}_{u,v})} \leq_{cd} L$. Assume now there exist $\text{ext}_{u,v}, \text{ext}_{u',v} \in \mathcal{O}(\Sigma^\Delta)$ satisfying that $\psi_L(\text{ext}_{u,v}) = \psi_L(\text{ext}_{u,v'})$ is an $\varphi_L(L)$-reachable idempotent such that $\Delta(u) > 0$ but $|v| \neq |v'|$. Symmetrically, one can prove that we also have EQUALITY $\leq_{cd} L$ in this case.

In conclusion, as EQUALITY is TC$^0$-complete under constant-depth reductions, it follows that $L$ is TC$^0$-hard under constant-depth reductions. □

The following proposition has essentially already been shown in [24, Proposition 135], yet with some inaccuracies (we refer to Section 8) that we fix here.

**Proposition 5.5.** If $L$ is not quasi-aperiodic, then one can effectively compute some $m \geq 2$ such that $\text{MOD}_m \leq_{cd} L$.
**Proof.** Since $L$ is not quasi-aperiodic, by Point 2 (a) Proposition 5.1 one can effectively compute $k, l \in \mathbb{N}$ such that $\psi_L(\mathcal{O}(\Sigma^\Delta)^{k,l})$ is not aperiodic. Thus, one can compute $m \ge 2$ such that $\psi_L(\mathcal{O}(\Sigma^\Delta)^{k,l})$ contains the additive group $G = ([0, m-1], +, 0)$ of $\mathbb{Z}/m\mathbb{Z}$ for some prime number $m$. Moreover, there exist $\text{ext}_{u_0,v_0}, \text{ext}_{u_1,v_1} \in \mathcal{O}(\Sigma^\Delta)^{k,l}$ such that $\psi_L(\text{ext}_{u_0,v_0}) = 0_G$ and $\psi_L(\text{ext}_{u_1,v_1}) = 1_G$. Since $G$ is a group both $\psi_L(\text{ext}_{u_0,v_0})$ and $\psi_L(\text{ext}_{u_1,v_1})$ are $\varphi_L(L)$-reachable. Moreover there exist $xy, z \in \Sigma^\Delta$ such that $xu_0zv_0y \in L$ if, and only if, $xu_1zv_1y \notin L$. Let us assume without loss of generality that $xu_0zv_0y \notin L$ and $xu_1zv_1y \in L$ (the case when $xu_0zv_0y \in L$ and $xu_1zv_1y \notin L$ can be proven analogously). Let $h_\uparrow, h_\downarrow : \{0, 1\}^* \to \Sigma^*$ be the length-multiplying morphisms satisfying $h_\uparrow(i) = u_i$ and $h_\downarrow(i) = v_i$ for all $i \in \{0, 1\}$. We claim that

$$w \in \mathrm{MOD}_m \iff \bigwedge_{i=1}^{m-1} xh_\uparrow(w)^{i^{m-2}}zh_\downarrow(w^R)^{i^{m-2}}y \notin L.$$

Let $w_i = xh_\uparrow(w)^{i^{m-2}}zh_\downarrow(w^R)^{i^{m-2}}y$ for all $i \in [1, m-1]$. Observe that $w_i \in \Sigma^\Delta$ for all $i \in [1, m-1]$ directly by definition of the morphisms $h_\uparrow$ and $h_\downarrow$.

To show the above equivalence, let us first assume that $|w|_1$ is divisible by $m$. Then we have $\psi_L(\text{ext}_{h_\uparrow(w),h_\downarrow(w^R)}) = \psi_L(\text{ext}_{u_0,v_0}) = 0_G$, and consequently $\psi_L(\text{ext}_{h_\uparrow(w)^{i^{m-2}},h_\downarrow(w)^{i^{m-2}}}) = 0_G$ for all $i \in [1, m-1]$. It follows $w_i \notin L$ for all $i \in [1, m-1]$, as desired. Conversely, assume that $|w|_1$ is not divisible by $m$, i.e. $|w|_1 \equiv i \mod m$ for some $i \in [1, m-1]$. Hence $\psi_L(\text{ext}_{h_\uparrow(w),h_\downarrow(w^R)}) = i_G \neq 0_G$ and thus $\psi_L(\text{ext}_{h_\uparrow(w)^{i^{m-2}},h_\downarrow(w^R)^{i^{m-2}}}) = (i^{m-1} \mod m)_G = 1_G$ by Fermat's Little Theorem. Hence $w_i \in L$ as required.

Altogether we obtain $\mathrm{MOD}_m \leq_{cd} L$. $\square$

### 5.2.1 The non-solvable case

In this additional section we prove a stronger lower bound, namely when the syntactic morphism not only is not quasi-aperiodic but the syntactic Ext-algebra not solvable. For this we revisit solvable groups and introduce solvable Ext-algebras.

Let $G$ be a finite group. The word problem for $G$ is the question, given a word $w_1 \cdots w_n$ over $G$, to decide if their product $w_1 \cdots w_n$ in $G$ evaluates to $1_G$. The commutator of $g, h \in G$ is $ghg^{-1}h^{-1} \in G$, denoted by $[g, h]$. The commutator subgroup $[G, G]$ of $G$ is the subgroup of $G$ that is generated by the commutators of $G$. We say that $G$ is perfect if $G = [G, G]$. We say that $G$ is solvable if in the series of commutator subgroups (a.k.a. derived series) $G^{(0)}, G^{(1)}, \dots$ a trivial group is contained, where $G^{(0)} = G$ and $G^{(i+1)} = [G^{(i)}, G^{(i)}]$ for all $i \in \mathbb{N}$. Thus, note that any non-solvable finite group contains a perfect subgroup.

We say the Ext-algebra $(R, O)$ is solvable if all subsets of $R$ or $O$ that are groups (under the multiplication of $R$, resp. of $O$) are solvable. It is worth mentioning that one can prove that if $(\varphi, \psi) : (\Sigma^\Delta, \mathcal{O}(\Sigma^\Delta)) \to (R, O)$ is quasi-aperiodic, then $(R, O)$ is solvable. In fact, one can prove that if $(\varphi, \psi)$ is quasi-aperiodic, then $(R, O)$ must contain only Abelian groups.

Our proof that $L$ is $\mathbb{N}\mathcal{C}^1$-hard (and thus $\mathbb{T}\mathcal{C}^0$-hard) when $(R_L, O_L)$ is not solvable can be reduced to the case for words $[4]$, by showing that already $\psi_L(\mathcal{O}(\Sigma^\Delta)^{k,l})$ contains such a non-solvable group for some fixed $k, l \ge 0$.

**Proposition 5.6.** If $(R_L, O_L)$ is not solvable, then $L$ is $\mathbb{N}\mathcal{C}^1$-hard and thus not in $\mathbb{A}\mathcal{C}^0$.

Before we prove the proposition we remark that not every subset $G \subseteq R_L$ (resp. $G \subseteq O_L$) that is a group is necessarily a submonoid of $R_L$ (resp. $O_L$); in particular the neutral element of $G$ need not necessarily be the neutral element of $O_L$. Indeed, for instance assume $R_L = \{1, a, b\}$ where
$1 \cdot r = 1 \cdot r = r$ for all $r \in R$ and where $a \cdot b = b \cdot a = b$ and $a \cdot a = b \cdot b = a$; the subset $\{a, b\}$ forms the additive group of $\mathbb{Z}/2\mathbb{Z}$ with neutral element $a$. It is also worth mentioning that since $R$ is (isomorphic to) a submonoid of $O$ we could have equivalently defined an Ext-algebra to be solvable if all subsets of $O$ that are groups are solvable.

**Proof of Proposition 5.6.** Assume $(R_L, O_L)$ is not solvable. Then there exists a subset $G \subseteq O_L$, where $G$ is a non-trivial perfect group, i.e. $G = [G, G]$. Let $\omega$ be the idempotent power of $G$. For all $g, h \in G$ there exist $\mathrm{ext}_{u_g, v_g}, \mathrm{ext}_{u_h, v_h} \in \mathcal{O}(\Sigma^\Delta)$ such that

$$[g, h] = ghg^{-1}h^{-1} = ghg^{\omega-1}h^{\omega-1} = \psi_L \left( \mathrm{ext}_{u_g u_h u_g^{\omega-1} u_h^{\omega-1}, v_h^{\omega-1} v_g^{\omega-1} v_h v_g} \right)$$

and $1_G = g^{\omega}h^{\omega} = \psi_L(\mathrm{ext}_{u_g^{\omega}u_h^{\omega}, v_h^{\omega}v_g^{\omega}})$. Therefore, for all $g, h \in G$ we have

$$[g, h] = \psi_L \left( \mathrm{ext}_{u_g u_h u_g^{\omega-1} u_h^{\omega-1}, v_h^{\omega-1} v_g^{\omega-1} v_h v_g} \circ \bigcirc_{\substack{(g', h') \in G^2 \\ (g', h') \neq (g, h)}} \mathrm{ext}_{u_g^{\omega} u_h^{\omega}, v_h^{\omega}, v_g^{\omega}} \right).$$

Hence, $\{[g, h] | g, h \in G\} \subseteq \mathcal{O}(\Sigma^\Delta)^{k,l}$ for

$$k = \sum_{(g,h) \in G^2} (|u_g| + |u_h|) \cdot \omega \quad \text{and} \quad l = \sum_{(g,h) \in G^2} (|v_h| + |v_g|) \cdot \omega .$$

Since $G = [G, G]$ every element of $G$ can be written as the product of at most $|G|$ elements in $\{[g, h] | g, h \in G\}$ and, in fact, even as the product of exactly $|G|$ elements in $\{[g, h] | g, h \in G\}$, since it contains the identity $1_G$. Thus, we can conclude that $G \subseteq \psi_L(\mathcal{O}(\Sigma^\Delta))^{k \cdot |G|, l \cdot |G|}$. Since the word problem of any non-solvable finite group is $\mathrm{NC}^1$-hard by [4] and $G \subseteq \psi_L(\mathcal{O}(\Sigma^\Delta))^{k \cdot |G|, l \cdot |G|}$, it follows that the word problem for $G$ is constant-depth reducible to $L$. Hence $L$ is $\mathrm{NC}^1$-hard and in particular $\mathrm{TC}^0$-hard. $\square$

## 5.3 In $\mathrm{AC}^0$: Length-synchronous and quasi-aperiodic

This section is devoted to the following theorem.

**Theorem 5.7.** If $L$ is length-synchronous and $(\varphi_L, \psi_L)$ is quasi-aperiodic, then $L$ is in $\mathrm{FO}[+]$ and thus in $\mathrm{AC}^0$.

For the rest of this section let us fix a VPL $L$, its syntactic Ext-algebra $(R_L, O_L)$, and its syntactic morphism $(\varphi_L, \psi_L) : (\Sigma^\Delta, \mathcal{O}(\Sigma^\Delta)) \to (R_L, O_L)$.

Before we explain our proof strategy we introduce approximate matchings and horizontal and vertical evaluation languages. Approximate matchings generalize the classical matching relation on well-matched words with respect to our VPL $L$ in the sense that they are subsets of the matching relation but must equal the matching relation on all those words that are in $L$. Approximate matchings in the context of visibly pushdown languages were introduced by Ludwig [24]. We then introduce suitably padded word languages mimicking the evaluation problem of the horizontal monoid $R_L$ and the vertical monoid $O_L$, respectively.

**Approximate matchings.** For any word $w \in \Sigma^*$, we say that two positions $i, j \in [1, |w|]$ in $w$ are matched whenever $i < j$, $w_i \in \Sigma_{\mathrm{call}}$, $w_j \in \Sigma_{\mathrm{ret}}$ and $w_{i+1} \cdots w_{j-1} \in \Sigma^\Delta$; we also say that $i$ is
matched to j in w. Observe that a word w over Σ is well-matched if and only if for each position i ∈ [1, |w|],

• if i ∈ Σ<sub>call</sub>, then there exists a position j ∈ [1, |w|] such that i is matched to j in w;

• if i ∈ Σ<sub>ret</sub>, then there exists a position j ∈ [1, |w|] such that j is matched to i in w.

Given a word w ∈ Σ<sup>Δ</sup>, we denote by M<sup>Δ</sup>(w) its matching relation (or matching), that is the relation {(i, j) ∈ [1, |w|]<sup>2</sup> | i is matched to j in w} . An approximate matching relative to L ⊆ Σ<sup>Δ</sup> is a function M: Σ<sup>*</sup> → N<sub>≥0</sub><sup>2</sup> such that M(w) = M<sup>Δ</sup>(w) for all w ∈ L and M(w) ⊆ M<sup>Δ</sup>(w) for all w ∈ Σ<sup>*</sup> \ L.

**Horizontal and vertical evaluation languages.** For all $k \in \mathbb{N}$, we define

$$ \mathcal{O}(\Sigma^\Delta)^{k,*} = \{\mathrm{ext}_{u,v} \in \mathcal{O}(\Sigma^\Delta) : |u| = k\} \quad \text{and} \quad \mathcal{O}(\Sigma^\Delta)^{*,k} = \{\mathrm{ext}_{u,v} \in \mathcal{O}(\Sigma^\Delta) : |v| = k\}. $$

We also define $\mathcal{O}(\Sigma^\Delta)_\uparrow = \{\mathrm{ext}_{u,v} \in \mathcal{O}(\Sigma^\Delta) | \Delta(u) > 0\}$ and finally for all $k \in \mathbb{N}$, we define

$$ \mathcal{O}(\Sigma^\Delta)_\uparrow^{k,*} = \mathcal{O}(\Sigma^\Delta)^{k,*} \cap \mathcal{O}(\Sigma^\Delta)_\uparrow \quad \text{and} \quad \mathcal{O}(\Sigma^\Delta)_\uparrow^{*,k} = \mathcal{O}(\Sigma^\Delta)^{*,k} \cap \mathcal{O}(\Sigma^\Delta)_\uparrow. $$

Consider the alphabets $\Gamma_{\varphi_L} = \varphi_L(\Sigma^\Delta \setminus \{\varepsilon\}) \cup \{\$\}$ and $\Gamma_{\psi_L} = \psi_L(\mathcal{O}(\Sigma^\Delta)_\uparrow) \cup \{\$\}$ for a letter $\$ \notin R_L \cup O_L$. We also define

$$ \mathcal{V}_{\varphi_L} = \{\$^k s \mid k \in \mathbb{N}, s \in \varphi_L(\Sigma^{k+1})\}^* \quad \text{and} \quad \mathcal{V}_{\psi_L} = \{\$^k f \mid k \in \mathbb{N}, f \in \psi_L(\mathcal{O}(\Sigma^\Delta)_\uparrow^{k+1,*})\}^*. $$

Define the $\varphi_L$-evaluation morphism eval<sub>ϕ<sub>L</sub></sub>: $\Gamma_{\varphi_L}^* \to R_L$ by eval<sub>ϕ<sub>L</sub></sub>(s) = s for all s ∈ $\varphi_L(\Sigma^\Delta \setminus \{\varepsilon\})$ and eval<sub>ϕ<sub>L</sub></sub>($\$) = 1_R$. Similarly, define the $\psi_L$-evaluation morphism eval<sub>ψ<sub>L</sub></sub>: $\Gamma_{\psi_L}^* \to O_L$ by eval<sub>ψ<sub>L</sub></sub>(f) = f for all f ∈ $\psi_L(\mathcal{O}(\Sigma^\Delta)_\uparrow)$ and eval<sub>ψ<sub>L</sub></sub>($\$) = 1_{O_L}$. Finally, for all $r \in R_L$, we set

$$ \mathcal{E}_{\varphi_L, r} = \mathcal{V}_{\varphi_L} \cap \mathrm{eval}_{\varphi_L}^{-1}(r) $$

and for all $e \in O_L$, we set

$$ \mathcal{E}_{\psi_L, e} = \mathcal{V}_{\psi_L} \cap \mathrm{eval}_{\psi_L}^{-1}(e). $$

### 5.3.1 Strategy for the proof of Theorem 5.7

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

1. Lemma 5.9: $\mathcal{V}_{\varphi_L}$ and $\mathcal{V}_{\psi_L}$ are regular languages whose syntactic morphisms are quasi-aperiodic.

2. Proposition 5.10: Let L be a VPL whose syntactic morphism $(\varphi_L, \psi_L)$ is quasi-aperiodic.

• For all $r \in R_L$, the language $\mathcal{E}_{\varphi_L, r}$ is regular and its syntactic morphism is quasi-aperiodic.

• For all $e \in O_L$, if for each $\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$ we have that $\mathcal{R}_f = \{(u, v) \in \mathrm{Con}(\Sigma) | \psi_L(\mathrm{ext}_{u,v}) = f\}$ is length-synchronous, then $\mathcal{E}_{\psi_L, e}$ is a regular language whose syntactic morphism is quasi-aperiodic.

3. Proposition 5.12: If $L \subseteq \Sigma^\Delta$ is length-synchronous, then there exists an $\mathrm{FO}_\Sigma[+]$-formula $\mu(x, y)$ such that $M: \Sigma^* \to N_{>0}^2$ defined by $M(w) = \{(i, j) \in [1, |w|]^2 | w \models \mu(i, j)\}$ for all $w \in \Sigma^*$ is an approximate matching relative to L.
4. Proposition 5.16: Assume a VPL $L$ has bounded nesting depth and

* $\mathcal{E}_{\varphi_{L,r}}$ is a regular language whose syntactic morphism is quasi-aperiodic for all $\varphi_{L}(L)$-reachable $r \in R_{L}$, and

* $\mathcal{E}_{\psi_{L,e}}$ is a regular language whose syntactic morphism is quasi-aperiodic for all $\varphi_{L}(L)$-reachable $e \in O_{L}$.

Then there exists an $\mathbf{FO}_{\Sigma, \rightsquigarrow}[+]$-sentence $\eta$ such that for any approximate matching $M$ relative to $L$, we have $w \in L$ if, and only if, $(w, M(w)) \models \eta$ for all $w \in \Sigma^{*}$.

Let us argue that Points 2, 3 and 4 indeed imply Theorem 5.7 (Point 1 will be used in the proof of Point 2). Length-synchronicity of $L$ implies weak length-synchronicity of $L$ and thus bounded nesting depth of $L$ (Proposition 4.14). Point 2 implies the other assumptions of Point 4: length-synchronicity of $L$ means by definition that for each $\varphi_{L}(L)$-reachable idempotent $f \in O_{L}$ we have that $\mathcal{R}_{f} = \{(u, v) \in \mathbf{Con}(\Sigma) \mid \psi_{L}(\mathrm{ext}_{u,v}) = f\}$ is length-synchronous, so Point 2 implies that $\mathcal{E}_{\varphi_{L,r}}$ and $\mathcal{E}_{\psi_{L,e}}$ are quasi-aperiodic for all $r \in R_{L}$ and all $e \in O_{L}$, respectively. Finally, combining the $\mathbf{FO}_{\Sigma, \rightsquigarrow}[+]$-sentence of Point 4 with the $\mathbf{FO}_{\Sigma}[+]$-formula given by Point 3 that defines an approximate matching relative to $L$ yields an $\mathbf{FO}_{\Sigma}[+]$-sentence defining $L$, thus proving Theorem 5.7.

### 5.3.2 $\mathcal{V}_{\varphi_L}$ and $\mathcal{V}_{\psi_L}$ are quasi-aperiodic (Proof of Point 1)

Before proving Point 1 in the proof strategy for Theorem 5.7 we require the following auxiliary lemma. It provides an important periodicity property of Ext-algebra morphisms.

**Lemma 5.8.** *The following periodicity holds:*

1. There exist $t \in \mathbb{N}$ and $p \in \mathbb{N}_{>0}$ such that $\varphi_{L}(\Sigma^{\Delta} \cap \Sigma^{i}) = \varphi_{L}(\Sigma^{\Delta} \cap \Sigma^{j})$ for all $i, j \in \mathbb{N}$ satisfying $i, j \ge t$ and $i \equiv j \pmod{p}$.

2. There exist $t \in \mathbb{N}$ and $p \in \mathbb{N}_{>0}$ such that $\psi_{L}(\mathcal{O}(\Sigma^{\Delta})_{\uparrow}^{i,*}) = \psi_{L}(\mathcal{O}(\Sigma^{\Delta})_{\uparrow}^{j,*})$ for all $i, j \in \mathbb{N}$ satisfying $i, j \ge t$ and $i \equiv j \pmod{p}$.

3. There exist $t \in \mathbb{N}$ and $p \in \mathbb{N}_{>0}$ such that $\psi_{L}(\mathcal{O}(\Sigma^{\Delta})_{\uparrow}^{*,i}) = \psi_{L}(\mathcal{O}(\Sigma^{\Delta})_{\uparrow}^{*,j})$ for all $i, j \in \mathbb{N}$ satisfying $i, j \ge t$ and $i \equiv j \pmod{p}$.

*Proof.* To prove Point 1 recall that $\varphi_{L}^{-1}(r)$ is a VPL and hence a context-free language for all $r \in R_{L}$. By Parikh's Theorem [14, Section 3] it follows that $S_{r} = \{|w| : w \in \Sigma^{\Delta}, \varphi_{L}(w) = r\} \subseteq \mathbb{N}$ is a semilinear set for all $r \in R_{L}$. It follows that for all $U \subseteq R_{L}$ the set $S_{U} = \{|w| : w \in \Sigma^{\Delta}, \varphi_{L}(w) \in U\} \subseteq \mathbb{N}$ is semilinear since semilinear sets are closed under union. Point 1 follows immediately from this observation.

Next we prove Point 2, Point 3 can be proven analogously. According to Lemma 6.4 in Section 6 for $\# \notin \Sigma$ the language $L_{e} = \{u\#v \mid uv \in \Sigma^{\Delta} : \psi_{L}(\mathrm{ext}_{u,v}) = e\}$ is a VPL for all $e \in O_{L}$. As the language $K = \{u\#v \mid u, v \in \Sigma^{\Delta}\}$ is obviously a VPL, it follows that for all $e \in O_{L}$ the language

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

is a VPL as well. By Lemma 6.5 in Section 6 the set

$$S_e = \{(k, l) \in \mathbb{N} \times \mathbb{N} \mid \exists u \in \Sigma^k, v \in l : u \# v \in L_{e\uparrow}\}$$

is semilinear as well for all $e \in O_{L}$. As a consequence we obtain that for all $Y \subseteq O_{L}$ the set

$$S_Y = \{(k, l) \in \mathbb{N} \times \mathbb{N} \mid \exists u \in \Sigma^k, v \in \Sigma^l, e \in Y : u \# v \in L_{e\uparrow}\} \subseteq \mathbb{N} \times \mathbb{N}$$
is semilinear as well since semilinear sets are closed under union. Since for all $Y \subseteq O_L$ the set $\{k \in \mathbb{N} \mid \psi_L(O(\Sigma^\Delta)_\uparrow^{k,*} = Y\}$ is nothing but the projection of $S_Y$ onto the first component and semilinear sets are closed under projection, Point 2 follows. $\square$

The following lemma holds irrespective of whether the syntactic morphism $(\varphi_L, \psi_L)$ of $L$ is quasi-aperiodic or not.

**Lemma 5.9.** $\mathcal{V}_{\varphi_L}$, $\mathcal{V}_{\psi_L}$ are regular languages whose syntactic morphisms are quasi-aperiodic.

*Proof.* Take $t \in \mathbb{N}$ and $p \in \mathbb{N}_{>0}$ given by Lemma 5.8 such that $\psi_L(O(\Sigma^\Delta)_\uparrow^{i,*}) = \psi_L(O(\Sigma^\Delta)_\uparrow^{j,*})$ for all $i, j \in \mathbb{N}$ satisfying $i, j \ge t$ and $i \equiv j \pmod p$. Define $\theta_{t,p}: \mathbb{N} \to \mathbb{N}$ as

$$ \theta_{t,p}(n) = \begin{cases} n & \text{if } n < t \\ \min\{n' \in \mathbb{N} \mid n' \ge t \wedge n' \equiv n \pmod p\} & \text{otherwise} \end{cases} $$

for all $n \in \mathbb{N}$. Take $M$ to be the syntactic monoid of $\mathcal{V}_{\psi_L}$ and $h: \Gamma_{\psi_L}^* \to M$ to be its syntactic morphism.

If there exists $f \in \psi_L(O(\Sigma^\Delta)_\uparrow)$ and $k \in \mathbb{N}$ such that $\$^k f \notin \mathcal{V}_{\psi_L}$, let us fix some $f_\perp$ and $k_\perp$ that satisfy this. Observe that for all $k \in \mathbb{N}$, we have that $h(\$^k) = h(\$^{\theta_{t,p}(k)})$. Further, for all $n \in \mathbb{N}_{>0}$, $k_1, \dots, k_{n+1} \in \mathbb{N}$ and $f_1, \dots, f_n \in \psi_L(O(\Sigma^\Delta)_\uparrow)$, we have $h(\$^{k_1}f_1 \cdots \$^{k_n}f_n \$^{k_{n+1}}) = h(\$^{\theta_{t,p}(k_1)}f_1 \alpha \$^{\theta_{t,p}(k_{n+1})})$, where

$$ \alpha = \begin{cases} \varepsilon & \text{if } \$$^{k_2}f_2 \cdots \$^{k_n}f_n \in \mathcal{V}_{\psi_L} \\ \$$^{k_\perp}f_\perp & \text{otherwise.} \end{cases} $$

Therefore, $M$ is finite and thus $\mathcal{V}_{\psi_L}$ is regular. Let $l \in \mathbb{N}_{>0}$ be the stability index of $h$ and take $q \in \mathbb{N}_{>0}$ such that $q \cdot l \ge t$ and $q \cdot l \equiv 0 \pmod p$. By definition, we have $h(\Gamma_{\psi_L}^l) = h(\Gamma_{\psi_L}^{q \cdot l})$. Thus, to show that $h$ is quasi-aperiodic it is sufficient to prove that for all $m \in h(\Gamma_{\psi_L}^{q \cdot l})$, we have $m^2 = m^3$. Indeed, given $m \in h(\Gamma_{\psi_L}^{q \cdot l})$, only the following three cases can occur.

1. $m = h(\$^{q \cdot l})$. In this case, we have

$$ m^2 = h(\$^{2 \cdot q \cdot l}) = h(\$^{\theta_{t,p}(2 \cdot q \cdot l)}) = h(\$^{\theta_{t,p}(q \cdot l)}) = h(\$^{q \cdot l}) = m, $$

where the third equality follows from $\theta_{t,p}(2 \cdot q \cdot l) = \theta_{t,p}(q \cdot l)$.

2. $m = h(\$^{k_1}f\$^{k_\perp}f_\perp\$^{k_2})$ for $f \in \psi_L(O(\Sigma^\Delta)_\uparrow)$ and $k_1, k_2 \in \mathbb{N}$ satisfying $\theta_{t,p}(k_1) = k_1$ and $\theta_{t,p}(k_2) = k_2$. In this case, we have

$$ m^2 = h(\$^{k_1}f\$^{k_\perp}f_\perp\$^{k_1+k_2}f\$^{k_\perp}f_\perp\$^{k_2}) = h(\$^{k_1}f\$^{k_\perp}f_\perp\$^{k_2}) = m, $$

where the second equality follows from $\$^{k_\perp}f_\perp\$^{k_1+k_2}f\$^{k_\perp}f_\perp \notin \mathcal{V}_{\psi_L}$.

3. $m = h(\$^{k_1}f\$^{k_2})$ for $f \in \psi_L(O(\Sigma^\Delta)_\uparrow)$ and $k_1, k_2 \in \mathbb{N}$ satisfying $\theta_{t,p}(k_1) = k_1$ and $\theta_{t,p}(k_2) = k_2$. If $f \in \psi_L(O(\Sigma^\Delta)_\uparrow^{k_1+k_2+1,*})$, then

$$ m^2 = h(\$^{k_1}f\$^{k_1+k_2}f\$^{k_2}) = h(\$^{k_1}f\$^{k_2}) = m $$

because $\$^{k_1+k_2}f \in \mathcal{V}_{\psi_L}$. Otherwise, $f \notin \psi_L(O(\Sigma^\Delta)_\uparrow^{k_1+k_2+1,*})$ and then

$$ m^2 = h(\$^{k_1}f\$^{k_1+k_2}f\$^{k_2}) = h(\$^{k_1}f\$^{k_\perp}f_\perp\$^{k_2}) $$
because $\$^{k_1+k_2}f \notin \mathcal{V}_{\psi_L}$, so

$$m^3 = h(\$^{k_1}f\$^{k_\perp}f_\perp\$^{k_1+k_2}f\$^{k_2}) = h(\$^{k_1}f\$^{k_\perp}f_\perp\$^{k_2}) = m^2$$

because $\$^{k_\perp}f_\perp\$^{k_1+k_2}f \notin \mathcal{V}_{\psi_L}$.

Therefore, $\mathcal{V}_{\psi_L}$ is a regular language whose syntactic morphism is quasi-aperiodic. $\square$

### 5.3.3 Quasi-aperiodicity of evaluation languages $\mathcal{E}_{\varphi_L,r}$ and $\mathcal{E}_{\psi_L,e}$ (Proof of Point 2)

One important consequence of Lemma 5.9 is that for all $r \in R_L$ and $e \in O_L$, the languages $\mathcal{E}_{\varphi_L,r}$ and $\mathcal{E}_{\psi_L,e}$ are in fact regular languages. The following proposition gives conditions under which those languages have moreover quasi-aperiodic syntactic morphisms when the syntactic morphism of $L$ itself is.

**Proposition 5.10.** Let $L$ be a VPL whose syntactic morphism $(\varphi_L, \psi_L)$ is quasi-aperiodic.

* For all $r \in R_L$, the language $\mathcal{E}_{\varphi_L,r}$ is regular and its syntactic morphism is quasi-aperiodic.

* For all $e \in O_L$, if for each $\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^1$ we have that $\mathcal{R}_f = \{(u, v) \in \text{Con}(\Sigma) \mid \psi_L(\text{ext}_{u,v}) = f\}$ is length-synchronous, then $\mathcal{E}_{\psi_L,e}$ is a regular language whose syntactic morphism is quasi-aperiodic.

*Proof.* We already know that for all $r \in R_L$ and $e \in O_L$, the languages $\mathcal{E}_{\varphi_L,r}$ and $\mathcal{E}_{\psi_L,e}$ are regular. To prove the lemma, we then just have to prove that

* if there exists $r \in R_L$ such that the syntactic morphism of $\mathcal{E}_{\varphi_L,r}$ is not quasi-aperiodic, then there exists $k \in \mathbb{N}$ such that $\varphi(\Sigma^\Delta \cap \Sigma^k)$ contains a semigroup that is not aperiodic;

* if there exists $e \in O_L$ such that the syntactic morphism of $\mathcal{E}_{\psi_L,e}$ is not quasi-aperiodic and for each $\varphi_L(L)$-reachable idempotent $f \in O_L$ such that there exist $f', f'' \in O_L$ satisfying $e = f' \circ f \circ f''$ we have that $\mathcal{R}_f = \{(u, v) \in \Sigma^* \times \Sigma^* \mid uv \in \Sigma^\Delta, \Delta(u) > 0, \psi_L(\text{ext}_{u,v}) = f\}$ is length-synchronous, then there exist $k, l \in \mathbb{N}$ such that $\psi_L(\mathcal{O}(\Sigma^\Delta)^{k,l})$ contains a semigroup that is not aperiodic.

Indeed, the first point allows to conclude that $(\varphi_L, \psi_L)$ is not quasi-aperiodic, since if there exists a non-aperiodic semigroup $S$ contained in $\varphi_L(\Sigma^\Delta \cap \Sigma^k)$, then $\{\text{left}_s \mid s \in S\}$ is a semigroup contained in $\psi_L(\mathcal{O}(\Sigma^\Delta)^{k,0})$ (because for each $s \in S$, there exists $w \in \Sigma^\Delta \cap \Sigma^k$ satisfying $\varphi_L(w) = s$, so that $\psi_L(\text{ext}_{w,\varepsilon}) = \text{left}_{\varphi_L(w)} = \text{left}_s$). But this semigroup is non-aperiodic as well, since as $S$ is non-aperiodic, it must be that for all $i \in \mathbb{N}_{>0}$, there exists $s \in S$ such that $s^i \neq s^{i+1}$, so that $\text{left}_s^i \neq \text{left}_s^{i+1}$.

We only prove the second point, the first point can be proved in a similar way by leaving out the last paragraph of the following proof, that is the sole place where we need, given an $e \in O_L$, length-synchronicity of $\mathcal{R}_f$ for each $\varphi_L(L)$-reachable idempotent $f \in O_L$ such that there exist $f', f'' \in O_L$ satisfying $e = f' \circ f \circ f''$.

Take $t \in \mathbb{N}$ and $p \in \mathbb{N}_{>0}$ given by Lemma 5.8 such that $\psi_L(\mathcal{O}(\Sigma^\Delta)^{i,*}) = \psi_L(\mathcal{O}(\Sigma^\Delta)^{j,*})$ for all $i, j \in \mathbb{N}$ satisfying $i, j \ge t$ and $i \equiv j \pmod p$.

Assume there exists $e \in O_L$ such that the syntactic morphism of $\mathcal{E}_{\psi_L,e}$ is not quasi-aperiodic. Take $M$ to be the syntactic monoid of $\mathcal{E}_{\psi_L,e}$ and $h: \Gamma_{\psi_L}^* \to M$ to be its syntactic morphism. Let

<footnote n="1">¹In the terminology of Green's relations, to be introduced in the proof of Proposition 5.24, this is equivalent to the fact that $e \le_j f$.</footnote>
$s \in \mathbb{N}_{>0}$ be the stability index of $h$ and let $\omega \ge 2$ be a multiple both of the idempotent power of $M$ and the idempotent power of $O_L$. Non-quasi-aperiodicity of $h$ implies that there exists $g \in h(\Gamma_{\psi_L}^s)$ satisfying $g^\omega \neq g^{\omega+1}$.

By definition of the stability index, there exists $w \in \Gamma_{\psi_L}^{q \cdot s}$ for $q \in \mathbb{N}_{>0}$ such that $q \cdot s \ge t$ and $q \cdot s \equiv 0 \pmod{p}$ satisfying $h(w) = g$. Since $t \le q \cdot s \le q \cdot s \cdot \omega \le q \cdot s \cdot (\omega+1)$ and $q \cdot s \equiv q \cdot s \cdot \omega \equiv q \cdot s \cdot (\omega+1) \pmod{p}$, we cannot have $w = \mathbb{F}^{q \cdot s}$, for otherwise we would have $g^\omega = h(\mathbb{F}^{q \cdot s \cdot \omega}) = h(\mathbb{F}^{q \cdot s \cdot (\omega+1)}) = g^{\omega+1}$ because $\psi_L(\mathcal{O}(\Sigma^\Delta)_{\uparrow}^{q \cdot s \cdot \omega+k+1,*}) = \psi_L(\mathcal{O}(\Sigma^\Delta)_{\uparrow}^{q \cdot s \cdot (\omega+1)+k+1,*})$ for all $k \in \mathbb{N}$. Therefore, we have $w = \mathbb{F}^{k_1} f_1 \cdots \mathbb{F}^{k_n} f_n \mathbb{F}^{k_{n+1}}$ for $n \in \mathbb{N}_{>0}$, $k_1, \dots, k_{n+1} \in \mathbb{N}$ and $f_1, \dots, f_n \in \psi_L(\mathcal{O}(\Sigma^\Delta)_{\uparrow})$. Since $g^\omega \neq g^{\omega+1}$, there exist $x, y \in \Gamma_{\psi_L}^*$ such that either $xw^\omega y \in \mathcal{E}_{\psi_L, e}$ and $xw^{\omega+1} y \notin \mathcal{E}_{\psi_L, e}$, or $xw^\omega y \notin \mathcal{E}_{\psi_L, e}$ and $xw^{\omega+1} y \in \mathcal{E}_{\psi_L, e}$. Assume the first case holds. Then we have $x = x' \mathbb{F}^{k_x}$ and $y = \mathbb{F}^{k_y} y'$ with $k_x, k_y \in \mathbb{N}$ and $x', y' \in \Gamma_{\psi_L}^*$ satisfying $x', \mathbb{F}^{k_x+k_1} f_1, \mathbb{F}^{k_2} f_2, \dots, \mathbb{F}^{k_n} f_n, \mathbb{F}^{k_{n+1}+k_1} f_1, \mathbb{F}^{k_{n+1}+k_y} y' \in \mathcal{V}_{\psi_L}$ and $\mathrm{eval}_{\psi_L}(x') \circ (f_1 \circ \cdots \circ f_n)^\omega \circ \mathrm{eval}_{\psi_L}(y') = e$. Therefore, we also have $xw^{\omega+1} y \in \mathcal{V}_{\psi_L}$, hence since $xw^{\omega+1} y \notin \mathcal{E}_{\psi_L, e}$ we necessarily have

$$e = \mathrm{eval}_{\psi_L}(x') \circ (f_1 \circ \cdots \circ f_n)^\omega \circ \mathrm{eval}_{\psi_L}(y') \\ \neq \mathrm{eval}_{\psi_L}(xw^{\omega+1} y) = \mathrm{eval}_{\psi_L}(x') \circ (f_1 \circ \cdots \circ f_n)^{\omega+1} \circ \mathrm{eval}_{\psi_L}(y').$$

Thus we have $(f_1 \circ \cdots \circ f_n)^\omega \neq (f_1 \circ \cdots \circ f_n)^{\omega+1}$ and $\mathbb{F}^{k_{n+1}+k_1} f_1 \mathbb{F}^{k_2} f_2 \cdots \mathbb{F}^{k_n} f_n \in \mathcal{V}_{\psi_L}$. This is also true for the case when $xw^\omega y \notin \mathcal{E}_{\psi_L, e}$ and $xw^{\omega+1} y \in \mathcal{E}_{\psi_L, e}$.

Therefore, we have $(f_1 \circ \cdots \circ f_n)^\omega \neq (f_1 \circ \cdots \circ f_n)^{\omega+1}$ with $(f_1 \circ \cdots \circ f_n)^i \in \psi_L(\mathcal{O}(\Sigma^\Delta)_{\uparrow}^{q \cdot s \cdot i,*}) = \psi_L(\mathcal{O}(\Sigma^\Delta)_{\uparrow}^{q \cdot s,*})$ for each $i \in \mathbb{N}_{>0}$ because $k_{n+1}+k_1+\cdots+k_n+n = q \cdot s \ge t$ and $k_{n+1}+k_1+\cdots+k_n+n = q \cdot s \equiv 0 \pmod{p}$. But given $\omega'$ the idempotent power of $\{(f_1 \circ \cdots \circ f_n)^i \mid i \in \mathbb{N}_{>0}\}$, we have that $(f_1 \circ \cdots \circ f_n)^\omega = (f_1 \circ \cdots \circ f_n)^{\omega\omega'} = (f_1 \circ \cdots \circ f_n)^{\omega'},$ so that $(f_1 \circ \cdots \circ f_n)^{\omega'} \neq (f_1 \circ \cdots \circ f_n)^{\omega'+1}$, hence $\{(f_1 \circ \cdots \circ f_n)^i \mid i \in \mathbb{N}_{>0}\}$ is not aperiodic.

Assume additionally that for each $\varphi_L(L)$-reachable idempotent $f \in O_L$ such that there exist $f', f'' \in O_L$ satisfying $e = f' \circ f \circ f''$ we have that $\mathcal{R}_f = \{(u, v) \in \Sigma^* \times \Sigma^* \mid uv \in \Sigma^\Delta, \Delta(u) > 0, \psi_L(\mathrm{ext}_{u,v}) = f\}$ is length-synchronous. For each $i \in \mathbb{N}_{>0}$, let $\mathrm{ext}_{u_i, v_i} \in \psi_L(\mathcal{O}(\Sigma^\Delta)_{\uparrow}^{q \cdot s,*})$ such that $\psi_L(\mathrm{ext}_{u_i, v_i}) = (f_1 \circ \cdots \circ f_n)^i$. If $(f_1 \circ \cdots \circ f_n)^\omega$ were not $\varphi_L(L)$-reachable, then it would imply that $\mathrm{ext}_{u_\omega, v_\omega}$ is not $L$-reachable. This would in turn entail that for all $z \in \Sigma^\Delta$ and $\mathrm{ext}_{\alpha, \beta} \in \mathcal{O}(\Sigma^\Delta)$ we have

$$\mathrm{ext}_{\alpha, \beta}(\mathrm{ext}_{u_\omega, v_\omega}(z)) \notin L \wedge \mathrm{ext}_{\alpha, \beta}(\mathrm{ext}_{u_1 u_\omega, v_\omega v_1}(z)) = \mathrm{ext}_{\alpha u_1, v_1 \beta}(\mathrm{ext}_{u_\omega, v_\omega}(z)) \notin L,$$

so that it would follow that $(f_1 \circ \cdots \circ f_n)^\omega = \psi_L(\mathrm{ext}_{u_\omega, v_\omega}) = \psi_L(\mathrm{ext}_{u_1 u_\omega, v_\omega v_1}) = (f_1 \circ \cdots \circ f_n)^{\omega+1}$, a contradiction. Hence, since $(f_1 \circ \cdots \circ f_n)^\omega$ is a $\varphi_L(L)$-reachable idempotent and

$$e = \begin{cases} \mathrm{eval}_{\psi_L}(x') \circ (f_1 \circ \cdots \circ f_n)^\omega \circ \mathrm{eval}_{\psi_L}(y') & \text{if } xw^\omega y \in \mathcal{E}_{\psi_L, e} \text{ and } xw^{\omega+1} y \notin \mathcal{E}_{\psi_L, e} \\ \mathrm{eval}_{\psi_L}(x') \circ (f_1 \circ \cdots \circ f_n)^{\omega+1} \circ \mathrm{eval}_{\psi_L}(y') & \text{otherwise } (xw^\omega y \notin \mathcal{E}_{\psi_L, e} \text{ and } xw^{\omega+1} y \in \mathcal{E}_{\psi_L, e}) \end{cases},$$

it follows that $\mathcal{R}_{(f_1 \circ \cdots \circ f_n)^\omega}$ is length-synchronous. So for all $i \in \mathbb{N}, i \ge 2$, since $\psi_L(\mathrm{ext}_{u_1^\omega, v_1^\omega}) = \psi_L(\mathrm{ext}_{u_i^\omega, v_i^\omega}) = (f_1 \circ \cdots \circ f_n)^\omega$ with $\Delta(u_1^\omega) > 0$ and $\Delta(u_i^\omega) > 0$, since $|u_1| = |u_i|$, we have

$$\frac{|u_1^\omega|}{|v_1^\omega|} = \frac{|u_i^\omega|}{|v_i^\omega|} \Rightarrow \frac{|u_1|}{|v_1|} = \frac{|u_i|}{|v_i|} \Rightarrow |v_1| = |v_i|.$$

To conclude, we obtain that the non-aperiodic semigroup $\{(f_1 \circ \cdots \circ f_n)^i \mid i \in \mathbb{N}_{>0}\}$ is contained in $\psi_L(\mathcal{O}(\Sigma^\Delta)^{q \cdot s, |v_1|})$. $\square$
The following remark states that the length-synchronicity precondition in the second point of Proposition 5.10 is important. In fact it shows that weak length-synchronicity is not sufficient.

**Remark 5.11.** For the second point of Proposition 5.10 it is generally not sufficient to assume, given $e$, that for each $\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$ we have that $\mathcal{R}_f = \{(u, v) \in \Sigma^* \times \Sigma^* | uv \in \Sigma^\Delta, \Delta(u) > 0, \psi_L(\mathrm{ext}_{u,v}) = f\}$ is weakly length-synchronous. Indeed, the VPL K generated by the grammar with rules

$$S \rightarrow aSb_1 | acTb_2 | \varepsilon \\ T \rightarrow aTb_1 | acSb_2 .$$

using $S$ as start symbol is not length-synchronous, but weakly length-synchronous, and has a quasi-aperiodic syntactic morphism. However, for the syntactic Ext-algebra $(R_K, O_K)$ and the syntactic morphism $(\varphi_K, \psi_K)$ of $K$, we claim that there exists a $\varphi_K(K)$-reachable $e \in O_K$ such that $\mathcal{E}_{\psi_K, e}$ is a regular language whose syntactic morphism is not quasi-aperiodic while, as $K$ is weakly length-synchronous, for each $\varphi_L(L)$-reachable idempotent $f \in O_L$ we have that $\mathcal{R}_f = \{(u, v) \in \Sigma^* \times \Sigma^* | uv \in \Sigma^\Delta, \Delta(u) > 0, \psi_L(\mathrm{ext}_{u,v}) = f\}$ is weakly length-synchronous.

Let $\Gamma$ be the visibly pushdown alphabet of $K$. Note that we have $K \subset \mathcal{L}_{1,2}$, where $\mathcal{L}_{1,2} = L(S \rightarrow aSb_1|acSb_2|\varepsilon)$ is the VPL initially introduced in Example 2.5. For all $uv, u'v' \in \mathcal{L}_{1,2}$ with $u, u' \in \{a, c\}^+$, $v, v' \in \{b_1, b_2\}^+$, $|u|_c \equiv |u'|_c \pmod 2$ we have $xuzvy \in K \Leftrightarrow xu'zv'y \in K$ for all $xy, z \in \Gamma^\Delta$. This implies that if we set $e_0 = \psi_K(\mathrm{ext}_{a,b_1})$ and $e_1 = \psi_K(\mathrm{ext}_{ac,b_2})$, we have that for all $uv \in \mathcal{L}_{1,2}$ with $u \in \{a, c\}^+$, $v \in \{b_1, b_2\}^+$, it holds that $\psi_K(\mathrm{ext}_{u,v}) = e_{|u|_c \pmod 2}$. Therefore, while $e_0 \neq e_1$, we have $e_0 \circ e_1 = e_1 \circ e_0 = e_1$ and $e_0 \circ e_0 = e_1 \circ e_1 = e_0$.

Consider the length-multiplying monoid morphism $\beta: \{0,1\}^* \rightarrow \Gamma_{\psi_K}^*$ such that $\beta(0) = e_0e_0$ and $\beta(1) = \$e_1$. Then $\mathrm{MOD}_2 = \beta^{-1}(\mathcal{E}_{\psi_K, e_0})$, so $\mathcal{E}_{\psi_K, e_0}$ cannot have a quasi-aperiodic syntactic morphism, for otherwise, by closure of the class of regular languages whose syntactic morphism is quasi-aperiodic under inverses of length-multiplying morphisms (see [30]), we would have that $\mathrm{MOD}_2$ has a quasi-aperiodic syntactic morphism.

### 5.3.4 Approximate matching relation in FO$[+]$ (Proof of Point 3)

The following proposition states that there is a FO$[+]$-definable approximate matching relative to any length-synchronous visibly pushdown language.

**Proposition 5.12.** If $L \subseteq \Sigma^\Delta$ is length-synchronous, then there exists an FO$[+]$-formula $\eta(x, y)$ such that $M: \Sigma^* \rightarrow \mathbb{N}_{>0}^2$ defined by $M(w) = \{(i, j) \in [1, |w|]^2 | w \models \eta(i, j)\}$ for all $w \in \Sigma^*$ is an approximate matching relative to $L$.

The technical heart of the proof is the following lemma whose proof is postponed and will take most part of this subsection. This lemma realizes the characterization of length-synchronicity given by Proposition 4.11 via an FO$[+]$-formula.

**Lemma 5.13.** Assume that $(\varphi_L, \psi_L)$ is weakly length-synchronous. Let $e \in O_L$ be $\varphi_L(L)$-reachable and assume that $U_e = \{(u, v) \in \mathrm{Con}(\Sigma) | e \circ \psi_L(\mathrm{ext}_{u,v}) = e\}$ is length-synchronous. Then there exists an FO$[+]$-formula $\pi_e(x, x', y', y)$ such that for all $w \in \Sigma^+$ and $i, i', j', j \in [1, |w|], i \leq i' < j' \leq j$ the following holds,

* if $w \models \pi_e(i, i', j', j)$, then $w_i \cdots w_{i'} w_{j'} \cdots w_j \in \Sigma^\Delta$ and

* if $w_i \cdots w_{i'} w_{j'} \cdots w_j \in \Sigma^\Delta$ and $(w_i \cdots w_{i'}, w_{j'} \cdots w_j) \in U_e$, then $w \models \pi_e(i, i', j', j)$.
**Building an approximate matching assuming predicates $\pi_e$.** Let us prove Proposition 5.12 by making use of Lemma 5.13.

*Proof of Proposition 5.12.* By assumption $(\varphi_L, \psi_L)$ is $\varphi_L(L)$-length-synchronous. Thus, the set of contexts $U_e$ is length-synchronous for all $\varphi_L(L)$-reachable $e \in O_L$ by Proposition 4.10. Moreover, there exists $d_L \in \mathbb{N}$ bounding the nesting depth of the words in $L$ Proposition 4.14. For defining our desired formula $\mu$, we will construct $FO_{\Sigma[+]}$ formulas $\mu_d$ and $\mu_d^\uparrow$ for all $0 \le d \le d_L$ with the following properties: for all $w \in \Sigma^+$ and for all $i, j \in [1, |w|]$, we have

* if $w \models \mu_d^\uparrow(i, j)$ or $w \models \mu_d(i, j)$, then $w_i \cdots w_j \in \Sigma^\Delta$,

* if $w \in L$, $w_i \dots w_j \in \Sigma^\Delta$, $\mathrm{nd}(w_i \dots w_j) \le d$ and $i$ is matched to $j$ in $w$, then $w \models \mu_d^\uparrow(i, j)$, and

* if $w \in L$, $\mathrm{nd}(w_i \dots w_j) \le d$ and $w_i \dots w_j \in \Sigma^\Delta$, then $w \models \mu_d(i, j)$.

We therefore define $\mu = \mu_{d_L}$. The construction of $\mu_d^\uparrow$ and $\mu_d$ is by induction on $d$. We set

$$ \mu_0(i, j) = \perp \text{ and } \mu_0(i, j) = \forall z(x \le z \le y \rightarrow \Sigma_{\mathrm{int}}(z)). $$

Let us assume $d > 0$. The formula $\mu_d$ is easily defined assuming $\mu_d^\uparrow$. We define

$$ \mu_d(x, y) = \forall z \left[ x \le z \le y \rightarrow \left( \Sigma_{\mathrm{int}}(z) \lor \exists z' \left( (\Sigma_{\mathrm{call}}(z) \land \Sigma_{\mathrm{ret}}(z') \land \mu_d^\uparrow(z, z')) \lor (\Sigma_{\mathrm{call}}(z') \land \Sigma_{\mathrm{ret}}(z) \land \mu_d^\uparrow(z', z)) \right) \right] $$

It remains to define $\mu_d^\uparrow$. Let us assume $u = w_i \dots w_j \in \Sigma^\Delta$, that $i$ is matched to $j$ in $w$ and that $\mathrm{nd}(u) = d > 0$. Hence, $u = a_1 v b_1 \in \Sigma^\Delta$ for some $a_1 \in \Sigma_{\mathrm{call}}$, $b_1 \in \Sigma_{\mathrm{ret}}$, and $v \in \Sigma^\Delta$. We then apply Lemma 4.17 which states that $u$ has a nesting-maximal stair factorization $u = \mathrm{ext}_{x_1, y_1} \circ \mathrm{ext}_{a_1, b_1} \circ \dots \mathrm{ext}_{x_k, y_k} \circ \mathrm{ext}_{a_k, b_k}(u')$ such that for some $h \in [1, k]$, setting $u_\ell = \mathrm{ext}_{a_\ell, b_\ell} \circ \mathrm{ext}_{x_{\ell+1}, y_{\ell+1}} \circ \dots \circ \mathrm{ext}_{a_k, b_k}(u')$ for all $\ell \in [1, k]$ and $u_{k+1} = u'$, we have

1. $\mathrm{nd}(u) = \mathrm{nd}(u_h) = d$,

2. $\mathrm{nd}(u_{h+1}) = d - 1$, and

3. $\mathrm{nd}(x_1), \mathrm{nd}(y_1), \dots, \mathrm{nd}(x_h), \mathrm{nd}(y_h) < d$.

We remark that $x_1 = y_1 = \varepsilon$. Let $i = i_1 < \dots < i_h$ and $j_h < \dots < j_1 = j$ be the positions that correspond to the positions of the letters $a_1, \dots, a_h \in \Sigma_{\mathrm{call}}$ and $b_1, \dots, b_h \in \Sigma_{\mathrm{ret}}$ of $u$ in $w$, respectively: more precisely $i_\ell = i + |x_1 \cdots a_{\ell-1} x_\ell|$ and $j_\ell = |x_1 a_1 \cdots x_k a_k u' b_k y_k \cdots b_{\ell+1} y_{\ell+1}| + 1$ for all $\ell \in [1, h]$. The formula $\eta_d^\uparrow$ could guess the positions $i = i_1 < \dots < i_h$ and $j_h < \dots < j_1 = j$ and verify the following (recalling that $x_1 = y_1 = \varepsilon$):

(a) the infix $w_{i_h+1} \cdots w_{j_h-1} = \mathrm{ext}_{x_{h+1}, y_{h+1}}(u_{h+1})$ is well-matched, and

(b) the word $w_{i_1} \cdots w_{i_h} w_{j_h} \cdots w_{j_1}$ is well-matched.
Point (a) can be realized via the formula $\mu_{d-1}$ by making use of Point 2 from above, whereas Point (b) can be realized by the following ad-hoc formula, this time making use of Point 3 and from above:

$$ \kappa_h(x, x', y', y) = \exists x_1 \cdots x_h \exists y_1 \cdots y_h \left( x = x_1 \wedge x' = x_h \wedge y' = y_h \wedge y = y_h \wedge \left( \bigwedge_{t=1}^h \Sigma_{\text{call}}(x_t) \wedge \Sigma_{\text{ret}}(y_t) \wedge \bigwedge_{t=1}^{h-1} \mu_{d-1}(x_t + 1, x_{t+1} - 1) \wedge \mu_{d-1}(y_{t+1} + 1, y_t - 1) \right) \right) $$

The problem with this approach is that the size of the formula depends on the size of $w$. For instance, for $a \in \Sigma_{\text{call}}$, $b \in \Sigma_{\text{ret}}$, $c \in \Sigma_{\text{int}}$, and $u = a^n cb^n$ we have $\text{nd}(u) = \text{nd}(acb) = 1$ for all $n \ge 1$. Hence we would have $h = n - 1$, so $h$ would depend on $u$ which is problematic. Therefore, towards expressing Point (b) by a formula whose size only depends on $|O_L|$, let us define, for all $\ell, \ell' \in [1, h]$, the product

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

We remark that all $e_{\ell, \ell'}$ are $\varphi_L(L)$-reachable since $w$ is assumed to be in $L$. For $e \in O_L$ we say an interval $I = [s, t] \subseteq [1, h]$ is e-repetitive if $s < t$ and $e_s = e_t$. We say $[s, t] \subseteq [1, h]$ is repetitive if it is e-repetitive for some $e \in O_L$.

**Claim 5.14.** There exist indices $1 = t_0 \le s_1 < t_1 < s_2 < t_2 < \cdots < s_q < t_q \le s_{q+1} = h$ such that $[s_1, t_1], \dots, [s_q, t_q]$ are all repetitive and for $D_0 = [t_0, s_1], D_1 = [t_1, s_2], \dots, D_q = [t_q, s_{q+1}]$ we have $q + \sum_{p=0}^q |D_p| \le 3|O_L|$.

*Proof of the Claim.* For all $z \in [1, h]$ let $\lambda(z) = \max\{\ell \in [1, h] \mid e_\ell = e_z\}$. Observe $\lambda(z) \ge z$ for all $z \in [1, h]$ and that $|\lambda([1, h])| \le |O_L|$. We define $t_0 = 1$. Let $p > 0$ and assume that we have already defined $t_{p-1}$. In case $t_{p-1} = h$ we are done and define $q = p-1$ and $s_{q+1} = h$. So let us assume $t_{p-1} < h$. In case there exists $z \in [t_{p-1}, h]$ such that $z < \lambda(z)$ we define $s_p = \min\{z \in [t_{p-1}, h] \mid z < \lambda(z)\}$ and $t_p = \lambda(s_p)$, otherwise (i.e. in case $z = \lambda(z)$ for all $z \in [t_{p-1}, h]$) we are done and define $q = p-1$ and $s_{q+1} = h$. Immediately by definition we have $1 = t_0 \le s_1 < t_1 < s_2 < t_2 < \cdots < s_q < t_q \le s_{q+1} = h$ (because if we had $t_{p-1} = s_p$ for a $p \in [2, q]$, we would have $e_{s_{p-1}} = e_{t_{p-1}} = e_{s_p}$, so $\lambda(s_p) = \lambda(s_{p-1}) = t_{p-1} = s_p < \lambda(s_p)$, a contradiction) and $e_{s_p} = e_{t_p}$ for all $p \in [1, q]$. Moreover, the intervals $[s_1, t_1], \dots, [s_q, t_q]$ are indeed all repetitive. Since moreover $t_p \in \lambda([1, h])$ for all $p \in [1, q]$ and $|\lambda([1, h])| \le |O_L|$ we must have $q \le |O_L|$. Now let $D_0 = [t_0, s_1], D_1 = [t_1, s_2], \dots, D_q = [t_q, s_{q+1}]$. Clearly, these sets are pairwise disjoint. Moreover, by construction, the only elements $z \in \bigcup_{p=0}^q D_p$ such that $z < \lambda(z)$ are those in $X = \{s_1, \dots, s_q\}$, so that all elements $z \in (\bigcup_{p=0}^q D_p) \setminus X$ satisfy $z = \lambda(z)$, i.e. are elements from $\lambda([1, h])$. Thus, we obtain $q + \sum_{p=0}^q |D_p| = q + |\bigcup_{p=0}^q D_p| \le |O_L| + |X| + |\lambda([1, h])| = 3|O_L|$. $\square$

Let $1 = t_0 \le s_1 < t_1 < s_2 < t_2 < \cdots < s_q < t_q \le s_{q+1} = h$ be the indices satisfying Claim 5.14 along with $D_0 = [t_0, s_1], D_1 = [t_1, s_2], \dots, D_q = [t_q, s_{q+1}]$. Let $d_p = |D_p|$ for all $p \in [0, q]$. Since, for all $p \in [1, q]$, the non-empty interval $[s_p, t_p]$ is repetitive, we have $e_{s_p} = e_{t_p}$ and thus obtain

$$ e_{s_p} = e_{t_p} = e_{s_p} \circ \psi_L(\text{ext}_{x_{s_{p+1}}, \dots, a_{t_p}, b_{t_p}, \dots, y_{s_{p+1}}}). $$

Hence, we have $w \models \pi_{e_{s_p}}(i_{s_p} + 1, i_{t_p}, j_{t_p}, j_{s_p} - 1)$ where $\pi_{e_{s_p}}$ is the formula given by Lemma 5.13 (recall that $e_{s_p}$ is $\varphi_L(L)$-reachable and that $\mathcal{U}_{e_{s_p}}$ is length-synchronous). We can therefore use the
formula $\pi_{e_{sp}}$ to witness that $w_{i_{sp}+1} \cdots w_{i_{tp}} w_{j_{tp}} \cdots w_{j_{sp}-1}$ is indeed a well-matched word. It will thus remain to verify that $w_{i_{tp}} \cdots w_{i_{sp+1}} w_{j_{sp+1}} \cdots w_{i_{tp}}$ is well-matched for all $p \in [0, q]$; this can be guaranteed by evaluating $\kappa_{d_p}(i_{tp}, i_{sp+1}, j_{sp+1}, i_{tp})$. We can now define our final formula $\mu_d^\uparrow$:

$$ \mu_d^\uparrow(x, y) = \bigvee_{\substack{q \in [0, |O_L|] \\ d_0, \dots, d_q \ge 1: \\ q+d_0+\dots+d_q \le 3|0|}} \exists x_1 \dots x_{q+1} \exists x'_0 \dots x'_q \exists y_1 \dots y_{q+1} \exists y'_1 \dots y'_0 \\ \left[ x_0 \le x_1 < x'_1 < x_2 < \dots < x'_q < y'_q < y_q < \dots < y'_1 < y_1 \le y'_0 \wedge \right. \\ \qquad \left. x'_0 = x \wedge y'_0 = y \wedge \mu_{d-1}(x_{q+1} + 1, y_{q+1} - 1) \wedge \right. \\ \qquad \left. \bigwedge_{p=1}^q \left( \bigvee_{e \in O_L \ \varphi_L(L)\text{-reachable}} \pi_e(x_p + 1, x'_p, y'_p, y_p - 1) \right) \wedge \bigwedge_{p=0}^q \kappa_{d_p}(x'_p, x_{p+1}, y_{p+1}, y'_p) \right] . \quad \Box $$

The following remark is obvious but will be important in Section 5.4.

**Remark 5.15.** When constructing our predicate $\mu_d^\uparrow$, we could have replaced any subset of the predicates $\pi_e$, where $e$ is $\varphi_L(L)$-reachable from above, by the predicate $\pi_e^{\text{exact}}$ expressing that for all $w \in \Sigma^+$ and $i, i', j', j \in [1, |w|], i \le i' < j' \le j$ it holds:

$$ w \models \pi_e^{\text{exact}}(i, i', j', j) \iff w_i \dots w_{i'} w_{j'} \dots w_j \in \Sigma^\Delta, e \circ \psi_L(\text{ext}_{w_i \dots w_{i'}, w_{j'} \dots w_j}) = e, \text{ and} \\ \Delta(w_i \dots w_{i'}) > 0 $$

It remains to prove Lemma 5.13.

## Proof of Lemma 5.13

In essence, our proof is inspired by the approach taken in [24, Proof of Proposition 126], which is itself a flawed adaptation (we refer to Section 8 for more details) of the approach taken in [23, Proof of Lemma 15].

Let $\alpha_e \in \mathbb{Q}_{>0}$, $\beta_e \in \mathbb{N}$ and $\gamma_e \in \mathbb{N}_{>0}$ given by Proposition 4.11 for $e$. There exist unique $n_e, d_e \in \mathbb{N}_{>0}$ that are relatively prime such that $\alpha_e = \frac{n_e}{d_e}$. We are going to build an $\text{FO}[+]$-formula $\pi_e(x, x', y', y)$ such that for all $w \in \Sigma^+$ and $i, i', j', j \in [1, |w|], i \le i' < j' \le j$, we have that $w \models \pi_e(i, i', j', j)$ if, and only if, all of the following conditions are satisfied:

(i) $\frac{i'-i+1}{j-j'+1} = \frac{n_e}{d_e}$;

(ii) $-\beta_e \le \Delta(w_i \cdots w_{i+k \cdot n_e-1} w_{j-k \cdot d_e+1} \cdots w_j) \le \beta_e$ for all $k \in \mathbb{N}_{>0}$ such that $k \le (j-j'+1)/d_e$ and $\Delta(w_i \cdots w_{i'} w_{j'} \cdots w_j) = 0$;

(iii) $\Delta(w_{i+(q-1) \cdot \gamma_e} \cdots w_{i+q \cdot \gamma_e-1}) \ge 1$ for all $q \in \mathbb{N}_{>0}$ with $q \cdot \gamma_e \le i'-i+1$ and $\Delta(w_i \cdots w_{i+p-1}) \ge 0$ for all $p \in [1, i'-i+1]$;

(iv) $\Delta(w_{j-q \cdot \gamma_e+1} \cdots w_{j-(q-1) \cdot \gamma_e}) \le -1$ for all $q \in \mathbb{N}_{>0}$ with $q \cdot \gamma_e \le j-j'+1$ and $\Delta(w_{j-p+1} \cdots w_j) \le 0$ for all $p \in [1, j-j'+1]$.

Let us first prove that these four conditions whose conjunction the $\text{FO}[+]$-formula $\pi_e(x, x', y', y)$ will express, indeed imply the two conditions of the lemma.

If conditions (i) to (iv) are satisfied for a $w \in \Sigma^+$ and $i, i', j', j \in [1, |w|], i \le i' < j' \le j$, we actually have that $w_i \cdots w_{i'} w_{j'} \cdots w_j \in \Sigma^\Delta$. Indeed, condition (ii) ensures that $\Delta(w_i \cdots w_{i'} w_{j'} \cdots w_j) =$
0. Conditions (iii) and (iv) then additionally imply that $\Delta(w_i \cdots w_{i+p-1}) \ge 0$ for all $p \in [1, i' - i + 1]$ and $\Delta(w_i \cdots w_i' w_{j'} \cdots w_{j'+p-1}) \ge 0$ for all $p \in [1, j - j' + 1]$. This is because if there were a $p \in [1, j - j' + 1]$ such that $\Delta(w_i \cdots w_i' w_{j'} \cdots w_{j'+p-1}) < 0$, then it should be that $\Delta(w_{j'+p} \cdots w_j) > 0$ with $p \le j - j'$ as we already know that $\Delta(w_i \cdots w_i' w_{j'} \cdots w_j) = 0$: this would be a contradiction to condition (iv).

Conversely, let us fix some $w \in \Sigma^+$ and indices $i, i', j', j \in [1, |w|]$ such that $i \le i' < j' \le j$, $w_i \cdots w_i' w_{j'} \cdots w_j \in \Sigma^\Delta$, $\Delta(w_i \cdots w_i') > 0$ and $e \circ \psi_L(\text{ext}_{w_i \cdots w_i', w_{j'} \cdots w_j}) = e$. In the terminology of Proposition 4.11, for $F = \varphi_L(L)$, we have $(w_i \cdots w_i', w_{j'} \cdots w_j) \in \mathcal{U}_e$. We claim that Points (i) to (iv) are actually satisfied. Indeed, recalling that $L$ is length-synchronous by assumption, 2(a) of Proposition 4.11 for $e$ in fact states that that Point (i) is satisfied. Next, since for all $k \in \mathbb{N}_{>0}$ such that $k \le \frac{j-j'+1}{d_e} = \frac{i'-i+1}{n_e}$, the word $w_i \cdots w_{i+k \cdot n_e-1}$ is a prefix of $w_i \cdots w_{i'}$ and the word $w_{j-k \cdot d_e+1} \cdots w_j$ is a suffix of $w_{j'} \cdots w_j$ such that $\frac{|w_i \cdots w_{i+k \cdot n_e-1}|}{|w_{j-k \cdot d_e+1} \cdots w_j|} = \frac{k \cdot n_e}{k \cdot d_e} = \alpha_e$, it must hold that $-\beta_e \le \Delta(w_i \cdots w_{i+k \cdot n_e-1} w_{j-k \cdot d_e+1} \cdots w_j) \le \beta_e$ by Point 2(b) of Proposition 4.11. We have that $\Delta(w_i \cdots w_i' w_{j'} \cdots w_j) = 0$ immediately follows from our assumption $w_i \cdots w_i' w_{j'} \cdots w_j \in \Sigma^\Delta$, thus Point (ii) holds. Another consequence of our assumption $w_i \cdots w_i' w_{j'} \cdots w_j \in \Sigma^\Delta$ is that $\Delta(w_i \cdots w_{i+p-1}) \ge 0$ for all $p \in [1, i' - i + 1]$ and $\Delta(w_i \cdots w_i' w_{j'} \cdots w_{j'+p-1}) \ge 0$ for all $p \in [1, j - j' + 1]$. This implies that $\Delta(w_{j-p+1} \cdots w_j) \le 0$ for all $p \in [1, j - j' + 1]$, as already argued above. Since $w_{i+(q-1) \cdot \gamma_e} \cdots w_{i+q \cdot \gamma_e-1}$ is a factor of $w_i \cdots w_{i'}$ of length $\gamma_e$ for all $q \in \mathbb{N}_{>0}$ such that $q \cdot \gamma_e \le i' - i + 1$ and $w_{j-q \cdot \gamma_e+1} \cdots w_{j-(q-1) \cdot \gamma_e}$ is a factor of $w_{j'} \cdots w_j$ of length $\gamma_e$ for all $q \in \mathbb{N}_{>0}$ such that $q \cdot \gamma_e \le j - j' + 1$, by Points 2(c) and 2(d) of Proposition 4.11, we finally have that conditions (iii) and (iv) are also satisfied.

It now remains to construct the formula $\pi_e(x, x', y', y)$. We set

$$ \begin{aligned} \pi_e(x, x', y', y) = & (x' - x + 1) \cdot d_e = (y - y' + 1) \cdot n_e \wedge \\ & \mu_{n_e, d_e, \beta_e}(x, x', y', y) \wedge \\ & \nu_{\gamma_e}^+(x, x') \wedge \nu_{\gamma_e}^-(y', y), \end{aligned} $$

where the first line checks condition (i), the FO[+]-formula $\mu_{n_e, d_e, \beta_e}(x, x', y', y)$ will check condition (ii) under the assumption condition (i) is satisfied and the FO[+]-formulas $\nu_{\gamma_e}^+(x, x')$ and $\nu_{\gamma_e}^-(y', y)$ respectively will check conditions (iii) and (iv). We now explain how to build those formulas.

**Helper formulas.** For all $k \in \mathbb{N}_{>0}$ and $h \in \mathbb{Z}$ such that $-k \le h \le k$, we let

$$ H_k^h(x) = \bigvee_{\substack{I, J \subseteq [1, k] \\ I \cap J = \emptyset \\ |I| - |J| = h}} \left( \bigwedge_{p \in I} \Sigma_{\text{call}}(x + p - 1) \wedge \bigwedge_{p \in J} \Sigma_{\text{ret}}(x + p - 1) \wedge \bigwedge_{p \in [1, k] \setminus (I \cup J)} \Sigma_{\text{int}}(x + p - 1) \right) $$

such that for all $w \in \Sigma^+$ and $i \in [1, |w|]$ such that $i \le |w| - k + 1$, we have $w \models H_k^h(i)$ if, and only if, $\Delta(w_i \cdots w_{i+k-1}) = h$.

For all $n, d \in \mathbb{N}_{>0}$ relatively prime and $h \in \mathbb{Z}$, $-n - d \le h \le n + d$, we define

$$ D_{n,d}^h(x, y, z) = \bigvee_{\substack{-n \le h_1 \le n \\ -d \le h_2 \le d \\ h_1+h_2=h}} \left( H_n^{h_1}(x + (z-1) \cdot n) \wedge H_d^{h_2}(y - z \cdot d + 1) \right), $$

such that for all $w \in \Sigma^+$ and $i, j, k \in [1, |w|]$ with $i + k \cdot n - 1 \le |w|$ and $j - k \cdot d + 1 \ge 1$, we have
$w \models D_{n,d}^h(i, j, k)$ if, and only if,

$$ \Delta(w_{i+(k-1)\cdot n} \cdots w_{i+k\cdot n-1}w_{j-k\cdot d+1} \cdots w_{j-(k-1)\cdot d}) = h. $$

**Formula** $\mu_{n,d,q}(x, x', y', y)$. For each $p \in \mathbb{N}$ let $\Gamma_p = \{a_{-p}, \dots, a_{-1}, a_0, a_1, \dots, a_p\}$ and define $\Delta_p: \Gamma_p^* \to \mathbb{Z}$ to be the $p$-height monoid morphism satisfying $\Delta_p(a_h) = h$ for all $a_h \in \Gamma_p$. Consider the language

$$ L_{p,q} = \{w \in \Gamma_p^* | \Delta_p(w) = 0 \wedge \forall i \in [1, |w|], -q \le \Delta_p(w_1 \cdots w_i) \le q\}. $$

We claim that this language is recognized by a finite aperiodic monoid. This implies, by a theorem by McNaughton and Papert (see [29, Theorem VI.1.1]), that there exists an $\text{FO}_{\Gamma_{n+d}}[<]$-sentence $\tilde{\mu}_{p,q}$ defining $L_{p,q}$.

Let now $n, d \in \mathbb{N}_{>0}$ relatively prime and $q \in \mathbb{N}$. Consider $w \in \Sigma^+$ and $i, i', j', j \in [1, |w|]$ such that $i \le i' < j' \le j$ and $\frac{i'-i+1}{j-j'+1} = \frac{n}{d}$. We want to check whether we have

$$ -q \le \Delta(w_i \cdots w_{i+k \cdot n-1} w_{j-k \cdot d+1} \cdots w_j) \le q $$

for all $k \in \mathbb{N}_{>0}$ such that $k \le (j - j' + 1)/d$ and moreover $\Delta(w_i \cdots w_{i'} w_{j'} \cdots w_j) = 0$. Since $n$ and $d$ are relatively prime, this means that there exists $l \in [1, |w|]$ such that $i' - i + 1 = l \cdot n$ and $j - j' + 1 = l \cdot d$. We can hence decompose $w_i \cdots w_{i'}$ as $u_1 \cdots u_l$ with $u_1, \dots, u_l \in \Sigma^n$ and $w_{j'} \cdots w_j$ as $v_l \cdots v_1$ with $v_1, \dots, v_l \in \Sigma^d$. Observe that $\Delta(u_i v_i) \in [-n-d, n+d]$ for all $i \in [1, l]$. Using this decomposition, we now need to check whether $-q \le \Delta(u_1 v_1) + \cdots + \Delta(u_k v_k) \le q$ for all $k \in [1, l]$ and $\Delta(u_1 v_1) + \cdots + \Delta(u_l v_l) = 0$. This is equivalent to checking whether the word $\tilde{w} = a_{\Delta(u_1 v_1)} \cdots a_{\Delta(u_l v_l)}$ in $\Gamma_{n+d}^*$ belongs to $L_{n+d,q}$.

We thus transform the $\text{FO}_{\Gamma_{n+d}}[<]$-sentence $\tilde{\mu}_{n+d,q}$ into an $\text{FO}_{\Sigma^+}$-formula $\mu_{n+d,q}(x, x', y', y)$ by

* replacing any quantification $\exists z \rho(z)$ by $\exists z (z \le (y - y' + 1)/d \wedge \rho(z))$;

* replacing any quantification $\forall z \rho(z)$ by $\forall z (z \le (y - y' + 1)/d \rightarrow \rho(z))$;

* replacing any atomic formula of the form $a_h(z)$ for $a_h \in \Gamma_{n+d}$ by $D_{n,d}^h(x, y, z)$.

By this translation for all $w \in \Sigma^+$ and $i, i', j', j \in [1, |w|]$ with $i \le i' < j' \le j$ and $\frac{i'-i+1}{j-j'+1} = \frac{n}{d}$ we have $w \models \mu_{n,d,q}(i, i', j', j)$ if, and only if, $-q \le \Delta(w_i \cdots w_{i+k \cdot n-1} w_{j-k \cdot d+1} \cdots w_j) \le q$ for all $k \in \mathbb{N}_{>0}$, $k \le (j - j' + 1)/d$ and $\Delta(w_i \cdots w_{i'} w_{j'} \cdots w_j) = 0$.

It remains to show that $L_{p,q}$ is recognized by a finite aperiodic monoid for all $p, q \in \mathbb{N}$. Set $Q_q = \{-q, \dots, -1, 0, 1, \dots, q, \perp\}$ and consider the monoid $Q_q^{Q_q}$ with function composition from left to right. For each $a_h \in \Gamma_p$, we define the function $f_{a_h}: Q_q \to Q_q$ to be such that

$$ f_{a_h}(h') = \begin{cases} h' + h & \text{if } h' \ne \perp \text{ and } -q \le h' + h \le q \\ \perp & \text{otherwise} \end{cases} $$

for all $h' \in Q_q$. We take $M_{p,q}$ to be the submonoid of $Q_q^{Q_q}$ generated by $\{f_{a_h} | a_h \in \Gamma_p\}$ and define $\varphi_{p,q}: \Gamma_p^* \to M_{p,q}$ as the unique monoid morphism such that $\varphi_{p,q}(a_h) = f_{a_h}$ for all $a_h \in \Gamma_p$.

It is straightforward to show, by induction on the length of $w$, that for all $w \in \Gamma_p^*$ and all $h \in Q_q$, we have

$$ \varphi_{p,q}(w)(h) = \begin{cases} h + \Delta_p(w) & \text{if } h \ne \perp \text{ and } -q \le h + \Delta_p(w_1 \cdots w_i) \le q \text{ for all } i \in [1, |w|] \\ \perp & \text{otherwise.} \end{cases} $$
Thus $L_{p,q} = \varphi_{p,q}^{-1}(\{f \in M_{p,q} | f(0) = 0\})$. We claim that the monoid $M_{p,q}$ is aperiodic. Indeed, take $f \in M_{p,q}$; we claim that $f^{2q+1} = f^{2q+2}$. Since $M_{p,q}$ is generated by $\{f_{a_h} | a_h \in \Gamma_p\}$, there exists $w \in \Gamma_p^*$ satisfying $\varphi_{p,q}(w) = f$. There are three subcases to consider.

* If $\Delta_p(w) = 0$, then since $h + \Delta_p(w^{n-1}w_1 \cdots w_i) = h + \Delta_p(w_1 \cdots w_i)$ for all $h \in \mathbb{Z}$, $-q \le h \le q$, for all $n \in \mathbb{N}_{>0}$ and $i \in [1, |w|]$, we have that $f^n = f$ for all $n \in \mathbb{N}_{>0}$.

* If $\Delta_p(w) > 0$, then since $q < h + \Delta_p(w^{2q+1}) \le h + \Delta_p(w^{2q+2})$ for all $h \in \mathbb{Z}$, $-q \le h \le q$, both $f^{2q+1}$ and $f^{2q+2}$ must be equal to the function sending every element to $\perp$.

* If $\Delta_p(w) < 0$, then since $h + \Delta_p(w^{2q+2}) \le h + \Delta_p(w^{2q+1}) < -q$ for all $h \in \mathbb{Z}$, $-q \le h \le q$, both $f^{2q+1}$ and $f^{2q+2}$ must be equal to the function sending every element to $\perp$.

**Formula** $\nu_l^+(x, x')$. For all $l \in \mathbb{N}_{>0}$, we let

$$ \nu_l^+(x, x') = \bigwedge_{p=1}^{l^2} (x' - x + 1 \ge p \rightarrow \bigwedge_{k=1}^{p} \bigvee_{h=0}^{k} H_k^h(x)) \wedge \\ \forall z (z \cdot l \le x' - x + 1 \rightarrow \bigvee_{h=1}^{l} H_l^h(x + (z - 1) \cdot l)). $$

Fix any $w \in \Sigma^+$ and $i, i' \in [1, |w|]$ such that $i \le i'$. We have $w \models \nu_l^+(i, i')$ if, and only if, $\Delta(w_i \cdots w_{i+p-1}) \ge 0$ for all $p \in [1, \min\{l^2, i'-i+1\}]$ and $\Delta(w_{i+(q-1) \cdot l} \cdots w_{i+q \cdot l-1}) \ge 1$ for all $q \in \mathbb{N}_{>0}$ such that $q \cdot l \le i' - i + 1$. The latter is clearly equivalent to having $\Delta(w_{i+(q-1) \cdot l} \cdots w_{i+q \cdot l-1}) \ge 1$ for all $q \in \mathbb{N}_{>0}$, $q \cdot l \le i' - i + 1$ and $\Delta(w_i \cdots w_{i+p-1}) \ge 0$ for all $p \in [1, i' - i + 1]$, as required.

**Formula** $\nu_l^-(y', y)$. For all $l \in \mathbb{N}_{>0}$, we let

$$ \nu_l^-(y', y) = \bigwedge_{p=1}^{l^2} (y - y' + 1 \ge p \rightarrow \bigwedge_{k=1}^{p} \bigvee_{h=0}^{k} H_k^{-h}(y - k + 1)) \wedge \\ \forall z (z \cdot l \le y - y' + 1 \rightarrow \bigvee_{h=1}^{l} H_l^{-h}(y - z \cdot l + 1)). $$

Therefore, analogously as for $\nu_l^+(x, x')$, for all $w \in \Sigma^+$ and $j', j \in [1, |w|]$ such that $j' \le j$, we have $w \models \nu_l^-(j', j)$ if, and only if, $\Delta(w_{j-q \cdot l+1} \cdots w_{j-(q-1) \cdot l}) \le -1$ for all $q \in \mathbb{N}_{>0}$ such that $q \cdot l \le j - j' + 1$ and $\Delta(w_{j-p+1} \cdots w_j) \le 0$ for all $p \in [1, j - j' + 1]$.

### 5.3.5 Evaluation in FO$[+]$ (Proof of Point 4)

The following proposition states that every VPL $L$ that has bounded nesting depth and for which the horizontal and vertical evaluation languages $\mathcal{E}_{\varphi_L, r}$ and $\mathcal{E}_{\psi_L, e}$ are quasi-aperiodic for all $\varphi_L(L)$-reachable $r$ and $e$, respectively, is definable by an $\text{FO}_{\Sigma, \rightsquigarrow}[+]$-sentence in case an approximate matching is present as built-in predicate.
**Proposition 5.16.** Assume a VPL L has bounded nesting depth and

* $\mathcal{E}_{\varphi_{L,r}}$ is a regular language whose syntactic morphism is quasi-aperiodic for all $\varphi_L(L)$-reachable $r \in R_L$, and

* $\mathcal{E}_{\psi_{L,e}}$ is a regular language whose syntactic morphism is quasi-aperiodic for all $\varphi_L(L)$-reachable $e \in O_L$.

Then there exists an FO$_{\Sigma, \omega_\omega}$-[+]-sentence $\eta$ such that for any approximate matching M relative to L, we have $w \in L$ if, and only if, $(w, M(w)) \models \eta$ for all $w \in \Sigma^*$.

*Proof.* By hypothesis, there exists $d_L \in \mathbb{N}$ bounding the nesting depth of the words in L.

By hypothesis also, for each $\varphi_L(L)$-reachable $r \in R_L$, the language $\mathcal{E}_{\varphi_{L,r}}$ is regular and its syntactic morphism is quasi-aperiodic. This implies, by [29, Theorem VI.4.1], that for each $\varphi_L(L)$-reachable $r \in R_L$, there exists an FO$_{\varphi_L}$-[<, MOD]-sentence $\nu_{\varphi_L,r}$ defining $\mathcal{E}_{\varphi_L,r}$.

Finally, by hypothesis, for each $\varphi_L(L)$-reachable $e \in O_L$, the language $\mathcal{E}_{\psi_{L,e}}$ is regular and its syntactic morphism is quasi-aperiodic. Again, by [29, Theorem VI.4.1], for each $\varphi_L(L)$-reachable $e \in O_L$, there exists an FO$_{\psi_L}$-[<, MOD]-sentence $\nu_{\psi_L,e}$ defining $\mathcal{E}_{\psi_L,e}$.

**Auxiliary formulas.** We introduce a few auxiliary formulas that all assume access to the full matching relation $M^\Delta(w)$, represented by the relational symbol $\omega$.

First let us define a formula A such that for all $w \in \Sigma^\Delta$ and $i, j, k \in [1, |w|]$ satisfying $w_i \cdots w_j \in \Sigma^\Delta$, we have that $(w, M^\Delta(w)) \models A(i, j, k)$ if, and only if, $i \le k < j$ and $\Delta(w_i \cdots w_k) > 0$. We let

$$A(x, y, z) = \exists x' \exists y' (x \le x' \le z < y' \le y \land x' \omega y').$$

Next, we define a formula U such that for all $w \in \Sigma^\Delta$ and $i, i', k \in [1, |w|]$, we have that $(w, M^\Delta(w)) \models U(i, i', k)$ if, and only if, $i \le k \le i'$ and $k$ is matched to some position larger than $i'$ in w. We let

$$U(x, x', z) = x \le z \le x' \land \exists t (z \omega t \land x' < t).$$

The last formulas we introduce are $N_d$ which express that the infix $w_i \cdots w_j \in \Sigma^\Delta$ of $w \in \Sigma^\Delta$ has nesting depth at least $d \ge 0$. More precisely, for all $d \in \mathbb{N}$, we introduce auxiliary formulas $N_d$ such that for all $w \in \Sigma^\Delta$ and $i, j \in [1, |w|]$ satisfying $w_i \cdots w_j \in \Sigma^\Delta$, we have that $(w, M^\Delta(w)) \models N_d(i, j)$ if, and only if, $\mathrm{nd}(w_i \cdots w_j) \ge d$. The case $d=0$ is trivial since we can set $N_0(i, j) = \top$.

Take $w \in \Sigma^\Delta$ such that $\mathrm{nd}(w) = d' \ge 1$. Note that then $w$ can be factorized as $w = w_1uw_2$ such that $w_1, w_2 \in \Sigma^\Delta$, $u \in \Sigma_{\mathrm{call}}\Sigma^\Delta\Sigma_{\mathrm{ret}}$ and $\mathrm{nd}(w) = \mathrm{nd}(u) = d'$. This means that $u = a_1vb_1$ for $a_1 \in \Sigma_{\mathrm{call}}$, $b_1 \in \Sigma_{\mathrm{ret}}$ and $v \in \Sigma^\Delta$. We then apply Lemma 4.16 and Lemma 4.17 implying that $u$ has a nesting-maximal stair factorization

$$u = \mathrm{ext}_{x_1, y_1} \circ \mathrm{ext}_{a_1, b_1} \circ \dots \circ \mathrm{ext}_{x_k, y_k} \circ \mathrm{ext}_{a_k, b_k}(u')$$

for which there exists $h \in [1, k]$ such that, setting $u_i = \mathrm{ext}_{a_i, b_i} \circ \mathrm{ext}_{x_{i+1}, y_{i+1}} \circ \dots \circ \mathrm{ext}_{a_k, b_k}(u')$ for all $i \in [1, k]$ and $u_{k+1} = u'$, we have $\mathrm{nd}(u) = \mathrm{nd}(u_h) = d'$ and $\mathrm{nd}(\mathrm{ext}_{x_{h+1}, y_{h+1}} \circ \mathrm{ext}_{a_{h+1}, b_{h+1}} \circ \dots \circ \mathrm{ext}_{a_k, b_k}(u')) = \mathrm{nd}(u_{h+1}) = d' - 1$. Thus, by definition of the nesting depth of a well-matched word, $u_h = a_h z_1 z_2 b_h$ for $z_1, z_2 \in \Sigma^\Delta$ satisfying $\mathrm{nd}(z_1) = \mathrm{nd}(z_2) = d' - 1$.

Hence, we set

$$N_1(x, y) = \exists x' \exists y' (x \le x' < y' \le y \land x' \omega y').$$
and for $d \ge 2$ we set

$$N_d(x, y) = \exists x' \exists y' \exists z (x \le x' < z < y' \le y \land x' \rightsquigarrow y' \land \neg A(x' + 1, y' - 1, z) \land N_{d-1}(x' + 1, z) \land N_{d-1}(z + 1, y' - 1)).$$

**Main construction.** To build the $FO_{\Sigma, \rightsquigarrow}[+]$-sentence $\eta$, we build $FO_{\Sigma, \rightsquigarrow}[+]$-formulas

* $\eta_{d,r}^{\uparrow}(x, y)$ for all $d \in \mathbb{N}$ and all $\varphi_L(L)$-reachable $r \in R_L$ and

* $\eta_{d,r}(x, y)$ for all $d \in \mathbb{N}$ and all $\varphi_L(L)$-reachable $r \in R_L$

that also assume access to the full matching relation $M^{\Delta}(w)$. They will have the following properties for all $w \in \Sigma^{\Delta}$ and all $i, j \in [1, |w|]$:

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

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

Let the formula $E$ be defined as $\forall x(x \neq x)$ if $\varepsilon \in L$ and $\perp = \exists x(x \neq x)$ otherwise. Our final formula $\eta$ will then be defined as

$$\eta = \forall z \exists t \left( (\Sigma_{\text{call}}(z) \to z \rightsquigarrow t) \land (\Sigma_{\text{ret}}(z) \to t \rightsquigarrow z) \right) \land \left( E \lor \exists x \exists y (\neg \exists x'(x' < x) \land \neg \exists y'(y < y') \land \bigvee_{r \in \varphi_L(L)} \eta_{d,r}(x, y)) \right).$$

It now remains to build $\eta_{d,r}^{\uparrow}(x, y)$ and $\eta_{d,r}(x, y)$ for all $d \in \mathbb{N}$ and $\varphi_L(L)$-reachable $r \in R_L$. The construction is by induction on $d$. Let $r \in R_L$ that is $\varphi_L(L)$-reachable. We define $\eta_{0,r}^{\uparrow}(x, y) = \perp$. We define $\eta_{0,r}$ as

$$\eta_{0,r}(x, y) = \neg N_1(x, y) \land \tau_0(\nu_{\varphi_L, r}),$$

where the translation $\tau_0$ is inductively defined as follows:

* $\tau_0(z < z') = z < z'$;

* $\tau_0(s(z)) = \bigvee_{c \in \varphi_L^{-1}(s) \cap \Sigma_{\text{int}}} c(z)$ for all $s \in \varphi_L(\Sigma^{\Delta} \setminus \{\varepsilon\})$;

* $\tau_0(\mathrm{MOD}_m(z)) = \exists t((z = x \to 1 = t \cdot m) \land (z \neq x \to z - x + 1 = t \cdot m))$ for all $m \in \mathbb{N}_{>0}$;

* $\tau_0(\$z) = \perp$;

* $\tau_0(\rho_1(z_1) \land \rho_2(z_2)) = \tau_0(\rho_1(z_1)) \land \tau_0(\rho_1(z_2))$;

* $\tau_0(\neg \rho(z)) = \neg \tau_0(\rho(z))$;

* $\tau_0(\exists z \rho(z, z)) = \exists z(x \le z \le y \land \tau_0(\rho(z, z)))$.

Now let $d > 0$. Let us first define $\eta_{d,r}$ when assuming that we have already defined $\eta_{d,r}^{\uparrow}$. Given $w \in \Sigma^{\Delta} \setminus \{\varepsilon\}$ and $i, j \in [1, |w|]$ such that $w_i \cdots w_j \in \Sigma^{\Delta} \setminus \{\varepsilon\}$, note that in case $\mathrm{nd}(w_i \cdots w_j) \le d$, then one can factorize $w_i \cdots w_j$ as $w_i \cdots w_j = u_1 \cdots u_m$ such that $u_{\ell} \in \Sigma_{\text{int}} \cup \Sigma_{\text{call}}\Sigma^{\Delta}\Sigma_{\text{ret}}$ and