# The $\mathsf{AC}^{0}$-Complexity Of Visibly Pushdown Languages

Stefan Göller
<EMAIL_ADDRESS>The first author was supported by the Agence
Nationale de la Recherche grant no. ANR-17-CE40-0010. School of Electrical
Engineering and Computer Science, Universität Kassel, Germany  Nathan
Grosshans
<EMAIL_ADDRESS>Independent Scholar, France

###### Abstract

We study the question of which visibly pushdown languages (VPLs) are in the
complexity class $\mathsf{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 $\mathsf{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
$\mathsf{AC}^{0}$, outputs some $m\geq 2$ such that $\mathrm{MOD}_{m}$ is
constant-depth reducible to $L$ (implying that $L$ is not in
$\mathsf{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\not=l$ such that the
concrete intermediate VPL $L(S\rightarrow\varepsilon\mid ac^{k-1}Sb_{1}\mid
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
$\mathsf{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 $\mathsf{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 $\mathsf{AC}^{0}$ (when restricted to
well-matched words).

For our proofs we revisit so-called $\operatorname{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

  1. 1 Introduction
  2. 2 Preliminaries
    1. 2.1 Complexity and logic
    2. 2.2 Main result
    3. 2.3 Corollary for visibly counter languages
  3. 3 Language-theoretic and algebraic foundations and Ext-Algebras
    1. 3.1 Basic algebraic automata theory
    2. 3.2 Ext-algebras
  4. 4 (Weak) length-synchronicity, nesting depth, and quasi-aperiodicity
    1. 4.1 A pumping lemma for Ext-algebra morphisms
    2. 4.2 Weak length-synchronicity and length-synchronicity
    3. 4.3 The nesting depth of visibly pushdown languages
    4. 4.4 Quasi-aperiodicity and its correspondence with quasi-counterfreeness
  5. 5 Proof of the main theorem
    1. 5.1 Proof outline for Theorem 2.9
    2. 5.2 Lower bounds
      1. 5.2.1 The non-solvable case
    3. 5.3 In $\mathsf{AC}^{0}$: Length-synchronous and quasi-aperiodic
      1. Approximate matchings.
      2. Horizontal and vertical evaluation languages.
      3. 5.3.1 Strategy for the proof of Theorem 5.7
      4. 5.3.2 $\mathcal{V}_{\varphi_{L}}$ and $\mathcal{V}_{\psi_{L}}$ are quasi-aperiodic (Proof of Point 1)
      5. 5.3.3 Quasi-aperiodicity of evaluation languages $\mathcal{E}_{\varphi_{L},r}$ and $\mathcal{E}_{\psi_{L},e}$ (Proof of Point 2)
      6. 5.3.4 Approximate matching relation in $\mathsf{FO}[\mathsf{+}]$ (Proof of Point 3)
        1. Building an approximate matching assuming predicates $\pi_{e}$.
      7. 5.3.5 Evaluation in $\mathsf{FO}[\mathsf{+}]$ (Proof of Point 4)
    4. 5.4 The intermediate case
      1. 5.4.1 Proof strategy
      2. 5.4.2 Computation of $k,l$
    5. 5.5 Proof of Corollary 2.11
  6. 6 Proof of Proposition 5.1
  7. 7 Conclusion
  8. 8 Some errata in previous work

##  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 $\mathsf{FO}[\mathsf{<}]$ by a result of
McNaughton and Papert [29]. The more general class of regular languages
expressible in $\mathsf{FO}[\mathsf{arb}]$, i.e. first-order logic with
arbitrary numerical predicates, coincides with the regular languages in
$\mathsf{AC}^{0}$ [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 $\mathsf{AC}^{0}$.

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 $\operatorname{Ext}$-algebras [10]; these involve pairs of monoids
$(R,O)$ where $O$ is a submonoid of $R^{R}$. Being tailored towards
recognizing word languages, $\operatorname{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 $\operatorname{Ext}$-algebra is finite. While
context-free languages are generally in $\mathsf{LOGCFL}=\mathsf{SAC}^{1}$,
the visibly pushdown languages, as the regular languages, are known to be in
$\mathsf{NC}^{1}$ [11]. By a famous result of Barrington [4], there already
exist regular languages that are $\mathsf{NC}^{1}$-hard. In this paper we
study the question of which visibly pushdown languages are in
$\mathsf{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 $\operatorname{Ext}$-algebras.
Unfortunately, the definition of $\operatorname{Ext}$-algebra morphisms in
[10] is incorrect in that it provably does not lead to freeness.

The regular languages that are in $\mathsf{AC}^{0}$ were effectively
characterized by Barrington et al. [5]: a regular language is in
$\mathsf{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 $\mathsf{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 $\mathsf{AC}^{0}$. Yet, his
conjectural characterization contains several serious flaws — a detailled
discussion of these shortcomings can be found in Section 8.

Our contribution. We reintroduce $\operatorname{Ext}$-algebras, fix the notion
of $\operatorname{Ext}$-algebra morphisms and define the languages they
recognize. We also reintroduce the syntactic $\operatorname{Ext}$-algebra of
languages of well-matched words. We rigorously prove classical results like
freeness and minimality of syntactic $\operatorname{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
$\operatorname{Ext}$-algebra. While these results essentially revisit the
constructions of [10], we use $\operatorname{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)\geq 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^{\prime},v^{\prime})=(uu^{\prime},v^{\prime}v)$.

We introduce the following notions: a set of contexts $\mathcal{R}$ is length-
synchronous if $|u|/|v|=|u^{\prime}|/|v^{\prime}|$ for all
$(u,v),(u^{\prime},v^{\prime})\in\mathcal{R}$ with
$\Delta(u),\Delta(u^{\prime})>0$ and weakly length-synchronous if
$u=u^{\prime}$ implies $|v|=|v^{\prime}|$ and $v=v^{\prime}$ implies
$|u|=|u^{\prime}|$ for all $(u,v),(u^{\prime},v^{\prime})\in\mathcal{R}$ with
$\Delta(u),\Delta(u^{\prime})>0$. Any language $L$ of well-matched words
induces a congruence $\equiv_{L}$ on contexts:
$(u,v)\equiv_{L}(u^{\prime},v^{\prime})$ if $xuwvy\in L\Leftrightarrow
xu^{\prime}wv^{\prime}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\rightarrow_{G}\varepsilon$,
where $S$ is the start nonterminal and whose other productions are of the form
$T\rightarrow_{G}uT^{\prime}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\geq 1$ with $k\not=l$ a concrete intermediate VPL,
denoted by $\mathcal{L}_{k,l}$ is the one that is generated by the context-
free grammar $S\rightarrow\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 $\mathsf{AC}^{0}$ or provably not in
$\mathsf{AC}^{0}$ — analogous remarks apply to $\mathsf{ACC}^{0}$.

Our main result states that there is an algorithm that, given a DVPA $A$
correctly outputs either $L(A)\in\mathsf{AC}^{0}$, outputs some $m\geq 2$ such
that $\mathrm{MOD}_{m}$ is constant-depth reducible to $L$ (thus witnessing
that $L(A)\not\in\mathsf{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\not=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
$\mathsf{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 $\mathsf{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 $\mathsf{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 $\mathsf{AC}^{0}$ (when restricted to
well-matched words).

For our main result we extensively study $\operatorname{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 $\operatorname{Ext}$-algebras and
their correspondence to visibly pushdown languages. Section 4 introduces
central notions like length-synchronicity and weak length-synchronicity for
$\operatorname{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 $\operatorname{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,\ldots,j\\}$. For any function $f:X\rightarrow Y$ and any subset
$Z\subseteq X$ we denote by ${f|}_{Z}:Z\rightarrow 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
$\left|w\right|_{\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
$\left|w\right|_{a}$ to denote $\left|w\right|_{\\{a\\}}$.

We define the languages

$\mathrm{EQUALITY}=\\{w\in\\{0,1\\}^{*}:|w|_{0}=|w|_{1}\\}\quad\text{~and~}\quad\mathrm{MOD}_{m}=\\{w\in\\{0,1\\}^{*}:m\text{
divides }|w|_{1}\\}$

for each $m\geq 2$.

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

######  Definition 2.1.

The set of _well-matched words over a visibly pushdown alphabet $\Sigma$_,
denoted by $\Sigma^{\triangle}$, is the smallest set satisfying the following:

  * •

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

  * •

$awb\in\Sigma^{\triangle}$ for all $w\in\Sigma^{\triangle}$,
$a\in\Sigma_{\text{call}}$ and $b\in\Sigma_{\text{ret}}$, and

  * •

$uv\in\Sigma^{\triangle}$ for all
$u,v\in\Sigma^{\triangle}\setminus\\{\varepsilon\\}$.

A well-matched word $w\in\Sigma^{\triangle}$ is one-turn if
$w\in(\Sigma\setminus\Sigma_{\text{ret}})^{*}(\Sigma\setminus\Sigma_{\text{call}})^{*}$.
A language $L\subseteq\Sigma^{\triangle}$ is one-turn if it contains only one-
turn words. Let $\Sigma$ be a visibly pushdown alphabet. We define
$\Delta\colon\Sigma^{*}\to\mathbb{Z}$ to be the height monoid morphism such
that $\Delta(w)=\left|w\right|_{\Sigma_{call}}-\left|w\right|_{\Sigma_{ret}}$
for all $w\in\Sigma^{*}$. A context is a pair
$(u,v)\in\Sigma^{*}\times\Sigma^{*}$ such that $uv\in\Sigma^{\triangle}$. The
_composition_ of two contexts $(u,v),(x,y)\in\mathsf{Con}(\Sigma)$ is defined
as $(u,v)\circ(x,y)=(ux,yv)$. For $\sigma\in\mathsf{Con}(\Sigma)$ by
$\sigma^{k}$ we denote the $k$-fold composition $\sigma\circ\dots\circ\sigma$.
For any context $(u,v)\in\mathsf{Con}(\Sigma)$ and well-matched word
$w\in\Sigma^{\triangle}$ we define $(u,v)w=uwv$. An equivalence relation
$\equiv$ on $\mathsf{Con}(\Sigma)$ is a _congruence_ if for all
$\chi,\chi^{\prime},\sigma,\tau\in\mathsf{Con}(\Sigma)$ we have that
$\sigma\equiv\tau$ implies
$\chi\circ\sigma\circ\chi^{\prime}\equiv\chi\circ\tau\circ\chi^{\prime}$.
Given a congruence $\equiv$ over $\mathsf{Con}(\Sigma)$ we denote by
$[\sigma]_{\equiv}$ the equivalence class of $\sigma$. Given a language of
well-matched words $L\subseteq\Sigma^{\triangle}$ we write
$\sigma\equiv_{L}\tau$ if for all $\chi\in\mathsf{Con}(\Sigma)$ and all
$w\in\Sigma^{\triangle}$ 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\rightarrow_{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\rightarrow_{G}y$ and
$x,z\in(V\cup\Sigma)^{*}$ such that $u=xTz$ and $v=xyz$. By
$L(G)=\\{w\in\Sigma^{*}\mid 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 nondeterministic visibly pushdown automata are determinizable
[2].

######  Definition 2.2.

A _deterministic visibly pushdown automaton_ (DVPA) is a tuple
$A=(Q,\Sigma,\Gamma,\delta,\allowbreak q_{0},F,\bot)$, 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_ ,

  * •

$\bot\in\Gamma$ is the _bottom-of-stack symbol_ , and

  * •

$\delta\colon Q\times\Sigma\times\Gamma\to
Q\times\bigl{(}\\{\varepsilon\\}\cup\Gamma\cup(\Gamma\setminus\\{\bot\\})\Gamma\bigr{)}$
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\\{\bot\\})\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_ $\widehat{\delta}\colon
Q\times\Sigma^{*}\times\Gamma^{*}\to Q\times\Gamma^{*}$ inductively as

  * •

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

  * •

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

  * •

$\widehat{\delta}(q,aw,\alpha\beta)=\widehat{\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\mathopen{}\left(A\right)\mathclose{}=\\{w\in\Sigma^{*}\mid\widehat{\delta}(q_{0},w,\bot)\in
F\times\\{\bot\\}\\}$. We call such a language a _visibly pushdown language_
(VPL). We remark that visibly pushdown languages are always subsets of
$\Sigma^{\triangle}$.

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},\ldots,x_{d}),\vec{y}=(y_{1},\ldots,y_{d})\in\mathbb{N}^{d}$
we define $\vec{x}+\vec{y}=(x_{1}+y_{1},\ldots,x_{d}+y_{d})$. We define the
norm of a vector $\vec{x}\in\mathbb{N}^{d}$ as
$\lVert\vec{x}\rVert=\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},\ldots,x_{d})\in\mathbb{N}^{d}$ and
$n\in\mathbb{N}$ we define $n\vec{x}=(nx_{1},\ldots,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},\ldots,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 $1$s), and the $\text{mod}_{m}$ function (that
outputs $1$ if the number of its inputs that are $1$s is divisible by $m$) for
all $m\geq 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_{\text{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_{\text{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=_{\text{cd}}L$ if $K\leq_{\text{cd}}L$ and $L\leq_{\text{cd}}K$; we also
say that $K$ and $L$ are constant-depth equivalent. We say a language $L$ is
hard for a complexity class $\mathsf{C}$ (or just $\mathsf{C}$-hard) if
$L^{\prime}\leq_{\text{cd}}L$ for all $L^{\prime}\in\mathsf{C}$. We say $L$ is
$\mathsf{C}$-complete if $L$ is $\mathsf{C}$-hard and $L\in\mathsf{C}$. The
following complexity classes are relevant in this paper:

  * •

$\mathsf{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;

  * •

$\mathsf{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;

  * •

$\mathsf{TC}^{0}$ 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;

  * •

$\mathsf{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\in\mathbb{N}_{>0}$_ is a symbol of arity $r$ associated to a subset
of ${\mathbb{N}_{>0}}^{r}$. Given a class $\mathcal{C}$ of numerical
predicates and a finite alphabet $\Sigma$, we call
$\mathsf{FO}_{\Sigma}[\mathcal{C}]$-formula a first order formula over finite
words using the alphabet $\Sigma$ and numerical predicates from the class
$\mathcal{C}$. On occasions, we might also consider
$\mathsf{FO}_{\Sigma,\leftrightsquigarrow}[\mathcal{C}]$-formulas that in
comparison to the previous ones can use an additional binary predicate
$\leftrightsquigarrow$ and are interpreted on structures $(w,M)$ with
$w\in\Sigma^{*}$ and
$M\subseteq[1,\mathopen{}\left|w\right|\mathclose{}]^{2}$, where everything is
interpreted as for $\mathsf{FO}_{\Sigma}[\mathcal{C}]$-formulas on $w$
excepted for $\leftrightsquigarrow$ that is interpreted by $M$. Given a class
$\mathcal{C}$ of numerical predicates, by $\mathsf{FO}[\mathcal{C}]$ we denote
the class of all languages over any finite alphabet $\Sigma$ defined by a
$\mathsf{FO}_{\Sigma}[\mathcal{C}]$-sentence. A classical result at the
interplay of circuit complexity and logic is that
$\mathsf{AC}^{0}=\mathsf{FO}[\mathsf{arb}]$, where $\mathsf{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 $\mathsf{MOD}_{m}$ for all $m\in\mathbb{N}_{>0}$ (gathered
together in the set $\mathsf{MOD}=\\{\mathsf{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\mathsf{Con}(\Sigma)$ be a set of contexts.

  * •

$\mathcal{R}$ is length-synchronous if
$\mathopen{}\left|u\right|\mathclose{}/\mathopen{}\left|v\right|\mathclose{}=\mathopen{}\left|u^{\prime}\right|\mathclose{}/\mathopen{}\left|v^{\prime}\right|\mathclose{}$
for all $(u,v),(u^{\prime},v^{\prime})\in\mathcal{R}$ with
$\Delta(u),\Delta(u^{\prime})>0$.

  * •

$\mathcal{R}$ is weakly length-synchronous if $u=u^{\prime}$ implies
$\mathopen{}\left|v\right|\mathclose{}=\mathopen{}\left|v^{\prime}\right|\mathclose{}$
and $v=v^{\prime}$ implies $|u|=|u^{\prime}|$ for all
$(u,v),(u^{\prime},v^{\prime})\in\mathcal{R}$ with
$\Delta(u),\Delta(u^{\prime})>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^{\prime})\in\mathcal{R}$, where
$\mathopen{}\left|v\right|\mathclose{}\not=\mathopen{}\left|v^{\prime}\right|\mathclose{}$
and $\Delta(u)>0$, then
$\mathopen{}\left|u\right|\mathclose{},\mathopen{}\left|v\right|\mathclose{},\mathopen{}\left|v^{\prime}\right|\mathclose{}>0$
and so the quotients
$\frac{\mathopen{}\left|u\right|\mathclose{}}{\mathopen{}\left|v\right|\mathclose{}}$
and
$\frac{\mathopen{}\left|u\right|\mathclose{}}{\mathopen{}\left|v^{\prime}\right|\mathclose{}}$
are distinct, thus violating length-synchronicity of $\mathcal{R}$.

######  Definition 2.4 (Quasi-Counterfree).

A VPL $L\subseteq\Sigma^{\triangle}$ is quasi-counterfree if for all
$\sigma=(u,v)\in\mathsf{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\mathsf{Con}(\Sigma)$ we have
$\tau\not\equiv_{L}\sigma\circ\sigma$.

We will later show that quasi-counterfreeness of a VPL
$L\subseteq\Sigma^{\triangle}$ is equivalent to the condition that there is no
$k,l\in\mathbb{N}$ such that there is a subset of
$\mathsf{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_{\text{call}}=\\{a\\}$, $\Sigma_{\text{int}}=\\{c\\}$ and
$\Sigma_{\text{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\rightarrow ac^{k-1}Sb_{1}\mid
ac^{l-1}Sb_{2}\mid\varepsilon\,\,\text{.}$ We have that the set of contexts
$\\{(u,v)\in\mathsf{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\rightarrow_{G}\varepsilon$, and all other productions of $G$ are of the
form $T\rightarrow_{G}uT^{\prime}v$, where $uv\in\Sigma^{\triangle}$ is one-
turn such that
$u\in(\Sigma_{\text{int}}^{*}\Sigma_{\text{call}}\Sigma_{\text{int}}^{*})^{+}$
and
$v\in(\Sigma_{\text{int}}^{*}\Sigma_{\text{ret}}\Sigma_{\text{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\mathsf{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 $\mathsf{ACC}^{0}$ or
$\mathsf{TC}^{0}$-hard under constant-depth reductions.

In fact, the authors are not even aware of any intermediate VPL that is
provably not in $\mathsf{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\mathsf{AC}^{0}$,

  * •

$m\geq 2$ such that $\mathrm{MOD}_{m}\leq_{\text{cd}}L(A)$ (hence implying
$L(A)\not\in\mathsf{AC}^{0}$),

  * •

vertically visibly pushdown grammars $G_{1},\dots,G_{m}$ each generating
intermediate VPLs such that $L=_{\text{cd}}\biguplus_{i=1}^{m}L(G_{i})$. In
this case one can moreover effectively compute $k,l\in\mathbb{N}$ with
$k\not=l$ such that $\mathcal{L}_{k,l}\leq_{\text{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 $\mathsf{AC}^{0}$.

######  Conjecture 2.10.

Either all intermediate VPLs are in $\mathsf{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\geq 0$ is a threshold, and $\delta_{i}:Q\times\Sigma\rightarrow 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^{\prime},n^{\prime})$ and any $x\in\Sigma$ we define
$(q,n)\xrightarrow{x}_{A}(q^{\prime},n^{\prime})$ if
$q^{\prime}=\delta_{\min(n,m)}(q,x)$ and $n^{\prime}=n+\Delta(x)$. The
relation $\xrightarrow{x}_{A}$ is naturally extended to $\xrightarrow{w}_{A}$
for $w\in\Sigma^{*}$. By $L(A)=\\{w\in\Sigma^{\triangle}\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 $\mathsf{AC}^{0}$ or some $m\geq 2$ such that
$\mathrm{MOD}_{m}\leq_{\text{cd}}L(A)$ (hence implying
$L(A)\not\in\mathsf{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 $\left|M\right|=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\mathclose{}/\mathopen{}\equiv$ with base
set $M\mathclose{}/\mathopen{}\equiv=\\{[m]_{\equiv}\mid 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^{\prime}\in M$ such that
$xx^{\prime}=x^{\prime}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\colon 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\colon\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\colon\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
$\operatorname{Ext}$-algebra morphisms to establish freeness.

Let $(M,\cdot,1_{M})$ be a monoid. For each $m\in M$, we shall respectively
denote by $\mathrm{left}_{m}$ and $\mathrm{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 _$\operatorname{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 $\mathrm{left}_{r}$ and
$\mathrm{right}_{r}$ for each $r\in R$.

######  Definition 3.2.

Let $(R,O)$ and $(S,P)$ be $\operatorname{Ext}$-algebras. An
_$\operatorname{Ext}$ -algebra morphism from $(R,O)$ to $(S,P)$_ is a pair
$(\varphi,\psi)$ of monoid morphisms $\varphi\colon R\to S$ and $\psi\colon
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(\mathrm{left}_{r})=\mathrm{left}_{\varphi(r)}$
and $\psi(\mathrm{right}_{r})=\mathrm{right}_{\varphi(r)}$.

We write $(\varphi,\psi)\colon(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
_$\operatorname{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(\mathrm{left}_{r}(1_{R}))=\psi(\mathrm{left}_{r})(\varphi(1_{R}))=\psi(\mathrm{left}_{r})(1_{S})$.

######  Definition 3.4.

Let $(R,O)$ and $(S,P)$ be $\operatorname{Ext}$-algebras. Then

  * •

$(R,O)$ is a _sub- $\operatorname{Ext}$-algebra_ of $(S,P)$ whenever $R$ is a
submonoid of $S$ and there exists a submonoid $O^{\prime}$ of $P$ such that
$O=\\{{e|}_{R}\mid e\in O^{\prime}\\}$, so that we may denote $O$ by
${O^{\prime}|}_{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-$\operatorname{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\mathsf{Con}(\Sigma)$, consider the function
$\operatorname{ext}_{u,v}\colon\Sigma^{\triangle}\to\Sigma^{*}$ such that
$\operatorname{ext}_{u,v}(x)=uxv$ for all $x\in\Sigma^{\triangle}$. We call

$\operatorname{ext}_{u,v}\quad=\quad\operatorname{ext}_{x_{1},y_{1}}\circ\cdots\circ\operatorname{ext}_{x_{m},y_{m}}$

a factorization of $\operatorname{ext}_{u,v}$. That is, $u=x_{1}\dots x_{m}$,
$v=y_{m}\cdots y_{1}$.

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

######  Lemma 3.6.

For all $\operatorname{ext}_{u,v}$ there exists a unique factorization

$\operatorname{ext}_{u,v}\quad=\quad\operatorname{ext}_{x_{1},y_{1}}\circ\operatorname{ext}_{a_{1},b_{1}}\circ\quad\cdots\quad\circ\operatorname{ext}_{x_{h-1},y_{h-1}}\circ\operatorname{ext}_{a_{h-1},b_{h-1}}\circ\operatorname{ext}_{x_{h},y_{h}}$

satisfying $h\geq 1$, $x_{i},y_{i}\in\Sigma^{\triangle}$ 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, $\operatorname{ext}_{u,v}$ is in fact a function
from $\Sigma^{\triangle}$ to $\Sigma^{\triangle}$.

###### 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|\leq 1$, then either
$\operatorname{ext}_{u,v}=\operatorname{ext}_{\varepsilon,\varepsilon}$, or
there is some $c\in\Sigma_{\text{int}}$ such that
$\operatorname{ext}_{u,v}=\operatorname{ext}_{\varepsilon,c}$ or
$\operatorname{ext}_{u,v}=\operatorname{ext}_{c,\varepsilon}$. In any of these
cases, we uniquely factorize $\operatorname{ext}_{u,v}$ as
$\operatorname{ext}_{x_{1},y_{1}}$ with $x_{1}=u$ and $y_{1}=v$.

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

$\operatorname{ext}_{x,y}\circ\operatorname{ext}_{a,b}\circ\operatorname{ext}_{x_{1},y_{1}}\circ\operatorname{ext}_{a_{1},b_{1}}\circ\cdots\circ\operatorname{ext}_{x_{h-2},y_{h-2}}\circ\operatorname{ext}_{a_{h-2},b_{h-2}}\circ\operatorname{ext}_{x_{h-1},y_{h-1}}$

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

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

######  Proposition 3.7.

Let $(R,O)$ be an $\operatorname{Ext}$-algebra and consider two functions
$\varphi\colon\Sigma_{\text{int}}\to R$ and
$\psi\colon\\{\operatorname{ext}_{a,b}\mid
a\in\Sigma_{\text{call}},b\in\Sigma_{\text{ret}}\\}\to O$. Then there exists a
unique $\operatorname{Ext}$-algebra morphism
$(\overline{\varphi},\overline{\psi})$ from
$(\Sigma^{\triangle},\mathcal{O}(\Sigma^{\triangle}))$ to $(R,O)$ satisfying
$\overline{\varphi}(c)=\varphi(c)$ for each $c\in\Sigma_{\text{int}}$ and
$\overline{\psi}(\operatorname{ext}_{a,b})=\psi(\operatorname{ext}_{a,b})$ for
each $a\in\Sigma_{\text{call}},b\in\Sigma_{\text{ret}}$.

###### Proof.

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

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

Observe that the four above types give unique decompositions. For proving that
$\overline{\varphi}$ is indeed a monoid morphism one proves that for all
$w,v\in\Sigma^{\triangle}$ we have
$\overline{\varphi}(wv)=\overline{\varphi}(w)\overline{\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^{\triangle}\setminus\\{\varepsilon\\}$ in the following. If $w$ is
of type 1 we have
$\overline{\varphi}(wv)=\overline{\varphi}(v)=1_{R}\cdot\overline{\varphi}(v)=\overline{\varphi}(w)\overline{\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^{\triangle}\setminus\\{\varepsilon\\}$, hence
$\overline{\varphi}(wv)=\overline{\varphi}(w)\overline{\varphi}(v)$. If $w$ is
of type 4, then $w=xy$ for some
$x,y\in\Sigma^{\triangle}\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^{\triangle}\setminus\\{\varepsilon\\}$. Hence
$\overline{\varphi}(wv)=\overline{\varphi}(x)\overline{\varphi}(yv)=\overline{\varphi}(x)\overline{\varphi}(y)\overline{\varphi}(v)=\overline{\varphi}(xy)\overline{\varphi}(v)=\overline{\varphi}(w)\overline{\varphi}(v)$,
where the first equality follows by definition of $\overline{\varphi}$ and the
second and third equality follow from the induction hypothesis. Given any
$\operatorname{ext}_{u,v}\in\mathcal{O}(\Sigma^{\triangle})$ let

$\operatorname{ext}_{u,v}\quad=\quad\operatorname{ext}_{x_{1},y_{1}}\circ\operatorname{ext}_{a_{1},b_{1}}\circ\quad\cdots\quad\circ\operatorname{ext}_{x_{h-1},y_{h-1}}\circ\operatorname{ext}_{a_{h-1},b_{h-1}}\circ\operatorname{ext}_{x_{h},y_{h}}$

be the unique stair factorization given by Lemma 3.6. We define

$\overline{\psi}(\operatorname{ext}_{u,v})=\bigcirc_{i=1}^{h-1}\bigl{(}\mathrm{left}_{\overline{\varphi}(x_{i})}\circ\mathrm{right}_{\overline{\varphi}(y_{i})}\circ\psi(\operatorname{ext}_{a_{i},b_{i}})\bigr{)}\circ\mathrm{left}_{\overline{\varphi}(x_{h})}\circ\mathrm{right}_{\overline{\varphi}(y_{h})}\,\,\text{.}$

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

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

$\operatorname{ext}_{u,v}\quad=\quad\operatorname{ext}_{x_{1},y_{1}}\circ\operatorname{ext}_{a_{1},b_{1}}\circ\quad\cdots\quad\circ\operatorname{ext}_{x_{h-1},y_{h-1}}\circ\operatorname{ext}_{a_{h-1},b_{h-1}}\circ\operatorname{ext}_{x_{h},y_{h}}$

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

$\overline{\psi}(\operatorname{ext}_{u,v})(\overline{\varphi}(w))=\mathrm{left}_{\overline{\varphi}(x_{h})}\circ\mathrm{right}_{\overline{\varphi}(y_{h})}(\overline{\varphi}(w))=\overline{\varphi}(x_{h}wy_{h})=\overline{\varphi}(\operatorname{ext}_{u,v}(w))\,\,\text{.}$

Otherwise, we have

$\displaystyle\overline{\psi}(\operatorname{ext}_{u,v})(\overline{\varphi}(w))$
$\displaystyle=$
$\displaystyle\bigcirc_{i=1}^{h-1}\bigl{(}\mathrm{left}_{\overline{\varphi}(x_{i})}\circ\mathrm{right}_{\overline{\varphi}(y_{i})}\circ\psi(\operatorname{ext}_{a_{i},b_{i}})\bigr{)}\circ\mathrm{left}_{\overline{\varphi}(x_{h})}\circ\mathrm{right}_{\overline{\varphi}(y_{h})}(\overline{\varphi}(w))$
$\displaystyle=$
$\displaystyle\bigcirc_{i=1}^{h-1}\bigl{(}\mathrm{left}_{\overline{\varphi}(x_{i})}\circ\mathrm{right}_{\overline{\varphi}(y_{i})}\circ\psi(\operatorname{ext}_{a_{i},b_{i}})\bigr{)}\bigl{(}\overline{\varphi}(x_{h}wy_{h})\bigr{)}$
$\displaystyle=$
$\displaystyle\bigcirc_{i=1}^{h-2}\bigl{(}\mathrm{left}_{\overline{\varphi}(x_{i})}\circ\mathrm{right}_{\overline{\varphi}(y_{i})}\circ\psi(\operatorname{ext}_{a_{i},b_{i}})\bigr{)}\circ$
$\displaystyle\mathrm{left}_{\overline{\varphi}(x_{h-1})}\circ\mathrm{right}_{\overline{\varphi}(y_{h-1})}\circ\psi(\operatorname{ext}_{a_{h-1},b_{h-1}})\bigl{(}\overline{\varphi}(x_{h}wy_{h})\bigr{)}$
$\displaystyle=$
$\displaystyle\bigcirc_{i=1}^{h-2}\bigl{(}\mathrm{left}_{\overline{\varphi}(x_{i})}\circ\mathrm{right}_{\overline{\varphi}(y_{i})}\circ\psi(\operatorname{ext}_{a_{i},b_{i}})\bigr{)}\circ$
$\displaystyle\mathrm{left}_{\overline{\varphi}(x_{h-1})}\circ\mathrm{right}_{\overline{\varphi}(y_{h-1})}\bigl{(}\overline{\varphi}(a_{h-1}x_{h}wy_{h}b_{h-1})\bigr{)}$
$\displaystyle=$
$\displaystyle\bigcirc_{i=1}^{h-2}\bigl{(}\mathrm{left}_{\overline{\varphi}(x_{i})}\circ\mathrm{right}_{\overline{\varphi}(y_{i})}\circ\psi(\operatorname{ext}_{a_{i},b_{i}})\bigr{)}\bigl{(}\overline{\varphi}(x_{h-1}a_{h-1}x_{h}wy_{h}b_{h-1}y_{h-1})\bigr{)}$
$\displaystyle=$ $\displaystyle\cdots$ $\displaystyle=$
$\displaystyle\overline{\varphi}(x_{1}a_{1}\cdots
x_{h-1}a_{h-1}x_{h}wy_{h}b_{h-1}y_{h-1}\cdots b_{1}y_{1})$ $\displaystyle=$
$\displaystyle\overline{\varphi}(\operatorname{ext}_{u,v}(w))\,\,\text{.}$

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

$\overline{\psi}(\mathrm{left}_{w})=\overline{\psi}(\operatorname{ext}_{w,\varepsilon})=\mathrm{left}_{\overline{\varphi}(w)}\circ\mathrm{right}_{\overline{\varphi}(\varepsilon)}=\mathrm{left}_{\overline{\varphi}(w)}\circ\mathrm{right}_{1_{R}}=\mathrm{left}_{\overline{\varphi}(w)}\circ
1_{O}=\mathrm{left}_{\overline{\varphi}(w)}\,\,\text{.}$

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

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

######  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 $\operatorname{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_{\text{call}}=\\{a\\}$, $\Gamma_{\text{int}}=\emptyset$ and
$\Gamma_{\text{ret}}=\\{b\\}$, where $R$ the is 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 $\\{\mathrm{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 $\operatorname{Ext}$-algebra. Let us define the function
$\varphi\colon\Gamma^{\triangle}\to R$ by $\varphi(w)=1$ for all
$w\in\Gamma^{\triangle}$ and the function
$\psi\colon\mathcal{O}(\Gamma^{\triangle})\to O$ by
$\psi(\operatorname{ext}_{a^{n},b^{n}})=\mathrm{id}$ for all $n\in\mathbb{N}$
and $\psi(\operatorname{ext}_{u,v})=\mathbf{1}$ for all $u,v\in\Gamma^{*}$
with $uv\in\Gamma^{\triangle}$ and $(u\in a\Gamma^{*}b\Gamma^{*}$ or
$v\in\Gamma^{*}a\Gamma^{*}b)$. The pair $(\varphi,\psi)$ forms a morphism from
$(\Gamma^{\triangle},\mathcal{O}(\Gamma^{\triangle}))$ to $(R,O)$, but it is
not the only one sending $\operatorname{ext}_{a,b}$ to $\mathrm{id}$, because
we could also take $\psi$ to send all elements of
$\mathcal{O}(\Gamma^{\triangle})$ to $\mathrm{id}$.

######  Definition 3.9.

A language $L\subseteq\Sigma^{\triangle}$ is _recognized_ by an
$\operatorname{Ext}$-algebra $(R,O)$ whenever there exists a morphism
$(\varphi,\psi)\colon(\Sigma^{\triangle},\mathcal{O}(\Sigma^{\triangle}))\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\rightarrow aSb_{1}\mid
acSb_{2}\mid\varepsilon)$ from Example 2.5 over the visibly pushdown alphabet
$\Gamma$, where $\Gamma_{\text{int}}=\\{c\\}$, $\Gamma_{\text{call}}=\\{a\\}$
and $\Gamma_{\text{ret}}=\\{b_{1},b_{2}\\}$. Consider the
$\operatorname{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:

$\begin{array}[b]{c|c|c|c|c|c|}\cdot&acb_{1}&\varepsilon&c&cab_{1}&ab_{1}\\\
\hline\cr acb_{1}&acb_{1}&acb_{1}&acb_{1}&acb_{1}&acb_{1}\\\
\hline\cr\varepsilon&acb_{1}&\varepsilon&c&cab_{1}&ab_{1}\\\ \hline\cr
c&acb_{1}&c&acb_{1}&acb_{1}&cab_{1}\\\ \hline\cr
cab_{1}&acb_{1}&cab_{1}&acb_{1}&acb_{1}&acb_{1}\\\ \hline\cr
ab_{1}&acb_{1}&ab_{1}&acb_{1}&acb_{1}&acb_{1}\\\ \hline\cr\end{array}$

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

$\displaystyle O$ $\displaystyle=$
$\displaystyle\\{(acb_{1},\varepsilon),(\varepsilon,\varepsilon),(c,\varepsilon),(\varepsilon,c),(ab_{1},\varepsilon),(\varepsilon,ab_{1}),(cab_{1},\varepsilon)\\}\
\cup$
$\displaystyle\\{(a,b_{2}),(ca,b_{2}),(ca,ab_{1}b_{2}),(ca,b_{1}),(a,ab_{1}b_{2}),(a,b_{1})\\},$

where the elements in the first set comprise
$\\{\mathrm{left}_{r},\mathrm{right}_{r}\mid r\in R\\}$, more precisely

  * •

$(acb_{1},\varepsilon)=\mathrm{left}_{acb_{1}}=\mathrm{right}_{acb_{1}}$,

  * •

$(\varepsilon,\varepsilon)=\mathrm{left}_{\varepsilon}=\mathrm{right}_{\varepsilon}=1_{O}$,

  * •

$(c,\varepsilon)=\mathrm{left}_{c}$,

  * •

$(\varepsilon,c)=\mathrm{right}_{c}$,

  * •

$(ab_{1},\varepsilon)=\mathrm{left}_{ab_{1}}$,

  * •

$(\varepsilon,ab_{1})=\mathrm{right}_{ab_{1}}$,

  * •

$(cab_{1},\varepsilon)=\mathrm{left}_{cab_{1}}=\mathrm{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}[b]{c||c|c|c|c|c|}r&acb_{1}&\varepsilon&c&cab_{1}&ab_{1}\\\
\hline\cr(a,b_{2})(r)&acb_{1}&acb_{1}&ab_{1}&ab_{1}&acb_{1}\end{array}$

  * •

$(ca,b_{2})$:

$\begin{array}[b]{c||c|c|c|c|c|}r&acb_{1}&\varepsilon&c&cab_{1}&ab_{1}\\\
\hline\cr(ca,b_{2})(r)&acb_{1}&acb_{1}&cab_{1}&cab_{1}&acb_{1}\end{array}$

  * •

$(ca,ab_{1}b_{2})$:

$\begin{array}[b]{c||c|c|c|c|c|}r&acb_{1}&\varepsilon&c&cab_{1}&ab_{1}\\\
\hline\cr(ca,ab_{1}b_{2})(r)&acb_{1}&acb_{1}&cab_{1}&acb_{1}&acb_{1}\end{array}$

  * •

$(ca,b_{1})$:

$\begin{array}[b]{c||c|c|c|c|c|}r&acb_{1}&\varepsilon&c&cab_{1}&ab_{1}\\\
\hline\cr(ca,b_{1})(r)&acb_{1}&cab_{1}&acb_{1}&acb_{1}&cab_{1}\end{array}$

  * •

$(a,ab_{1}b_{2})$:

$\begin{array}[b]{c||c|c|c|c|c|}r&acb_{1}&\varepsilon&c&cab_{1}&ab_{1}\\\
\hline\cr(a,ab_{1}b_{2})(r)&acb_{1}&acb_{1}&ab_{1}&acb_{1}&acb_{1}\end{array}$

  * •

$(a,b_{1})$:

$\begin{array}[b]{c||c|c|c|c|c|}r&acb_{1}&\varepsilon&c&cab_{1}&ab_{1}\\\
\hline\cr(a,b_{1})(r)&acb_{1}&ab_{1}&acb_{1}&acb_{1}&ab_{1}\end{array}\,\,\text{.}$

Consider the unique morphism
$(\varphi,\psi)\colon(\Gamma^{\triangle},\mathcal{O}(\Gamma^{\triangle}))\to(R,O)$
that (thanks to Proposition 3.7) satisfies $\varphi(c)=c$,
$\psi(\operatorname{ext}_{a,b_{1}})=(a,b_{1})$ and
$\psi(\operatorname{ext}_{a,b_{2}})=(a,b_{2})$. We have
$L=\varphi^{-1}(\\{\varepsilon,ab_{1}\\})$.

######  Definition 3.11.

Let $(R,O)$ be an $\operatorname{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)\mathclose{}/\mathopen{}\sim$ the pair
$(R\mathclose{}/\mathopen{}\sim,O^{\prime})$, where

$O^{\prime}=\\{e^{\prime}\in(R\mathclose{}/\mathopen{}\sim)^{R\mathclose{}/\mathopen{}\sim}\mid\exists
e\in O\ \forall x\in R\colon e^{\prime}([x]_{\sim})=[e(x)]_{\sim}\\}.$

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

######  Lemma 3.12.

Let $(R,O)$ be an $\operatorname{Ext}$-algebra and $\sim$ be a congruence on
$(R,O)$. Then $(R\mathclose{}/\mathopen{}\sim,O^{\prime})$, with

$O^{\prime}=\\{e^{\prime}\in(R\mathclose{}/\mathopen{}\sim)^{R\mathclose{}/\mathopen{}\sim}\mid\exists
e\in O\ \forall x\in R\colon e^{\prime}([x]_{\sim})=[e(x)]_{\sim}\\}$

a submonoid of
$(R\mathclose{}/\mathopen{}\sim)^{R\mathclose{}/\mathopen{}\sim}$, is an
$\operatorname{Ext}$-algebra and the pair $(\varphi,\psi)$ of functions
$\varphi\colon R\to R\mathclose{}/\mathopen{}\sim$ and $\psi\colon O\to
O^{\prime}$ 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\mathclose{}/\mathopen{}\sim,O^{\prime})$.

###### 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\mathclose{}/\mathopen{}\sim$ is a monoid.

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

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

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

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

$\displaystyle\psi(e)\circ\psi(f)([r]_{\sim})$
$\displaystyle=\psi(e)([f(r)]_{\sim})$ $\displaystyle=[e(f(r))]_{\sim}$
$\displaystyle=[e\circ f(r)]_{\sim}$ $\displaystyle=\psi(e\circ
f)([r]_{\sim})$

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(\mathrm{left}_{r})([x]_{\sim})=[\mathrm{left}_{r}(x)]_{\sim}=[rx]_{\sim}=[r]_{\sim}[x]_{\sim}=\mathrm{left}_{\varphi(r)}([x]_{\sim})$

for all $x\in R$, so that
$\psi(\mathrm{left}_{r})=\mathrm{left}_{\varphi(r)}$. Similarly, we can prove
that $\psi(\mathrm{right}_{r})=\mathrm{right}_{\varphi(r)}$ for all $r\in R$.
Thus, $(\varphi,\psi)$ is a surjective morphism from $(R,O)$ to
$(R\mathclose{}/\mathopen{}\sim,O^{\prime})$. ∎

The lemma also proves that the pair $(\varphi,\psi)$ of functions
$\varphi\colon R\to R\mathclose{}/\mathopen{}\sim$ and $\psi\colon O\to
O^{\prime}$ 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)\mathclose{}/\mathopen{}\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^{\triangle}$_ is the
congruence $\sim_{L}$ on
$(\Sigma^{\triangle},\mathcal{O}(\Sigma^{\triangle}))$ defined by $u\sim_{L}v$
for $u,v\in\Sigma^{\triangle}$ whenever $e(u)\in L\Leftrightarrow e(v)\in L$
for all $e\in\mathcal{O}(\Sigma^{\triangle})$. We define the _syntactic
$\operatorname{Ext}$-algebra of $L$_ to be
$(R_{L},O_{L})=(\Sigma^{\triangle},\mathcal{O}(\Sigma^{\triangle}))\mathclose{}/\mathopen{}\sim_{L}$
and the _syntactic morphism of $L$_ to be the morphism
$(\varphi_{L},\psi_{L})$ associated to $\sim_{L}$.

Note that the syntactic $\operatorname{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^{\triangle}$, 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
$\operatorname{Ext}$-algebra recognizing the language $\mathcal{L}_{1,2}$ in
Example 3.10 is in fact a certain presentation of the syntactic
$\operatorname{Ext}$-algebra of $\mathcal{L}_{1,2}$.

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

######  Lemma 3.14.

Let $(R,O)$ and $(S,P)$ be two $\operatorname{Ext}$-algebras such that $(R,O)$
divides $(S,P)$. Then any language $L\subseteq\Sigma^{\triangle}$ recognized
by $(R,O)$ is also recognized by $(S,P)$.

###### Proof.

Let $L\subseteq\Sigma^{\triangle}$ be a language recognized by $(R,O)$. This
means that there exists a morphism
$(\varphi,\psi)\colon(\Sigma^{\triangle},\mathcal{O}(\Sigma^{\triangle}))\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. (1)

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

  2. (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-$\operatorname{Ext}$-algebra of
$(S,P)$. This means that $R$ is a submonoid of $S$ and that there exists a
submonoid $O^{\prime}$ of $P$ satisfying $O={O^{\prime}|}_{R}$. Take an
arbitrary function $\sigma\colon O\to P$ such that ${\sigma(e)|}_{R}=e$ for
all $e\in O$. Let us consider the unique morphism
$(\varphi^{\prime},\psi^{\prime})\colon(\Sigma^{\triangle},\mathcal{O}(\Sigma^{\triangle}))\to(S,P)$
such that $\varphi^{\prime}(c)=\varphi(c)$ for all $c\in\Sigma_{\text{int}}$
and
$\psi^{\prime}(\operatorname{ext}_{a,b})=\sigma(\psi(\operatorname{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^{\prime}(w)=\varphi(w)$ for all $w\in\Sigma^{\triangle}$:

  * •

$w=\varepsilon$. Then $\varphi^{\prime}(w)=1_{S}=1_{R}=\varphi(w)$.

  * •

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

  * •

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

$\displaystyle\varphi^{\prime}(w)$
$\displaystyle=\varphi^{\prime}(\operatorname{ext}_{a,b}(w^{\prime}))$
$\displaystyle=\psi^{\prime}(\operatorname{ext}_{a,b})(\varphi^{\prime}(w^{\prime}))$
$\displaystyle\stackrel{{\scriptstyle\text{IH}}}{{=}}\sigma(\psi(\operatorname{ext}_{a,b}))(\varphi(w^{\prime}))$
$\displaystyle={\sigma(\psi(\operatorname{ext}_{a,b}))|}_{R}(\varphi(w^{\prime}))$
$\displaystyle=\psi(\operatorname{ext}_{a,b})(\varphi(w^{\prime}))$
$\displaystyle=\varphi(\operatorname{ext}_{a,b}(w^{\prime}))$
$\displaystyle=\varphi(w)\,\,\text{.}$

  * •

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

$\varphi^{\prime}(w)=\varphi^{\prime}(u)\varphi^{\prime}(v)\stackrel{{\scriptstyle\text{IH}}}{{=}}\varphi(u)\varphi(v)=\varphi(w)\,\,\text{.}$

Thus, $\varphi^{\prime-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)\colon(S,P)\to(R,O)$. Let us
define an arbitrary function $\rho\colon\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\colon\\{\operatorname{ext}_{a,b}\mid
a\in\Sigma_{\text{call}},b\in\Sigma_{\text{ret}}\\}\to P$ such that
$\sigma(\operatorname{ext}_{a,b})\in\beta^{-1}(\psi(\operatorname{ext}_{a,b}))$
for all $a\in\Sigma_{\text{call}},b\in\Sigma_{\text{ret}}$. Now, take the
unique morphism
$(\varphi^{\prime},\psi^{\prime})\colon(\Sigma^{\triangle},\mathcal{O}(\Sigma^{\triangle}))\to(S,P)$
given by Proposition 3.7 for $\rho$ and $\sigma$: we claim that it is such
that $\alpha(\varphi^{\prime}(w))=\varphi(w)$ for all
$w\in\Sigma^{\triangle}$. We can prove it by induction on $w$:

  * •

$w=\varepsilon$. Then
$\alpha(\varphi^{\prime}(w))=\alpha(1_{S})=1_{R}=\varphi(w)$.

  * •

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

  * •

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

$\displaystyle\alpha(\varphi^{\prime}(w))$
$\displaystyle=\alpha\bigl{(}\varphi^{\prime}(\operatorname{ext}_{a,b}(w^{\prime}))\bigr{)}$
$\displaystyle=\alpha\bigl{(}\psi^{\prime}(\operatorname{ext}_{a,b})(\varphi^{\prime}(w^{\prime}))\bigr{)}$
$\displaystyle=\beta(\psi^{\prime}(\operatorname{ext}_{a,b}))\bigl{(}\alpha(\varphi^{\prime}(w^{\prime}))\bigr{)}$
$\displaystyle\stackrel{{\scriptstyle\text{IH}}}{{=}}\beta(\sigma(\operatorname{ext}_{a,b}))(\varphi(w^{\prime}))$
$\displaystyle=\psi(\operatorname{ext}_{a,b})(\varphi(w^{\prime}))$
$\displaystyle=\varphi(\operatorname{ext}_{a,b}(w^{\prime}))$
$\displaystyle=\varphi(w)\,\,\text{.}$

  * •

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

$\alpha(\varphi^{\prime}(w))=\alpha(\varphi^{\prime}(u))\alpha(\varphi^{\prime}(v))\stackrel{{\scriptstyle\text{IH}}}{{=}}\varphi(u)\varphi(v)=\varphi(w)\,\,\text{.}$

Therefore, $\varphi^{\prime-1}(\alpha^{-1}(F))=L$, which implies that $(S,P)$
recognizes $L$. ∎

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

######  Lemma 3.15.

Let
$(\varphi,\psi)\colon(\Sigma^{\triangle},\mathcal{O}(\Sigma^{\triangle}))\to(R,O)$
be a morphism and let $L\subseteq\Sigma^{\triangle}$ be a language recognized
by $(R,O)$ via $(\varphi,\psi)$. Then
$\bigl{(}\varphi(\Sigma^{\triangle}),{\psi(\mathcal{O}(\Sigma^{\triangle}))|}_{\varphi(\Sigma^{\triangle})}\bigr{)}$
is a sub-$\operatorname{Ext}$-algebra of $(R,O)$ recognizing $L$ via the
surjective morphism $(\varphi,\psi^{\prime})$ where
$\psi^{\prime}(\operatorname{ext}_{u,v})={\psi(\operatorname{ext}_{u,v})|}_{\varphi(\Sigma^{\triangle})}$
for all $\operatorname{ext}_{u,v}\in\mathcal{O}(\Sigma^{\triangle})$.

###### 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^{\triangle})$ is a submonoid of $R$ and
$\psi(\mathcal{O}(\Sigma^{\triangle}))$ is a submonoid of $O$. Observe that
for all $e\in\psi(\mathcal{O}(\Sigma^{\triangle}))$ and
$r\in\varphi(\Sigma^{\triangle})$, we have

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

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

$\mathrm{left}_{r}=\mathrm{left}_{\varphi(w)}={\psi(\mathrm{left}_{w})|}_{\varphi(\Sigma^{\triangle})}={\psi(\operatorname{ext}_{w,\varepsilon})|}_{\varphi(\Sigma^{\triangle})}$

as well as
$\mathrm{right}_{r}={\psi(\operatorname{ext}_{\varepsilon,w})|}_{\varphi(\Sigma^{\triangle})}$.
Thus,
$\bigl{(}\varphi(\Sigma^{\triangle}),{\psi(\mathcal{O}(\Sigma^{\triangle}))|}_{\varphi(\Sigma^{\triangle})}\bigr{)}$
is a sub-$\operatorname{Ext}$-algebra of $(R,O)$.

It is clear that $\varphi$ is a surjective monoid morphism from
$\Sigma^{\triangle}$ to $\varphi(\Sigma^{\triangle})$. Further,

$\displaystyle\psi^{\prime}(\operatorname{ext}_{u,v})\circ\psi^{\prime}(\operatorname{ext}_{u^{\prime},v^{\prime}})$
$\displaystyle={\psi(\operatorname{ext}_{u,v})|}_{\varphi(\Sigma^{\triangle})}\circ{\psi(\operatorname{ext}_{u^{\prime},v^{\prime}})|}_{\varphi(\Sigma^{\triangle})}$
$\displaystyle=\bigl{(}\psi(\operatorname{ext}_{u,v})\circ\psi(\operatorname{ext}_{u^{\prime},v^{\prime}})\bigr{)}\big{|}_{\varphi(\Sigma^{\triangle})}$
$\displaystyle={\psi(\operatorname{ext}_{u,v}\circ\operatorname{ext}_{u^{\prime},v^{\prime}})|}_{\varphi(\Sigma^{\triangle})}$
$\displaystyle=\psi^{\prime}(\operatorname{ext}_{u,v}\circ\operatorname{ext}_{u^{\prime},v^{\prime}})$

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

  * •

$\psi^{\prime}(\operatorname{ext}_{u,v})(\varphi(w))={\psi(\operatorname{ext}_{u,v})|}_{\varphi(\Sigma^{\triangle})}(\varphi(w))=\psi(\operatorname{ext}_{u,v})(\varphi(w))=\varphi(\operatorname{ext}_{u,v}(w))$
for all $\operatorname{ext}_{u,v}\in\mathcal{O}(\Sigma^{\triangle})$ and
$w\in\Sigma^{\triangle}$;

  * •

$\psi^{\prime}(\mathrm{left}_{w})={\psi(\operatorname{ext}_{w,\varepsilon})|}_{\varphi(\Sigma^{\triangle})}=\mathrm{left}_{\varphi(w)}$
and $\psi^{\prime}(\mathrm{right}_{w})=\mathrm{right}_{\varphi(w)}$ for all
$w\in\Sigma^{\triangle}$.

Therefore, $(\varphi,\psi^{\prime})$ is a surjective morphism recognizing $L$.
∎

The following lemma states that a language is recognized by an
$\operatorname{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)\colon(\Sigma^{\triangle},\mathcal{O}(\Sigma^{\triangle}))\to(R,O)$
be a surjective morphism, let $L\subseteq\Sigma^{\triangle}$ and let
$(\varphi_{L},\psi_{L})\colon(\Sigma^{\triangle},\mathcal{O}(\Sigma^{\triangle}))\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)\colon(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)\colon(R,O)\to(R_{L},O_{L})$ such that
$\varphi_{L}=\alpha\circ\varphi$. Then

$\varphi^{-1}\bigl{(}\alpha^{-1}(\varphi(L))\bigr{)}=(\alpha\circ\varphi)^{-1}\bigl{(}\varphi_{L}(L))=\varphi_{L}^{-1}(\varphi_{L}(L))=L\,\,\text{,}$

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^{\prime}\in\Sigma^{\triangle}$ such that
$\varphi(w)=\varphi(w^{\prime})$. Then, given any
$e\in\mathcal{O}(\Sigma^{\triangle})$, we have that

$\varphi(e(w))=\psi(e)(\varphi(w))=\psi(e)(\varphi(w^{\prime}))=\varphi(e(w^{\prime}))\,\,\text{.}$

Therefore, since $\varphi^{-1}(F)=L$, it holds that $w\sim_{L}w^{\prime}$,
that is, $\varphi_{L}(w)=\varphi_{L}(w^{\prime})$.

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

$\varphi(\operatorname{ext}_{u,v}(w))=\psi(\operatorname{ext}_{u,v})(\varphi(w))=\psi(\operatorname{ext}_{u^{\prime},v^{\prime}})(\varphi(w))=\varphi(\operatorname{ext}_{u^{\prime},v^{\prime}}(w))\,\,\text{,}$

that is,
$\operatorname{ext}_{u,v}(w)\sim_{L}\operatorname{ext}_{u^{\prime},v^{\prime}}(w)$.
Hence,
$\psi_{L}(\operatorname{ext}_{u,v})=\psi_{L}(\operatorname{ext}_{u^{\prime},v^{\prime}})$.

We can now define the functions $\alpha\colon R\to R_{L}$ and $\beta\colon
O\to O_{L}$ such that $\alpha(\varphi(w))=\varphi_{L}(w)$ for all
$w\in\Sigma^{\triangle}$ and
$\beta(\psi(\operatorname{ext}_{u,v}))=\psi_{L}(\operatorname{ext}_{u,v})$ for
all $\operatorname{ext}_{u,v}\in\mathcal{O}(\Sigma^{\triangle})$: 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^{\triangle},\mathcal{O}(\Sigma^{\triangle}))$ 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$. ∎

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

######  Proposition 3.17.

An $\operatorname{Ext}$-algebra $(R,O)$ recognizes a language
$L\subseteq\Sigma^{\triangle}$ if, and only if, its syntactic
$\operatorname{Ext}$-algebra $(R_{L},O_{L})$ divides $(R,O)$.

###### Proof.

Let $(R,O)$ be an $\operatorname{Ext}$-algebra and let
$L\subseteq\Sigma^{\triangle}$ be a language. Consider also its syntactic
$\operatorname{Ext}$-algebra $(R_{L},O_{L})$ and its syntactic morphism
$(\varphi_{L},\psi_{L})$.

###### Implication from right to left.

Assume that the syntactic $\operatorname{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)\colon(\Sigma^{\triangle},\mathcal{O}(\Sigma^{\triangle}))\to(R,O)$.
By Lemma 3.15, we have that
$\bigl{(}\varphi(\Sigma^{\triangle}),{\psi(\mathcal{O}(\Sigma^{\triangle}))|}_{\varphi(\Sigma^{\triangle})}\bigr{)}=(R^{\prime},O^{\prime})$
is a sub-$\operatorname{Ext}$-algebra of $(R,O)$ recognizing $L$ via the
surjective morphism $(\varphi,\psi^{\prime})$ where
$\psi^{\prime}(\operatorname{ext}_{u,v})={\psi(\operatorname{ext}_{u,v})|}_{\varphi(\Sigma^{\triangle})}$
for all $\operatorname{ext}_{u,v}\in\mathcal{O}(\Sigma^{\triangle})$. Then, by
Lemma 3.16, there exists a surjective morphism
$(\alpha,\beta)\colon(R^{\prime},O^{\prime})\to(R_{L},O_{L})$ such that
$\varphi_{L}=\alpha\circ\varphi$. Thus, we have that $(R_{L},O_{L})$ divides
$(R,O)$. ∎

We say that an $\operatorname{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 $\operatorname{Ext}$-algebras. Its proof
provides effective translations from DVPAs to $\operatorname{Ext}$-algebras
and vice versa.

######  Theorem 3.18.

A language $L\subseteq\Sigma^{\triangle}$ is a VPL if, and only if, it is
recognized by a finite $\operatorname{Ext}$-algebra.

###### Proof.

Let $L\subseteq\Sigma^{\triangle}$ 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,\bot)$ 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\mathopen{}\left(A\right)\mathclose{}\subseteq\Sigma^{\triangle}$
and additionally we have that

$\widehat{\delta}(q,uv,\sigma)=\widehat{\delta}\bigl{(}\pi_{Q}(\widehat{\delta}(q,u,\sigma)),v,\pi_{\Gamma^{*}}(\widehat{\delta}(q,u,\sigma))\bigr{)}$

and

$\widehat{\delta}(q,w,\alpha\sigma)=\bigl{(}\pi_{Q}(\widehat{\delta}(q,w,\alpha)),\alpha\sigma\bigr{)}$

for all $q\in Q$, $u,v\in\Sigma^{*}$, $\sigma\in\Gamma^{*}$,
$w\in\Sigma^{\triangle}$ 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,\bot)$ such that
$L\mathopen{}\left(A\right)\mathclose{}=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 $\mathrm{left}_{r}$ and $\mathrm{right}_{r}$ for all
$r\in R$, it follows that $(R,O)$ is a finite $\operatorname{Ext}$-algebra. We
now prove that it recognizes $L$. For each $w\in\Sigma^{\triangle}$, define
$f_{w}\in R$ by $f_{w}(q,\alpha)=\pi_{Q}(\widehat{\delta}(q,w,\alpha))$ for
all $q\in Q$ and $\alpha\in\Gamma$. Let us consider the unique morphism
$(\varphi,\psi)\colon(\Sigma^{\triangle},\mathcal{O}(\Sigma^{\triangle}))\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(\operatorname{ext}_{a,b})$ sends any $f\in R$ to $g\in R$ satisfying
that $g(q,\alpha)=\pi_{Q}\bigl{(}\delta(f(p,\beta),b,\beta)\bigr{)}$ 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^{\triangle}$, 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^{\prime}b$ for some $a\in\Sigma_{\text{call}}$,
$b\in\Sigma_{\text{ret}}$ and $w^{\prime}\in\Sigma^{\triangle}$. Then

$\varphi(w)=\varphi(\operatorname{ext}_{a,b}(w^{\prime}))=\psi(\operatorname{ext}_{a,b})(\varphi(w^{\prime}))\stackrel{{\scriptstyle\text{IH}}}{{=}}\psi(\operatorname{ext}_{a,b})(f_{w^{\prime}})\,\,\text{.}$

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
$\widehat{\delta}$ extends $\delta$,

$\displaystyle g(q,\alpha)$
$\displaystyle=\pi_{Q}\bigl{(}\delta(f_{w^{\prime}}(p,\beta),b,\beta)\bigr{)}$
$\displaystyle=\pi_{Q}\Bigl{(}\delta\bigl{(}\pi_{Q}(\widehat{\delta}(p,w^{\prime},\beta)),b,\beta\bigr{)}\Bigr{)}$
$\displaystyle=\pi_{Q}\Bigl{(}\widehat{\delta}\bigl{(}\pi_{Q}(\widehat{\delta}(p,w^{\prime},\beta)),b,\beta\bigr{)}\Bigr{)}$
$\displaystyle=\pi_{Q}\Bigl{(}\widehat{\delta}\bigl{(}\pi_{Q}(\widehat{\delta}(q,aw^{\prime},\alpha)),b,\pi_{\Gamma^{*}}(\widehat{\delta}(q,aw^{\prime},\alpha))\bigr{)}\Bigr{)}$
$\displaystyle=\pi_{Q}(\widehat{\delta}(q,aw^{\prime}b,\alpha))$
$\displaystyle=f_{aw^{\prime}b}(q,\alpha)$
$\displaystyle=f_{w}(q,\alpha)\,\,\text{.}$

Thus $\varphi(w)=f_{w}$.

  * •

$w=uv$ for some $u,v\in\Sigma^{\triangle}\setminus\\{\varepsilon\\}$. Then
$\varphi(w)=\varphi(u)*\varphi(v)\stackrel{{\scriptstyle\text{IH}}}{{=}}f_{u}*f_{v}$.
But

$\displaystyle f_{u}*f_{v}(q,\alpha)$
$\displaystyle=f_{v}(f_{u}(q,\alpha),\alpha)$
$\displaystyle=f_{v}\bigl{(}\pi_{Q}(\widehat{\delta}(q,u,\alpha)),\alpha\bigr{)}$
$\displaystyle=\pi_{Q}\Bigl{(}\widehat{\delta}\bigl{(}\pi_{Q}(\widehat{\delta}(q,u,\alpha)),v,\alpha\bigr{)}\Bigr{)}$
$\displaystyle=\pi_{Q}\Bigl{(}\widehat{\delta}\bigl{(}\pi_{Q}(\widehat{\delta}(q,u,\alpha)),v,\pi_{\Gamma^{*}}(\widehat{\delta}(q,u,\alpha))\bigr{)}\Bigr{)}$
$\displaystyle=\pi_{Q}(\widehat{\delta}(q,uv,\alpha))$
$\displaystyle=f_{uv}(q,\alpha)$

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

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

$\displaystyle\varphi^{-1}(P)$ $\displaystyle=\\{w\in\Sigma^{\triangle}\mid
f_{w}(q_{0},\bot)\in F\\}$
$\displaystyle=\\{w\in\Sigma^{\triangle}\mid\pi_{Q}(\widehat{\delta}(q_{0},w,\bot))\in
F\\}$
$\displaystyle=\\{w\in\Sigma^{\triangle}\mid\widehat{\delta}(q_{0},w,\bot)\in
F\times\\{\bot\\}\\}$ $\displaystyle=L\mathopen{}\left(A\right)\mathclose{}$
$\displaystyle=L\,\,\text{.}$

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

###### Implication from right to left.

Assume there exists a finite $\operatorname{Ext}$-algebra $(R,O)$ that
recognizes $L$. This means that there exists a morphism
$(\varphi,\psi)\colon(\Sigma^{\triangle},\mathcal{O}(\Sigma^{\triangle}))\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,\bot),$

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

$\delta(r,a,\alpha)=\begin{cases}(1,(r,a)\alpha)&\text{if
$a\in\Sigma_{\text{call}}$}\\\
(s\psi(\operatorname{ext}_{b,a})(r),\varepsilon)&\text{if
$a\in\Sigma_{\text{ret}}$ and $\alpha=(s,b)\in
R\times\Sigma_{\text{call}}$}\\\ (r,\varepsilon)&\text{if
$a\in\Sigma_{\text{ret}}$ and $\alpha=\bot$}\\\ (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
$\widehat{\delta}(r,w,\sigma)=(r\varphi(w),\sigma)$ for all $r\in R$,
$w\in\Sigma^{\triangle}$ and $\sigma\in\Gamma^{*}\bot$ by induction on $w$.

  * •

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

  * •

$w=c$ for some $c\in\Sigma_{\text{int}}$. Then
$\widehat{\delta}(r,w,\sigma)=(r\varphi(c),\sigma)=(r\varphi(w),\sigma)$.

  * •

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

$\displaystyle\widehat{\delta}(r,w,\sigma)$
$\displaystyle=\widehat{\delta}(1,w^{\prime}b,(r,a)\sigma)$
$\displaystyle=\widehat{\delta}\bigl{(}\pi_{Q}(1,w^{\prime},(r,a)\sigma),b,\pi_{\Gamma^{*}}(1,w^{\prime},(r,a)\sigma)\bigr{)}$
$\displaystyle\stackrel{{\scriptstyle\text{IH}}}{{=}}\widehat{\delta}(\varphi(w^{\prime}),b,(r,a)\sigma)$
$\displaystyle=\bigl{(}r\psi(\operatorname{ext}_{a,b})(\varphi(w^{\prime})),\sigma\bigr{)}$
$\displaystyle=(r\varphi(w),\sigma)\,\,\text{.}$

  * •

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

$\displaystyle\widehat{\delta}(r,w,\sigma)$
$\displaystyle=\widehat{\delta}\bigl{(}\pi_{Q}(\widehat{\delta}(r,u,\sigma)),v,\pi_{\Gamma^{*}}(\widehat{\delta}(r,u,\sigma))\bigr{)}$
$\displaystyle\stackrel{{\scriptstyle\text{IH}}}{{=}}\widehat{\delta}(r\varphi(u),v,\sigma)$
$\displaystyle\stackrel{{\scriptstyle\text{IH}}}{{=}}(r\varphi(u)\varphi(v),\sigma)$
$\displaystyle=(r\varphi(w),\sigma)\,\,\text{.}$

Hence,

$\displaystyle L\mathopen{}\left(A\right)\mathclose{}$
$\displaystyle=\\{w\in\Sigma^{\triangle}\mid\widehat{\delta}(1,w,\bot)\in
F\times\\{\bot\\}\\}$
$\displaystyle=\\{w\in\Sigma^{\triangle}\mid\pi_{Q}(\widehat{\delta}(1,w,\bot))\in
F\\}$ $\displaystyle=\\{w\in\Sigma^{\triangle}\mid\varphi(w)\in F\\}$
$\displaystyle=\varphi^{-1}(F)=L\,\,\text{.}$

Therefore, $L$ is a VPL. ∎

##  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 $\operatorname{Ext}$-algebra $(R,O)$ and consider a morphism
$(\varphi,\psi)\colon(\Sigma^{\triangle},\mathcal{O}(\Sigma^{\triangle}))\to(R,O)$.
Suitably adjusting the pumping lemma for context-free language we introduce a
pumping lemma for $\operatorname{Ext}$-algebra morphisms in Section 4.1. In
Section 4.2 we extend the notions of weak length-synchronicity and length-
synchronicity to $\operatorname{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
$\operatorname{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 $\operatorname{Ext}$-algebra morphisms. It states that if
$uv\in\Sigma^{\triangle}$ 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},\ldots$ (resp.
$v_{1},v_{2},\ldots)$ such that $u_{1}v,u_{2}v,\ldots\in\Sigma^{\triangle}$
(resp. $uv_{1},uv_{2},\ldots\in\Sigma^{\triangle}$) and the morphism $\psi$
sends $\operatorname{ext}_{u,v}$ to the same element in $O$ as
$\operatorname{ext}_{u_{i},v}$ (resp. as $\operatorname{ext}_{u,v_{i}}$).

######  Lemma 4.1 (Pumping Lemma).

There exists $n\in\mathbb{N}_{>0}$ such that for all
$\operatorname{ext}_{u,v}\in\mathcal{O}(\Sigma^{\triangle})$ we have:

  * •

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

  * •

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

###### Proof.

For each $r\in 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 R}n_{r}$. Let
$\operatorname{ext}_{u,v}\in\mathcal{O}(\Sigma^{\triangle})$ be such that
there exists a factor $w\in\Sigma^{\triangle}$ of $u$ satisfying
$\mathopen{}\left|w\right|\mathclose{}\geq n$. Let

$\operatorname{ext}_{u,v}\quad=\quad\operatorname{ext}_{x_{1},y_{1}}\circ\operatorname{ext}_{a_{1},b_{1}}\circ\quad\cdots\quad\circ\operatorname{ext}_{x_{h-1},y_{h-1}}\circ\operatorname{ext}_{a_{h-1},b_{h-1}}\circ\operatorname{ext}_{x_{h},y_{h}}$

be the stair factorization of $\operatorname{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
$\mathopen{}\left|x_{j}\right|\mathclose{}\geq n$, so that if we set
$u^{\prime}=x_{1}a_{1}\cdots x_{j-1}a_{j-1}$, $v^{\prime}=b_{j-1}y_{j-1}\cdots
b_{1}y_{1}$, $u^{\prime\prime}=a_{j}x_{j+1}\cdots a_{h-1}x_{h}$ and
$v^{\prime\prime}=y_{h}b_{h-1}\cdots y_{j+1}b_{j}y_{j}$, we have
$u^{\prime}v^{\prime},u^{\prime\prime}v^{\prime\prime}\in\Sigma^{\triangle}$
and
$\operatorname{ext}_{u,v}=\operatorname{ext}_{u^{\prime},v^{\prime}}\circ\operatorname{ext}_{x_{j},\varepsilon}\circ\operatorname{ext}_{u^{\prime\prime},v^{\prime\prime}}$.
By the pumping lemma for context-free languages we have
$x_{j}=x^{\prime}xzyy^{\prime}$ with
$x^{\prime},x,z,y,y^{\prime}\in\Sigma^{*}$ such that
$\mathopen{}\left|xy\right|\mathclose{}\geq 1$,
$\mathopen{}\left|xzy\right|\mathclose{}\leq n$ and for all $i\in\mathbb{N}$,
$x^{\prime}x^{i}zy^{i}y^{\prime}\in\Sigma^{\triangle}$ and
$\varphi(x_{j})=\varphi(x^{\prime}x^{i}zy^{i}y^{\prime})$. This implies that
if we set $s=u^{\prime}x^{\prime}$ and $t=y^{\prime}u^{\prime\prime}$, then
for all $i\in\mathbb{N}$, we have
$sx^{i}zy^{i}tv=\operatorname{ext}_{u^{\prime},v^{\prime}}\circ\operatorname{ext}_{x^{\prime}x^{i}zy^{i}y^{\prime},\varepsilon}\circ\operatorname{ext}_{u^{\prime\prime},v^{\prime\prime}}(\varepsilon)\in\Sigma^{\triangle}$
and

$\displaystyle\psi(\operatorname{ext}_{u,v})$
$\displaystyle=\psi(\operatorname{ext}_{u^{\prime},v^{\prime}})\circ\mathrm{left}_{\varphi(x_{j})}\circ\psi(\operatorname{ext}_{u^{\prime\prime},v^{\prime\prime}})$
$\displaystyle=\psi(\operatorname{ext}_{u^{\prime},v^{\prime}})\circ\mathrm{left}_{\varphi(x^{\prime}x^{i}zy^{i}y^{\prime})}\circ\psi(\operatorname{ext}_{u^{\prime\prime},v^{\prime\prime}})$
$\displaystyle=\psi(\operatorname{ext}_{u^{\prime},v^{\prime}})\circ\psi(\operatorname{ext}_{x^{\prime}x^{i}zy^{i}y^{\prime},\varepsilon})\circ\psi(\operatorname{ext}_{u^{\prime\prime},v^{\prime\prime}})$
$\displaystyle=\psi(\operatorname{ext}_{sx^{i}zy^{i}t,v})\,\,\text{.}$

We handle the case where for
$\operatorname{ext}_{u,v}\in\mathcal{O}(\Sigma^{\triangle})$ there exists a
factor $w\in\Sigma^{\triangle}$ of $v$ such that
$\mathopen{}\left|w\right|\mathclose{}\geq n$ symmetrically. ∎

###  4.2 Weak length-synchronicity and length-synchronicity

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

For $F\subseteq R$ we say that an element $r\in 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 R$. Although we will mainly study
$F$-reachable elements over finite $\operatorname{Ext}$-algebras we remark
that the notion of $F$-reachability is defined over any
$\operatorname{Ext}$-algebra, in particular over
$(\Sigma^{\triangle},\mathcal{O}(\Sigma^{\triangle}))$. Fix any VPL $L$, its
syntactic $\operatorname{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}(\operatorname{ext}_{u,v})=\psi_{L}(\operatorname{ext}_{u^{\prime},v})=e$
and $\Delta(u),\Delta(u^{\prime})>0$ for some
$\operatorname{ext}_{u,v},\operatorname{ext}_{u^{\prime},v}\in\mathcal{O}(\Sigma^{\triangle})$
with $|u|\not=|u^{\prime}|$, then $L$ is $\mathsf{TC}^{0}$-hard. We remark
that we must have $\Delta(u)=\Delta(u^{\prime})$. Exploiting the fact that
$\mathopen{}\left|u\right|\mathclose{}\not=\mathopen{}\left|u^{\prime}\right|\mathclose{}$
we give a constant-depth reduction from the $\mathsf{TC}^{0}$-complete
language $\mathrm{EQUALITY}$ to $L$.

Since $\psi_{L}(\operatorname{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(\mathopen{}\left|u\right|\mathclose{}+\mathopen{}\left|u^{\prime}\right|\mathclose{})}y$,
where $h\colon\\{0,1\\}^{*}\to\Sigma^{*}$ is the length-multiplying morphism
satisfiying $h(0)=u^{\mathopen{}\left|u^{\prime}\right|\mathclose{}}$ and
$h(1)=u^{\prime\mathopen{}\left|u\right|\mathclose{}}$: one can prove that
$w\in\mathrm{EQUALITY}$ if, and only if,
$h(w)v^{n\cdot(\mathopen{}\left|u\right|\mathclose{}+\mathopen{}\left|u^{\prime}\right|\mathclose{})}\in\Sigma^{\triangle}$
if, and only if,
$xh(w)zv^{n\cdot(\mathopen{}\left|u\right|\mathclose{}+\mathopen{}\left|u^{\prime}\right|\mathclose{})}y\in
L$.

Dually, one can show that $L$ is $\mathsf{TC}^{0}$-hard in case
$\psi_{L}(\operatorname{ext}_{u,v})=\psi_{L}(\operatorname{ext}_{u,v^{\prime}})=e$
and $\Delta(u)>0$ for some
$\operatorname{ext}_{u,v},\operatorname{ext}_{u,v^{\prime}}\in\mathcal{O}(\Sigma^{\triangle})$
with
$\mathopen{}\left|v\right|\mathclose{}\not=\mathopen{}\left|v^{\prime}\right|\mathclose{}$.

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\mathsf{Con}(\Sigma)$ is
defined to be weakly length-synchronous if $u=u^{\prime}$ implies
$\mathopen{}\left|v\right|\mathclose{}=\mathopen{}\left|v^{\prime}\right|\mathclose{}$
and $v=v^{\prime}$ implies
$\mathopen{}\left|u\right|\mathclose{}=\mathopen{}\left|u^{\prime}\right|\mathclose{}$
for all $(u,v),(u^{\prime},v^{\prime})\in\mathcal{R}$ satisfying
$\Delta(u),\Delta(u^{\prime})>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\mathsf{Con}(\Sigma)\mid\psi(\operatorname{ext}_{u,v})=e\\}\quad\text{
and }\quad\mathcal{U}_{e}=\\{(u,v)\in\mathsf{Con}(\Sigma)\mid
e\circ\psi(\operatorname{ext}_{u,v})=e\\}$

######  Definition 4.3 (Weak Length-Synchronicity).

The morphism
$(\varphi,\psi)\colon(\Sigma^{\triangle},\mathcal{O}(\Sigma^{\triangle}))\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^{\triangle}$ 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^{\prime},v)\in\mathsf{Con}(\Sigma)$ be such that
$\Delta(u),\Delta(u^{\prime})>0$ and
$\psi(\operatorname{ext}_{u,v}),\psi(\operatorname{ext}_{u^{\prime},v})\in P$.
Set $e=\psi(\operatorname{ext}_{u,v})$ and
$f=\psi(\operatorname{ext}_{u^{\prime},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(\operatorname{ext}_{(u^{2\cdot\omega}u^{\prime\omega})^{\omega},v^{3\cdot\omega^{2}}})=(e^{\omega}f^{\omega})^{\omega}=\psi(\operatorname{ext}_{(u^{\omega}u^{\prime
2\cdot\omega})^{\omega},v^{3\cdot\omega^{2}}})$

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

$\begin{array}[]{lrcl}&\quad{\omega~\cdot(2\cdot\omega\cdot~|u|+\omega\cdot|u^{\prime}|)}&=&\omega\cdot(\omega\cdot|u|+2\cdot\omega\cdot|u^{\prime}|)\\\
\Longleftrightarrow&{2\cdot|u|+|u^{\prime}|}&=&{|u|+2\cdot|u^{\prime}|}\\\
\Longleftrightarrow&|u|&=&|u^{\prime}|\,\,\text{.}\end{array}$

In the same way, one can prove that for all
$(u,v),(u,v^{\prime})\in\mathsf{Con}(\Sigma)$ such that $\Delta(u)>0$ and
$\psi(\operatorname{ext}_{u,v}),\psi(\operatorname{ext}_{u,v^{\prime}})\in P$,
we have
$\mathopen{}\left|v\right|\mathclose{}=\mathopen{}\left|v^{\prime}\right|\mathclose{}$.

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

Instead of considering those pairs $(u,v)$ such that
$\operatorname{ext}_{u,v}$ is being mapped to an $F$-reachable idempotent, the
following characterization of weak length-synchronicity consider pairs $(u,v)$
such that $\operatorname{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-synchrononous.

###### Proof.

Let $F\subseteq R$.

If $\mathcal{U}_{e}=\\{(u,v)\in\mathsf{Con}(\Sigma)\mid
e\circ\psi(\operatorname{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\mathsf{Con}(\Sigma)\mid\psi(\operatorname{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. ∎

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 $\operatorname{ext}_{u,v}$ be such that
$\Delta(u)>0$ and $e\circ\psi(\operatorname{ext}_{u,v})=e$. If
$(\varphi,\psi)$ is $F$-weakly-length-synchronous, then the stair
factorization

$\operatorname{ext}_{u,v}=\operatorname{ext}_{x_{1},y_{1}}\circ\operatorname{ext}_{a_{1},b_{1}}\circ\dots\circ\operatorname{ext}_{x_{h-1},y_{h-1}}\circ\operatorname{ext}_{a_{h-1},b_{h-1}}\circ\operatorname{ext}_{x_{h},y_{h}}$

satisfies $|x_{i}|,|y_{i}|\leq 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 $\operatorname{Ext}$-algebra
morphisms and VPLs, respectively.

######  Definition 4.7 (Length-Synchronicity).

The morphism
$(\varphi,\psi)\colon(\Sigma^{\triangle},\mathcal{O}(\Sigma^{\triangle}))\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^{\triangle}$ 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\rightarrow aSb_{1}\mid
acSb_{2}\mid\varepsilon)$. Recall that the monoid $O_{\mathcal{L}_{1,2}}$ of
the syntactic $\operatorname{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))=\\{\operatorname{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
$\operatorname{ext}_{u,v}$ with $\Delta(u)>0$ is the idempotent $(a,b_{1})$.
However, both $\operatorname{ext}_{a,b_{1}}$ and
$\operatorname{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\not=2=|ac|/|b_{2}|$, we have that $\mathcal{L}_{1,2}$ is not
length-synchronous. On the other hand, note that if any
$\operatorname{ext}_{u,v}$ and $\operatorname{ext}_{u^{\prime},v}$ (resp.
$\operatorname{ext}_{u,v}$ and $\operatorname{ext}_{u,v^{\prime}}$) are sent
to $(a,b_{1})$ then $u=u^{\prime}$ and thus $|u|=|u^{\prime}|$ (resp.
$v=v^{\prime}$ and thus $|v|=|v^{\prime}|$). 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^{\prime},v^{\prime})\in\mathsf{Con}(\Sigma)$ be such that
$\Delta(u),\Delta(u^{\prime})>0$ and
$\psi(\operatorname{ext}_{u,v}),\psi(\operatorname{ext}_{u^{\prime},v^{\prime}})\in
P$. Set $e=\psi(\operatorname{ext}_{u,v})$ and
$f=\psi(\operatorname{ext}_{u^{\prime},v^{\prime}})$. 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(\operatorname{ext}_{(u^{2\cdot\omega}u^{\prime\omega})^{\omega},(v^{\prime\omega}v^{2\cdot\omega})^{\omega}})=(e^{\omega}f^{\omega})^{\omega}=\psi(\operatorname{ext}_{(u^{\omega}u^{\prime
2\cdot\omega})^{\omega},(v^{\prime 2\cdot\omega}v^{\omega})^{\omega}})$

so since
$\Delta((u^{2\cdot\omega}u^{\prime\omega})^{\omega}),\Delta((u^{\omega}u^{\prime
2\cdot\omega})^{\omega})>0$, setting
$(x,y)=((u^{2\cdot\omega}u^{\prime\omega})^{\omega},(v^{\prime\omega}v^{2\cdot\omega})^{\omega})$
and $(x^{\prime},y^{\prime})=((u^{\omega}u^{\prime
2\cdot\omega})^{\omega},(v^{\prime 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}$)

$\displaystyle\frac{|x|}{|y|}=\frac{|x^{\prime}|}{|y^{\prime}|}$
$\displaystyle\quad\Longrightarrow\quad$
$\displaystyle\frac{|x|}{|y|}=\frac{|x^{\prime}|}{|y^{\prime}|}=\frac{|x|+|x^{\prime}|}{|y|+|y^{\prime}|}=\frac{\omega^{2}\cdot(|u|+|u^{\prime}|)}{\omega^{2}\cdot(|v|+|v^{\prime}|)}$
$\displaystyle\quad\Longrightarrow\quad$
$\displaystyle\frac{|x|-\omega^{2}\cdot(|u|+|u^{\prime}|)}{|y|-\omega^{2}\cdot(|v|+|v^{\prime}|)}=\frac{|x^{\prime}|-\omega^{2}\cdot(|u|+|u^{\prime}|)}{|y^{\prime}|-\omega^{2}\cdot(|v|+|v^{\prime}|)}$
$\displaystyle\quad\Longrightarrow\quad$
$\displaystyle\frac{|u|}{|v|}=\frac{\omega^{2}\cdot|u|}{\omega^{2}\cdot|v|}\stackrel{{\scriptstyle(\ref{E
square})}}{{=}}\frac{\omega^{2}\cdot|u^{\prime}|}{\omega^{2}\cdot|v^{\prime}|}=\frac{|u^{\prime}|}{|v^{\prime}|}\,\,\text{.}$

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

The two following propositions characterize length-synchronicity of
$\operatorname{Ext}$-algebra morphisms, which will be of particular importance
when approximating the matching relation of a length-synchronous VPL in terms
of $\mathsf{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 $\mathsf{FO}[\mathsf{+}]$
and thus in $\mathsf{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\mathsf{Con}(\Sigma)\mid
e\circ\psi(\operatorname{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\mathsf{Con}(\Sigma)\mid\psi(\operatorname{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. ∎

######  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. 1.

The set of contexts $\mathcal{U}_{e}$ is length-synchronous.

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

    1. (a)

$\frac{\mathopen{}\left|u\right|\mathclose{}}{\mathopen{}\left|v\right|\mathclose{}}=\alpha$.

    2. (b)

For all $u^{\prime},v^{\prime}\in\Sigma^{+}$ with $u^{\prime}$ prefix of $u$
and $v^{\prime}$ suffix of $v$ such that
$\frac{\mathopen{}\left|u^{\prime}\right|\mathclose{}}{\mathopen{}\left|v^{\prime}\right|\mathclose{}}=\alpha$,
we have that
$-\Delta(v^{\prime})-\beta\leq\Delta(u^{\prime})\leq-\Delta(v^{\prime})+\beta$.

    3. (c)

For all factors $u^{\prime}\in\Sigma^{*}$ of $u$ such that
$\mathopen{}\left|u^{\prime}\right|\mathclose{}=\gamma$, we have
$\Delta(u^{\prime})\geq 1$.

    4. (d)

For all factors $v^{\prime}\in\Sigma^{*}$ of $v$ such that
$\mathopen{}\left|v^{\prime}\right|\mathclose{}=\gamma$, we have
$\Delta(v^{\prime})\leq-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

$\operatorname{ext}_{u,v}=\operatorname{ext}_{x_{1},y_{1}}\circ\operatorname{ext}_{a_{1},b_{1}}\circ\dots\circ\operatorname{ext}_{x_{h-1},y_{h-1}}\circ\operatorname{ext}_{a_{h-1},b_{h-1}}\circ\operatorname{ext}_{x_{h},y_{h}}$

be the stair factorization of $\operatorname{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}|\leq n$ by Lemma 4.6. Let
$u^{\prime}\in\Sigma^{*}$ be a prefix of $u$ and $v^{\prime}$ be a suffix of
$v$ such that $\frac{|u^{\prime}|}{|v^{\prime}|}=\alpha$. If
$(u^{\prime},v^{\prime})=(u,v)$ we are done since then
$\Delta(u^{\prime})=-\Delta(v^{\prime})$. Thus, it remains to consider the
case when $u^{\prime}$ is a strict prefix of $u$ and $v^{\prime}$ is a strict
suffix of $v$: indeed, due to
$\frac{|u|}{|v|}=\frac{|u^{\prime}|}{|v^{\prime}|}=\alpha$ we have that
$u^{\prime}$ is a strict prefix of $u$ if, and only if, $v^{\prime}$ 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^{\prime}$ and $y_{j}b_{j-1}\cdots y_{1}$ is a suffix of $v^{\prime}$. If
$j=1$ we are done, since then
$\min\\{\mathopen{}\left|u^{\prime}\right|\mathclose{},\mathopen{}\left|v^{\prime}\right|\mathclose{}\\}\leq
n$, so that
$|\Delta(u^{\prime})+\Delta(v^{\prime})|\leq\mathopen{}\left|u^{\prime}\right|\mathclose{}+\mathopen{}\left|v^{\prime}\right|\mathclose{}\leq
n+n\cdot\max(A,B)\leq\beta$. So assume now that $j>1$, which implies that
$\Delta(u^{\prime\prime})>0$. Note that $j<h$ since
$(u^{\prime},v^{\prime})\not=(u,v)$. Hence there exist unique words
$s,t\in\Sigma^{*}$ such that $u^{\prime}=u^{\prime\prime}s$ and
$v^{\prime}=tv^{\prime\prime}$, where $u^{\prime\prime}=x_{1}\cdots
a_{j-1}x_{j}$ and $v^{\prime\prime}=y_{j}b_{j-1}\cdots y_{1}$. By maximality
of $j$ we have $\min\\{|s|,|t|\\}\leq n$. Setting
$f=\psi(\operatorname{ext}_{u^{\prime\prime},v^{\prime\prime}})$ and
$g=\psi(\operatorname{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(\operatorname{ext}_{u,v})=f\circ g$. We claim
that there exist
$\operatorname{ext}_{x_{g},y_{g}}\in\mathcal{O}(\Sigma^{\triangle})$ such that
$\psi(\operatorname{ext}_{x_{g},y_{g}})=g$ and
$|x_{g}|,|y_{g}|\leq|O|\cdot(n+1)$: indeed, by the pigeonhole principle and
Lemma 4.6 (as $e\circ f\circ g=e$ and $\Delta(u^{\prime\prime})>0$), any
$\operatorname{ext}_{x,y}\in\mathcal{O}(\Sigma^{\triangle})$ such that
$\psi(\operatorname{ext}_{x,y})=g$ and $\max(|x|,|y|)>|O|\cdot(n+1)$ must have
a stair factorization according to Lemma 3.6 with an $h>\left|O\right|$ and
can thus be factorized as
$\operatorname{ext}_{x,y}=\operatorname{ext}_{x^{\prime},y^{\prime}}\circ\operatorname{ext}_{x^{\prime\prime},y^{\prime\prime}}\circ\operatorname{ext}_{x^{\prime\prime\prime},y^{\prime\prime\prime}}$
such that
$\psi(\operatorname{ext}_{x,y})=\psi(\operatorname{ext}_{x^{\prime},y^{\prime}})\circ\psi(\operatorname{ext}_{x^{\prime\prime\prime},y^{\prime\prime\prime}})$,
where moreover
$(x^{\prime\prime},y^{\prime\prime})\in\Sigma^{+}\times\Sigma^{+}$. Thus,
$\psi(\operatorname{ext}_{u^{\prime\prime}x_{g},y_{g}v^{\prime\prime}})=\psi(\operatorname{ext}_{u,v})$
and therefore
$(u^{\prime\prime}x_{g},y_{g}v^{\prime\prime})\in\mathcal{U}_{e}$ with
$\Delta(u^{\prime\prime}x_{g})>0$. It follows
$\alpha=\frac{|u^{\prime\prime}x_{g}|}{|y_{g}v^{\prime\prime}|}=\frac{|u^{\prime}|-|s|+|x_{g}|}{|y_{g}|+|v^{\prime}|-|t|}$,
or equivalently, using $\frac{|u^{\prime}|}{|v^{\prime}|}=\alpha$:

$\displaystyle|s|$ $\displaystyle=$
$\displaystyle|u^{\prime}|+|x_{g}|+\alpha(|t|-|y_{g}|-|v^{\prime}|)=|x_{g}|+\alpha(|t|-|y_{g}|)$
(2) $\displaystyle|t|$ $\displaystyle=$
$\displaystyle\frac{|s|-|u^{\prime}|-|x_{g}|}{\alpha}+|y_{g}|+|v^{\prime}|=\frac{|s|-|x_{g}|}{\alpha}+|y_{g}|\,\,\text{.}$
(3)

Finally, we obtain

$\displaystyle|\Delta(u^{\prime})+\Delta(v^{\prime})|$ $\displaystyle=$
$\displaystyle|\Delta(u^{\prime\prime}s)+\Delta(tv^{\prime\prime})|$
$\displaystyle\stackrel{{\scriptstyle\Delta(u^{\prime\prime})=-\Delta(v^{\prime\prime})}}{{=}}$
$\displaystyle|\Delta(s)+\Delta(t)|$ $\displaystyle\leq$
$\displaystyle~|s|+|t|$ $\displaystyle=$
$\displaystyle\min(|s|,|t|)+\max(|s|,|t|)$ $\displaystyle\leq$ $\displaystyle
n+\max(|s|,|t|)$ $\displaystyle\stackrel{{\scriptstyle(\ref{eq s}),(\ref{eq
t})}}{{\leq}}$ $\displaystyle
n+\max\left(|x_{g}|+\alpha(n-|y_{g}|),\frac{n-|x_{g}|}{\alpha}+|y_{g}|\right)$
$\displaystyle\leq$ $\displaystyle n+|O|\cdot(n+1)+n\cdot\max(A,B)$
$\displaystyle\leq$ $\displaystyle(n+1)\cdot(|O|+\max(A,B)+1)$
$\displaystyle=$ $\displaystyle\beta\,\,\text{.}$

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

$\operatorname{ext}_{u,v}=\operatorname{ext}_{x_{1},y_{1}}\circ\operatorname{ext}_{a_{1},b_{1}}\circ\dots\circ\operatorname{ext}_{x_{h-1},y_{h-1}}\circ\operatorname{ext}_{a_{h-1},b_{h-1}}\circ\operatorname{ext}_{x_{h},y_{h}}$

be the stair factorization of $\operatorname{ext}_{u,v}$ according to Lemma
3.6. Let $u^{\prime}$ with $|u^{\prime}|\geq\gamma$ be a factor of $u$ and
hence of $x_{1}a_{1}x_{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^{\prime}$ such that $\Delta(w)=\min\\{\Delta(x)\mid\text{$x$ is a prefix of
$u^{\prime}$}\\}$. Since $|x_{1}|,|y_{1}|,\dots,|x_{h}|,|y_{h}|\leq n$, it
immediately follows $\Delta(w)\geq-\frac{n}{2}$ and $|w|\leq n$. By the same
reason, every prefix of the form $ws$ of $u^{\prime}$ satisfies
$\Delta(ws)\geq\Delta(w)+\frac{|s|}{n+1}$. Thus we have

$\Delta(u^{\prime})\geq\Delta(w)+\frac{|u^{\prime}|-|w|}{n+1}\geq-\frac{n}{2}+\frac{((\lceil\frac{n}{2}\rceil+1)\cdot(n+1)+n)-n}{n+1}\geq
1\,\,\text{.}\qed$

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\mathsf{Con}(\Sigma)\mid
S\Rightarrow_{G}^{*}uSv\\}$. Then the following equivalences hold:

  1. 1.

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

  2. 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^{\triangle})\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\mathsf{Con}(\Sigma)\mid\psi_{L}(\operatorname{ext}_{u,v})=e\\}$.

Let $F=\\{e\in
O_{L}\mid\exists\operatorname{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}\leq\frac{|x|}{|y|}\leq C$ for all
$(x,y)\in\mathcal{R}(G)\setminus\\{(\varepsilon,\varepsilon)\\}$: indeed, one
can take $C=\frac{A}{B}$ where
$A=\max\bigl{\\{}\max\\{\mathopen{}\left|u\right|\mathclose{},\mathopen{}\left|v\right|\mathclose{}\\}\mathrel{\big{|}}T\rightarrow_{G}uT^{\prime}v\bigr{\\}}$
and
$B=\min\bigl{\\{}\min\\{\mathopen{}\left|u\right|\mathclose{},\mathopen{}\left|v\right|\mathclose{}\\}\mathrel{\big{|}}T\rightarrow_{G}uT^{\prime}v\bigr{\\}}$
since whenever $T\Rightarrow_{G}^{*}xT^{\prime}y$ thanks to a derivation
comprising $k\in\mathbb{N}_{>0}$ steps, we have

$\frac{1}{C}=\frac{k\cdot B}{k\cdot
A}\leq\frac{\mathopen{}\left|x\right|\mathclose{}}{\mathopen{}\left|y\right|\mathclose{}}\leq\frac{k\cdot
A}{k\cdot B}=C\,\,\text{.}$

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
$\operatorname{ext}_{u^{\prime},v^{\prime}}\in\psi_{L}^{-1}(g),\operatorname{ext}_{u,v}\in\psi_{L}^{-1}(e)$,
and $w\in\varphi_{L}^{-1}(r)$. Observe that we must have
$(u,v)\not=(\varepsilon,\varepsilon)$ since
$\psi_{L}(\operatorname{ext}_{\varepsilon,\varepsilon})$ is the identity in
$O_{L}$. Since $e$ is an idempotent we have that
$u^{\prime}u^{n}wv^{n}v^{\prime}\in L$ for all $n\geq 1$. Fix a sufficiently
large $N\geq 1$ such that
$\frac{|u^{\prime}|+|u|}{(N-1)|u|+|w|+N|v|+|v^{\prime}|}\leq\frac{1}{C}$ and
$\frac{|u^{\prime}|+N|u|+|w|+(N-1)|v|}{|v|+|v^{\prime}|}\geq C$, which exists
due to $(u,v)\not=(\varepsilon,\varepsilon)$. Since
$u^{\prime}u^{N}wv^{N}v^{\prime}\in L$ there exists
$(x,y)\in\mathcal{R}(G)\setminus\\{(\varepsilon,\varepsilon)\\}$ such that
$xy=u^{\prime}u^{N}wv^{N}v^{\prime}$, $S\Rightarrow_{G}^{*}xSy$,
$|x|\geq|u^{\prime}u|$, and $|y|\geq|vv^{\prime}|$. Let
$(x^{\prime},y^{\prime})\in\Sigma^{*}\times\Sigma^{*}$ be such that
$(x,y)=(u^{\prime}ux^{\prime},y^{\prime}vv^{\prime})$. As
$(u^{\prime},v^{\prime}),(u,v),(x,y)\in\mathsf{Con}(\Sigma)$,
$x^{\prime}\in(\Sigma\setminus\Sigma_{\text{ret}})^{*}$, and
$y^{\prime}\in(\Sigma\setminus\Sigma_{\text{call}})^{*}$, we can conclude
$(x^{\prime},y^{\prime})\in\mathsf{Con}(\Sigma)$. That is,
$(x,y)=(u^{\prime},v^{\prime})\circ(u,v)\circ(x^{\prime},y^{\prime})\in\mathcal{R}(G)$.
Hence,

$g\circ
e\circ\psi_{L}(\operatorname{ext}_{x^{\prime},y^{\prime}})=\psi_{L}(\operatorname{ext}_{u^{\prime}ux^{\prime},y^{\prime}vv^{\prime}})=\psi_{L}(\operatorname{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}(\operatorname{ext}_{u,v})=\psi_{L}(\operatorname{ext}_{u^{\prime},v^{\prime}})=e$
for some
$\operatorname{ext}_{u,v},\operatorname{ext}_{u^{\prime},v^{\prime}}\in\mathcal{O}(\Sigma^{\triangle})$
such that $\Delta(u),\Delta(u^{\prime})>0$ and
$\frac{|u|}{|v|}\not=\frac{|u^{\prime}|}{|v^{\prime}|}$. Without loss of
generality we may assume that $|v|=|v^{\prime}|$ (indeed, if
$|v|\not=|v^{\prime}|$, then
$\operatorname{ext}_{u^{|v^{\prime}|},v^{|v^{\prime}|}},\operatorname{ext}_{(u^{\prime})^{|v|},(v^{\prime})^{|v|}}$
satisfies the desired property). As a consequence we have
$|u|\not=|u^{\prime}|$, say $|u|<|u^{\prime}|$ 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^{\prime}$ for some
$f^{\prime}\in F$. Let us fix
$\operatorname{ext}_{x_{h},y_{h}}\in\psi_{L}^{-1}(h)$ and
$\operatorname{ext}_{x_{g},y_{g}}\in\psi_{L}^{-1}(g)$. We have
$\psi_{L}(\operatorname{ext}_{x_{g}ux_{h},y_{h}vy_{g}})=f^{\prime}=\psi_{L}(\operatorname{ext}_{x_{g}u^{\prime}x_{h},y_{h}v^{\prime}y_{g}})$.
Since $|x_{g}ux_{h}|<|x_{g}u^{\prime}x_{h}|$ and
$|y_{h}vy_{g}|=|y_{h}v^{\prime}y_{g}|$ it follows that
$\mathcal{R}_{f^{\prime}}$ 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}(\operatorname{ext}_{u,v})=\psi_{L}(\operatorname{ext}_{u^{\prime},v^{\prime}})=e$
for some
$\operatorname{ext}_{u,v},\operatorname{ext}_{u^{\prime},v^{\prime}}\in\mathcal{O}(\Sigma^{\triangle})$
such that $\Delta(u),\Delta(u^{\prime})>0$ and moreover either $u=u^{\prime}$
and $|v|\not=|v^{\prime}|$ or $v=v^{\prime}$ and $|u|\not=|u^{\prime}|$.
Without loss of generality let us assume that $u=u^{\prime}$ and
$|v|\not=|v^{\prime}|$. As mentioned above, there exist $g,h\in O_{L}$ such
that $g\circ e\circ h=f^{\prime}$ for some $f^{\prime}\in F$. Fix some
$\operatorname{ext}_{x_{g},y_{g}}\in\psi_{L}^{-1}(g)$ and some
$\operatorname{ext}_{x_{h},y_{h}}\in\psi_{L}^{-1}(h)$. Analogously, as argued
above, we have
$\psi_{L}(\operatorname{ext}_{x_{g}ux_{h},y_{h}vy_{g}})=\psi_{L}(\operatorname{ext}_{x_{g}ux_{h},y_{h}v^{\prime}y_{g}})=f^{\prime}$,
$\Delta(x_{g}ux_{h})>0$, and $|y_{h}vy_{g}|\not=|y_{h}v^{\prime}y_{g}|$,
implying that $\mathcal{R}_{f^{\prime}}$ is not weakly length-synchronous, a
contradiction to our assumption that $\mathcal{R}(G)=\bigcup_{f\in
F}\mathcal{R}_{f}$ is weakly length-synchronous. ∎

###  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
$\operatorname{nd}\colon\Sigma^{\triangle}\to\mathbb{N}$ defined inductively
as follows:

  * •

$\operatorname{nd}(\varepsilon)=0$;

  * •

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

  * •

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

  * •

$\operatorname{nd}(awb)=\begin{cases}\operatorname{nd}(w)+1&\text{if $w=uv$
with $u,v\in\Sigma^{\triangle}$ and
$\operatorname{nd}(w)=\operatorname{nd}(u)=\operatorname{nd}(v)$}\\\
\operatorname{nd}(w)&\text{otherwise}\end{cases}$ for all
$a\in\Sigma_{\text{call}}$, $b\in\Sigma_{\text{ret}}$ and
$w\in\Sigma^{\triangle}$.

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^{\triangle}$ there
exists a constant $d\in\mathbb{N}$ such that
$L\subseteq\\{w\in\Sigma^{\triangle}\mid\operatorname{nd}(w)\leq 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^{\triangle}$ with
$\operatorname{nd}(w)\geq 1$ is a factorization of $w$ as

$w=\operatorname{ext}_{x_{1},y_{1}}\circ\operatorname{ext}_{a_{1},b_{1}}\circ\cdots\circ\operatorname{ext}_{x_{k},y_{k}}\circ\operatorname{ext}_{a_{k},b_{k}}(w^{\prime})$

such that $k\geq 0$, $x_{i},y_{i}\in\Sigma^{\triangle}$,
$a_{i}\in\Sigma_{\text{call}}$, and $b_{i}\in\Sigma_{\text{ret}}$ for all
$i\in[1,l]$, and $w^{\prime}\in\Sigma_{\text{int}}^{*}$ satisfying that for
all $i\in[1,k]$ we have

$\operatorname{nd}(\operatorname{ext}_{x_{i},y_{i}}(w_{i}))=\operatorname{nd}(w_{i}),$

where
$w_{i}=\operatorname{ext}_{a_{i},b_{i}}\circ\operatorname{ext}_{x_{i+1},y_{i+1}}\circ\cdots\circ\operatorname{ext}_{a_{k},b_{k}}(w^{\prime})$.

######  Lemma 4.16.

All words $w\in\Sigma^{\triangle}$ 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^{\prime}b$ for $a\in\Sigma_{\text{call}}$, $b\in\Sigma_{\text{ret}}$ and
$w^{\prime}\in\Sigma^{\triangle}$. By using the inductive hypothesis,
$w^{\prime}$ has a nesting-maximal stair factorization
$\operatorname{ext}_{x_{1},y_{1}}\circ\operatorname{ext}_{a_{1},b_{1}}\circ\cdots\circ\operatorname{ext}_{x_{k},y_{k}}\circ\operatorname{ext}_{a_{k},b_{k}}(w^{\prime\prime})$.
It directly follows that
$\operatorname{ext}_{a,b}\circ\operatorname{ext}_{x_{1},y_{1}}\circ\operatorname{ext}_{a_{1},b_{1}}\circ\cdots\circ\operatorname{ext}_{x_{k},y_{k}}\circ\operatorname{ext}_{a_{k},b_{k}}(w^{\prime\prime})$
is a nesting-maximal stair factorization of $w$.