In this article we provide effective characterisations of regular languages of infinite trees that belong to the low levels of the Wadge hierarchy. More precisely we prove decidability for each of the finite levels of the hierarchy; for the class of the Boolean combinations of open sets $\boolcomb{1}$ (i.e. the union of the first $\omega$ levels); and for the Borel class $\bdelta{2}$ (i.e. for the union of the first $\omega_1$ levels).

§ INTRODUCTION

The space of all infinite trees over a finite alphabet is homeomorphic to the Cantor space. Therefore, it makes sense to ask if a language of infinite trees — in our setting, we are interested in regular ones — is for instance open, Borel, or of specific descriptive set theoretical complexity. As witnessed by a number of conjectures and results [39, 31, 19, 40, 14], topologically defined classes often have natural automata counterparts. For instance, in the case of $\omega$/̄words, the structure of parity deterministic automata (defined in terms of Wagner hierarchy) is strictly connected to the Wadge hierarchy, see [42]. In the case of regular tree languages that are Borel, there is a strong connection between the Borel rank and priorities used by weak alternating automata (see [15] and [14]).

Algorithms that determine if a regular language belongs to a subclass $\Ll$ of regular languages are known as effective characterisations. Typically, an effective characterisation comes with a structural description of automata (or algebras) that recognise languages from $\Ll$. The seminal example is Schützenberger's Theorem [37], which says that a regular language is star/̄free if and only if it is recognised by an aperiodic semigroup. For other examples about finite words, see the survey [35], which discusses effective characterisations for the low levels of the quantifier alternation hierarchy. For examples on $\omega$/̄words, including topologically motivated ones, see [34]. For examples on finite trees, see e.g. [11] or a survey [6].

Most of the known effective characterisations speak about languages of words (finite or infinite) or finite trees. The case of regular languages of infinite trees seems to be much more difficult, mainly because of the inherent non/̄determinism needed to recognise these languages [4, 10]. Thus, the known examples of effective characterisations are usually limited either to simple classes of sets (e.g. open sets [26, 43]) or to restricted classes of languages given as the input (e.g. recognised by deterministic automata [30]).

In this work we focus on the very low levels of the Borel hierarchy: the class $\boolcomb{1}$ of Boolean combinations of open sets; and the self/̄dual class $\bdelta{2}$ at the second level of the hierarchy. We use algebraic methods for infinite trees, i.e. our characterisations are defined by equations which must be satisfied by the syntactic algebra of a language.

This paper continues a line of work aimed at understanding the algebraic theory of regular languages of infinite trees [4, 10, 2]. The obtained results show that even simple algebras (i.e. not strong enough to distinguish all regular languages or not complete, see Subsection <ref>) can be adequate for characterising classes of languages that are sufficiently simple. This opens the possibility that a bit more complex algebraic structure (but a priori not complete) might be enough for the successive levels of the Borel hierarchy, like $\bdelta{3}$.

*Contribution of this article

decres=[draw, ultra thick, cap=round]

[toC] at (,+) $\{2^\w\}$;
[toC] at (,-) $\{\emptyset\}$;

[decres] (-0.4, --) – ++(0.8, 0.0);
[declab] at (, ---0.4) $(1)$;

[dot, scale=1.5] at (,) ;
[toC] at (,+) $\bsigma{1}$;
[toC] at (,-) $\bpi{1}$;

[decres] (-0.4, --) – ++(0.8, 0.0);
[declab] at (, ---0.4) $(2)$;

ıin 0,...,9
[dot, scale=*1.5] at (,) ;
[toC, scale=] at (,+) $\ndiff{\ind}{1}$;
[toC, scale=] at (,-) ${\mathcal{D}_{\ind}\complemento}(\bsigma{1})$;

[decres] (-0.7**, --) – ++(1.4**, 0.0);
[declab, scale=] at (, ---0.4) $(3)$;

[toC, scale=] at (,+) $\ndiff{\omega}{1}$;
[toC, scale=] at (,-) ${\mathcal{D}_{\omega}\complemento}(\bsigma{1})$;

[decres] (-0.7**, --) – ++(1.4**, 0.0);
[declab, scale=] at (, ---0.4) $?$;

ıin 0,...,11
[dot, scale=*1.5/0.65] at (,) ;
[toC, scale=] at (,+) $\ndiff{\omega+\ind}{1}$;
[toC, scale=] at (,-) ${\mathcal{D}_{\omega+\ind}\complemento}(\bsigma{1})$;

[decres] (-0.7**, --) – ++(1.4**, 0.0);
[declab, scale=] at (, ---0.4) $?$;

[toC] at (,+) $\bsigma{2}$;
[toC] at (,-) $\bpi{2}$;

[decres] (-0.4, --) – ++(0.8, 0.0);
[declab] at (, ---0.4) $(6)$;

[decres] (-0.4, ---1.0) – (, ---1.0);
[declab] at (-0.2+*0.5, ---1.4) $(4)$;

[decres] (+0.4, ---1.0) – (, ---1.0);
[declab] at (*0.5+*0.5, ---1.4) $(4)+(5)$;

[decres] (-0.4, ---1.9) – (, ---1.9);
[declab] at (-0.2+*0.5, ---2.3) $(5)$;

(-0.5, +0.5) edge[obrace] node $\boolcomb{1}$ (, +0.5);
(-0.5, +0.65) edge[obrace] node $\bdelta{2}$ (, +0.65);

(-0.1, ++0.3) arc (25:-25:*3);
(-0.1, ++0.3) arc (25:-25:*3);

[toL] at (-1.0, -0.3) $\omega$;
[->] (-0.9, -0.3) – ++(0.9, 0.0);

[toL] at (-1.0, -0.3) $\omega_1$;
[->] (-0.9, -0.3) – ++(0.9, 0.0);

The first $\omega_1+1$ levels of the Wadge hierarchy for infinite trees; together with their decidability results. The self/̄dual classes are depicted by $\bullet$, they are formed by the intersection of the two consecutive non self/̄dual classes.

Consider a class $\Gamma$ of languages (e.g. the class of open sets $\bsigma{1}$). Then, an effective characterisation of $\Gamma$ is an algorithm for the following decision problem:

[Effective Characterisation of $\Gamma$]

Given a representation of a regular language $L$, decide if $L \in \Gamma$.

As explained above, there are multiple results providing effective characterisations for various classes of languages. In this article we focus on the classes of the Wadge hierarchy inside $\bdelta{2}$, see Figure <ref> (the relevant technical notions are introduced in Section <ref>). Notice that, since regular languages are effectively closed under complement, an effective characterisation of $\Gamma$ provides at the same time an effective characterisation of $\Gamma\complemento$ and $\Gamma\cap\Gamma\complemento$. Thus, we will focus on non self/̄dual classes on one side of the hierarchy. Since $\trees_A$ is homeomorphic to $2^\omega$ (see Fact <ref>) all the results from Subsections <ref> and <ref> apply. Therefore, the Wadge hierarchy over $\trees_A$ introduces the following classes of sets:

* The class $\{\trees_A\}$. A language $L$ belongs to $\{\trees_A\}$ if and only if $L=\trees_A$, thus solving the effective characterisation for that class boils down to checking universality of $L$, which reduces to non/̄emptiness of the complement of $L$ [36].

* The class of open sets $\bsigma{1}$. That characterisation follows from [26, 43].

* The classes of the difference hierarchy $\ndiff{n}{1}$ for $2\leq n<\omega$. These classes are characterised in this paper, see Theorem <ref>.

* The class $\boolcomb{1}=\bigcup_{n\in\omega}\ndiff{n}{1}$ of Boolean combinations of open sets. This is the main contribution of this paper, see Theorem <ref>.

* The self/̄dual class $\bdelta{2}=\bigcup_{\xi<\omega_1}\ndiff{\xi}{1}$ of the Borel hierarchy. This result was claimed in [18], however the arguments there contain a flow, see discussion in Section <ref>. In this paper we provide a complete argument, see Theorem <ref>.

* The class $\bsigma{2}$ from the second level of the Borel hierarchy. This class seems to be out of reach of the algebras considered in this paper, see Subsection <ref>. However, an effective characterisation for that class exists, see [14].

What remains open is how to characterise the specific classes $\ndiff{\xi}{1}$ for $\omega\leq \xi<\omega_1$. Notice that there are only countably many regular languages and therefore there must exist $\xi_0<\omega_1$ such that no regular language belongs to $\ndiff{\xi}{1}$ for $\xi\geq \xi_0$. However, the value of $\xi_0$ is not known. Duparc and Murlak [15] have proved that there exist regular languages in any Wadge degree with Wadge rank less than $\omega^\omega$ (i.e. $\xi_0\geq\omega^\omega$). We do not know if $\xi_0=\omega^\omega$, even if this is a quite reasonable conjecture.

*Related work

First, a series of works [33, 32, 31, 19] provide effective characterisations for almost all natural classes when the input is restricted to deterministic automata or their dualised variant — the so/̄called game automata. These results are based on the pattern method saying that the language recognised by a deterministic automaton is complex if and only if the automaton itself contains a complex pattern. Unfortunately, there is no known method allowing to extend these techniques to languages involving non/̄determinism.

Recently, certain new techniques have been developed that show how to deal with the non/̄determinism of regular languages of infinite trees. The first result of this kind is the reduction of the general Rabin/̄Mostowski index problem to a certain boundedness problem for cost automata [13]. Unfortunately, the latter problem is not known to be decidable. However, the game approach used in the above reduction turned out to work for the lowest indices [12]. By adopting these techniques, the authors of [40] provided a characterisation of Borel sets among languages recognisable by Büchi automata. A similar approach used in [14] provided an effective characterisation of the Borel class $\bpi{2}$ among all regular tree languages. An effective (but not algebraic) characterisation of the class $\bdelta{2}$ follows directly from that result, however it does not solve the more difficult case of $\boolcomb{1}$.

The paper is based on the conference papers [9] and [18], see Conclusions for a discussion on relations between the new paper and the original ones.

*Structure The paper is structured as follows. In Section <ref> we recall some basic notions about words and trees and we set the notation used throughout the article, with a special emphasis on the topological hierarchies involved. In Section <ref> we describe a topological game that will be used to obtain effective characterisations of the levels of the Wadge hierarchy up to $\omega$. Subsection <ref> provides an easy application of the game to prove decidability of each of the first $\omega$ levels of the Wadge hierarchy (i.e. all the finite levels). Subsection <ref> extends the game to an infinite variant used later to characterise $\bdelta{2}$. In Section <ref> we present the algebraic structure used in this paper to represent regular languages of infinite trees. In Section <ref> we state Theorem <ref> characterising the class $\boolcomb{1}$ in terms of equations defined in the syntactic algebra. The proof of this theorem is spread across Subsections <ref>, <ref>, <ref> and <ref>. Finally, in Section <ref> we state and prove Theorem <ref> that uses the algebraic tools from Theorem <ref> to characterise the Borel class $\bdelta{2}$.

§ BASIC NOTIONS

If $f$ is a function, by $\dom(f)$ we denote the domain of $f$. We denote by $\omega$ the first infinite ordinal and by $\omega_1$ the first uncountable ordinal.

§.§ Words and trees

Consider a non/̄empty set $A$. We call $A$ an alphabet if $A$ is finite. Let $A^n$ be the space of the functions of the form $\fun{s}{\{0,\ldots,n{-}1\}}{A}$. Such a function can be represented as a word
$s=(s(0),\ldots, s(n{-}1))=s_0\cdots s_{n-1}$ over $A$. If $s=s_0s_1\cdots s_{n-1}$ then we say that $n$ is the length of $s$, and we denote it by $\lunghezza(s)$. The empty word is denoted by $\epsilon$, i.e. $\lunghezza(\epsilon)=0$ and $A^0=\{\epsilon\}$. By $A^{\leq n}$ we denote the set of words over $A$ of length at most $n$, i.e. $A^{\leq n} \eqdef A^0 \cup A^1 \cup \cdots \cup A^n$. We denote by $A^\ast$ the set of all the finite words over $A$: $A^\ast \eqdef \bigcup_{n \in \omega} A^n$. By $A^\omega$ we denote the set of infinite words over the alphabet $A$, formally the elements of this space are functions of the form $\fun{\alpha}{\omega}{A}$. Such a function can be represented as an infinite sequence
$(\alpha(0),\alpha(1),\alpha(2),\ldots)  = \alpha_0\alpha_1\alpha_2 \cdots$ Finally, we set $A^{\leq\w} \eqdef A^\ast \cup A^\omega$.

If $\alpha \in A^{\leq\omega}$ and $n \in \omega$, we define $\alpha\restr n\eqdef \alpha_0 \alpha_1\cdots \alpha_{n-1} \in A^n$ (if $\alpha$ is finite this definition makes sense only if $n \leq \lunghezza(\alpha)$). We say that $s \in A^\ast$ is a prefix of $\alpha \in A^{\leq\omega}$ if $s = \alpha\restr n$ for some $n$; in symbols $s \preceq \alpha$. We write $s\prec \alpha$ if $s \preceq \alpha$ but $s \neq \alpha$. The concatenation of $s,t \in A^\ast$, where $s=s_0 \cdots s_{n-1}$ and $t=t_0 \cdots t_{m-1}$, is the word $s\concat t= st= s_0 \cdots s_{n-1}t_0 \cdots t_{m-1}$. We can also consider the concatenation $s\concat \alpha$ of a finite word $s$ and an infinite word $\alpha$ defined in the obvious way: $s\concat \alpha = s_0 s_1 s_2 \cdots s_{\lunghezza(s)-1}\alpha_0\alpha_1\cdots$

Now let us generalise these notions to trees. In this article, we focus on trees with binary branching, where the two directions are left $\dL$ and right $\dR$. A partial tree over an alphabet $A$ is a partial function $\parfun{t}{{\{\dL,\dR\}}^\ast}{A}$ with a non/̄empty prefix/̄closed domain $\dom(t)$ (i.e. if $s \in \dom(t)$ and $s' \preceq s$ then $s' \in \dom(t)$). A node $u\in\dom(t)$ is either an internal node (i.e. both $u\concat\dL$ and $u\concat\dR$ belong to $\dom(t)$), a unary node (i.e. exactly one of $u\concat\dL$ and $u\concat\dR$ belongs to $\dom(t)$), or a leaf (i.e. none of $u\concat \dL$ and $u \concat \dR$ belongs to $\dom(t)$). For the sake of readability, we write $u\in t$ to denote that $u\in\dom(t)$ is a node of $t$. The empty sequence $\epsilon$ belongs to every partial tree and it is called the root of a tree. A branch of a partial tree $t$ is a word $\pi$ such that $\pi\restr n \in t $ for any $n \leq \lunghezza(\pi)$ if $\pi$ is finite (resp. for any $n \in \omega$ if $\pi$ is infinite). An infinite branch of a partial tree $t$ is called a path of $t$. A node $u$ is on a branch (finite or infinite) $\pi$ if it is a prefix of $\pi$, i.e. if $u \preceq \pi$. A partial tree $t$ is finite if its domain $\dom(t)$ is finite. A tree is a partial tree $t$ with $\dom(t) = {\{\dL, \dR\}}^\ast$ (i.e. a complete tree). The set of all trees over an alphabet $A$ is denoted $\trees_A$, that is $\trees_A \eqdef\{ t \mid \fun{t}{{\{ \dL, \dR\}}^\ast}{A}\}$.

If $p$ and $t$ are partial trees, we say that $p$ is a prefix of $t$, and we denote it by $p \preftree t$, if $\dom(p) \subseteq \dom(t)$ and $p(u)=t(u)$ for any $u \in \dom(p)$. We write $p \strictpreftree t$ if $p \preftree t$ but $p \neq t$. Finally, if $t$ is a partial tree and $u$ is a node of $t$, by $t.u$ we indicate the partial tree $t$ truncated in $u$: for any $w$ such that $uw \in \dom(t)$, we have $t.u(w)=t(uw)$.

For $d>0$ a $d$/̄prefix of a tree $t$ is the prefix $p\eqdef t\restr{\{\dL,\dR\}}^{< d}$, i.e. the prefix of $t$ containing all the nodes at depths smaller than $d$. For instance, the $1$/̄prefix of $t$ consists of the root of $t$ only.

A subset $L \subseteq \trees_A$ is a tree language. Regular tree languages are the ones recognised by parity non/̄deterministic automata or, equivalently, definable in Monadic Second/̄order Logic (for this equivalence see for example [21]).

§.§ Polish spaces

The subsequent subsections recall the topological notions coming from Descriptive Set Theory that we will use throughout the article. We do not aim for completeness, for more details we refer the reader to [25]. In the first subsection we define Polish spaces, that are the main objects studied in Descriptive Set Theory. In the remaining section we introduce the main hierarchies usually considered for Polish spaces, i.e. the Borel, difference, and Wadge hierarchies.

We denote a topological space by $(X,\tau)$, where $X$ is a non/̄empty set and $\tau$ is a family of subsets of $X$ called open sets. If $\tau$ is understood from the context we write just $X$ and suppress $\tau$ from the notation. We say that $X$ is a Polish space if $\tau$ is completely metrizable (i.e. there exists a complete metric on $X$ that generates $\tau$) and separable (i.e. there exists a countable dense subset of $X$).

If a space $X$ is known from the context and $A\subseteq X$ then by $A\complemento\eqdef X\setminus A$ we denote the complement of $A$ in $X$. Similarly, if $\Gamma$ is a family of subsets of $X$ then $\Gamma\complemento\eqdef\{A\complemento\mid A\in\Gamma\}$.

Consider a non/̄empty at most countable set $B$. We will now introduce the so/̄called prefix topologies on the spaces $B^\w$ and $\trees_B$ by providing explicitly their bases. However, it is worth noticing that these topologies coincide with the Tychonoff topologies when $B$ is considered as a discrete topological space, see <cit.>.

The prefix topology on the space of infinite words $B^\omega$ over $B$ is generated by the basic open sets of the form:

\[ N_s = \{ \alpha \in B^\w \mid s \prec \alpha\},\]

with $s \in B^\ast$. When $B= \{0,1\}$, we obtain the Cantor space, denoted by $2^\w$. When $B= \omega$, we obtain the Baire space, denoted by $\w^\w$. Every space of the form $B^\w$ with the prefix topology is Polish. It is easy to check that the prefix topology is completely metrizable: the metric  $d(\alpha, \beta) = 2^{-n}$, where $n$ is the minimum index such that $\alpha(n) \neq \beta(n)$ (and $d(\alpha,\beta)=0$ if $\alpha=\beta$), is complete and it generates the prefix topology. Moreover, if we fix a symbol $c \in B$, the set

\[ D= \{ s\concat ccc\cdots \mid s \in B^\ast\}\]

is countable (since $B^\ast$ is countable) and dense, so $B^\w$ is separable. In particular, the Cantor space and the Baire space are Polish spaces.

The prefix topology can easily be generalised to trees $\trees_A$, with basic open sets of the form:

\[ N_p = \{t \in \trees_A \mid p \strictpreftree t \},\]

where $p$ is a finite partial tree. Every $N_p$ is actually a clopen (i.e. both open and closed). We denote this topology by $\toppref$. The topology $\toppref$ is generated by several metrics. The usual metric considered to generate $\toppref$ is $\metricpref(t_1,t_2) = 2^{-n}$ where $n$ is the minimum length of a node $u$ such that $t_1(u) \neq t_2(u)$ (and $\metricpref(t_1,t_2)=0$ for $t_1=t_2$). Each open ball of $\metricpref$ is a basic clopen set $N_p$ for a certain finite partial tree $p$.

Notice that the metric $\metricpref$ satisfies the following strengthening of the triangle inequality:

\[\metricpref(x,z)\leq \max \big(\metricpref(x,y),\metricpref(y,z)\big).\]

Such a metric is called an ultrametric, see <cit.>. This property makes $\metricpref$ too rigid for our way of choosing optimal witnesses (see Definition <ref> of optimal strategy trees). Therefore, we will also consider a different metric, denoted by $\topdisc$ and called the discounted distance. This metric also generates $\toppref$ but has a less intuitive family of open balls. Fix some enumeration $u_0, u_1, \ldots$ of all the nodes in ${\{\dL,\dR\}}^\ast$. Given two trees $t_1$ and $t_2$, for any node $u$, define $\dist(t_1(u),t_2(u))= 0$ if $t_1(u) = t_2(u)$, $1$ in the other case. Let

\[\topdisc(t_1,t_2) \eqdef \sum_{n \geq 0} \frac{1}{2^n}\cdot \dist\big(t_1(u_n),t_2(u_n)\big).\]

Regardless of the enumeration $(u_0, u_1,\ldots)$, the prefix and discounted distances yield the same topology.

It is enough to observe that $\toppref$ is exactly the product topology obtained by starting from the discrete topology and the discounted distance is exactly the product metric.

$\trees_A$ with the topology $\toppref$ is a Polish space homeomorphic to the Cantor space $2^\omega$.

The proof is a standard encoding of one compact product space into another. One can also use a characterisation of the Cantor space, see <cit.>.

§.§ The Borel hierarchy

Let $(X,\tau)$ be a topological space. Recall that $\omega_1$ is the first uncountable ordinal. We define, by a transfinite recursion on $1 \leq \xi < \omega_1$, the following classes:

\begin{align*}
\bsigma{1}(X) &\eqdef \{A\subseteq X \mid A \text{ is open} \};\\
\bpi{\xi}(X) &\eqdef \{A\complemento\subseteq X \mid A\in \bsigma{\xi} (X) \}= \big(\bsigma{\xi}(X)\big)\complemento;\\
\bsigma{\xi}(X) &\eqdef \big\{ \bigcup_n A_n \mid A_n \in \bpi{\xi_n} (X), \ 1\leq  \xi_n < \xi, \ n \in \omega  \big\}.
\end{align*}

Moreover, for $1 \leq \xi < \omega_1$, we define the intersection of the two classes $\bdelta{\xi}(X)\eqdef \bsigma{\xi}(X) \cap \bpi{\xi}(X)$.

For each $1\leq\xi<\omega_1$, the classes $\bsigma{\xi}(X)$ and $\bpi{\xi}(X)$ are closed under finite unions and finite intersections. The class $\bdelta{\xi}(X)$ is also closed under complement and therefore forms a Boolean algebra.

The smallest Boolean algebra containing all the sets from $\bsigma{\xi}(X)$ is denoted $\boolcomb{\xi}(X)$. The above fact implies that $\boolcomb{\xi}(X)\subseteq \bdelta{\xi+1}(X)$. For uncountable Polish spaces the inclusion is strict, this fact follows from <cit.>.

The Borel sets of $X$ are:

\[ \borel(X) = \bigcup_{\xi \in \omega_1} \bsigma{\xi}(X) = \bigcup_{\xi \in \omega_1} \bpi{\xi}(X)= \bigcup_{\xi \in \omega_1} \bdelta{\xi}(X).\]

When the space $X$ is clear from the context, we omit it and write just $\bsigma{\xi}$, $\bpi{\xi}$, etc…

Notice that if $\xi\leq \xi'<\omega_1$ then directly from the definition we know that $\bsigma{\xi}\subseteq\bsigma{\xi'}$. The following fact shows that the opposite containment does not hold in general.

Let $(X,\tau)$ be an uncountable Polish space. Then the Borel hierarchy of $X$ does not collapse i.e. every class $\bsigma{\xi}$ is properly contained in $\bsigma{\xi +1}$.

For the rest of the article we will focus on the first two levels of the Borel hierarchy, as depicted in Figure <ref>.

in 1, 2
(s-) at (*-1,1) $\bsigma{\x}$;
(b-) at (*,0) $\boolcomb{\x}$;
(p-) at (*-1,-1) $\bpi{\x}$;

in 2, 3
(d-) at (*-2,0) $\bdelta{\x}$;

at (*2.85,+1) $\cdots$;
at (*2.85,-1) $\cdots$;

/→in 1/2, 2/3
[-] (p-) – (b-);
[-] (s-) – (b-);

[-] (b-.east) – (d-→.west);

[-] (d-2) – (s-2);
[-] (d-2) – (p-2);

The first levels of the Borel hierarchy.

§.§ The difference hierarchy

The Borel hierarchy is refined by the so/̄called the difference hierarchy, see <cit.>. First notice that every ordinal $\theta$ can be uniquely written as $\lambda+n$, where $\lambda$ is $0$ or a limit ordinal and $n \in \omega$. We say that the parity of $\theta$ is even (resp. odd) if $n$ is even (resp. odd).

Let $X$ be a topological space, $\Gamma$ a family of subsets of $X$, and $\theta<\omega_1$ a countable ordinal. A set $A\subseteq X$ is called a $\theta$/̄difference of $\Gamma$ sets if and only if there exists a $\theta$/̄indexed sequence of sets ${(A_\eta)}_{\eta<\theta}\subseteq\Gamma$ that is non/̄decreasing (i.e. $A_{\eta} \subseteq A_{\eta'}$ if $\eta\leq \eta'$) and:

\begin{align*}
x \in A \Longleftrightarrow & \text{ the minimum $\eta<\theta$ such that $x \in A_\eta$,}\\
&\text{ has parity opposite to that of $\theta$.}
\end{align*}

The family of all $\theta$/̄differences of $\Gamma$ sets is denoted ${\mathcal{D}_{\theta}}(\Gamma)$. In particular, for each $\xi<\omega_1$ the class $\ndiff{\theta}{\xi}(X)$ is the family of all $\theta$/̄differences of sets from the Borel class $\bsigma{\xi}(X)$.

The above definition requires the sequence ${(A_\eta)}_{\eta<\theta}$ to be non/̄decreasing and we will focus on $\Gamma=\bsigma{\xi}(X)$. These are important assumptions, because of the following remark.

For each $\xi<\omega_1$ we have $\mathcal{D}_\omega\big(\bpi{\xi})=\bsigma{\xi+1}$.

The inclusion $\mathcal{D}_\omega\big(\bpi{\xi})\subseteq\bsigma{\xi+1}$ follows directly from the definition. For the opposite direction, consider a set $A\in\bsigma{\xi+1}$. It is easy to check that $A$ can be written as $\bigcup_{n\in\w} A_n$ with ${(A_n)}_{n\in\omega}$ non/̄decreasing and each $A_n$ in $\bpi{\xi}$. Then take $A'_n\eqdef A_{\lfloor n\rfloor}$ and notice that this sequence is also non/̄decreasing and contains only $\bpi{\xi}$ sets. However, $x\in A$ iff $\exists n.\ x\in A_n$ iff the minimum $n$ such that $x\in A_n'$ is even. Therefore, $A$ is an $\omega$/̄difference of $\bpi{\xi}$ sets and $A\in \mathcal{D}_\omega\big(\bpi{\xi})$.

Notice that for a natural number $n$ we have $A \in  \ndiff{n}{\xi}$ if and only if it can be written as follows (see Figure <ref>):

\begin{align}
A &= A_0 \cup (A_2 \setminus A_1) \cup \cdots \cup (A_{n-1} \setminus A_{n-2})&\text{if $n$ is odd,}
\label{eq:form-diff-n-odd}\\
A &=  (A_1 \setminus A_0) \cup \cdots \cup (A_{n-1} \setminus A_{n-2})&\text{if $n$ is even,}
\label{eq:form-diff-n-even}
\end{align}

with $A_0, \ldots, A_{n-1}$ belonging to $\bsigma{\xi}$.

As one can easily check from the definition, the classes $\ndiff{\eta}{\xi}$ are monotone both in $\eta$ and in $\xi$.

For each $\eta\leq \eta'$ and $\xi\leq \xi'$ we have

\[\ndiff{\eta}{\xi}\subseteq \ndiff{\eta'}{\xi'}.\]

The following theorem shows that the difference hierarchy over $\bsigma{\xi}$ saturates the successive class $\bdelta{\xi+1}$.

lll=[scale=0.8, anchor=south west, inner sep=0]

(z) at (0,0);

[black] (z) circle (*11);
[white] (z) circle (*9);
[black] (z) circle (*5);
[white] (z) circle (*3);
[black] (z) circle (*1);

[toC, scale=2.2] at (0, *6+0.15) $\vdots$;

[lll, black] at (*1.1,*1.1) $A_0$;
[lll, white] at (*3.2,*3.2) $A_1$;
[lll, black] at (*5.2,*5.2) $A_2$;
[lll, white] at (*9.2,*9.2) $A_{n-2}$;
[lll, black] at (*11.2 ,*11.2 ) $A_{n-1}$;

A set $A=A_0 \cup (A_2 \setminus A_1) \cup \cdots \cup(A_{n-1} \setminus A_{n-1})$ ($A$ is the union of the black parts) with $A_0 \subseteq A_1 \subseteq A_2 \subseteq \cdots \subseteq A_{n-2} \subseteq A_{n-1}$ and $A_i \in \bsigma{\xi}$ for every $i$.

In Polish spaces and for any $1 \leq \xi < \omega_1$ we have that

\[\bdelta{\xi+1}= \bigcup_{1 \leq \theta < \omega_1} \ndiff{\theta}{\xi}.\]

Similarly, the first $\omega$ levels of the hierarchy coincide with the class $\boolcomb{\xi}$:

In Polish spaces and for any $1 \leq \xi < \omega_1$ we have that

\[\boolcomb{\xi}= \bigcup_{1 \leq \theta < \omega} \ndiff{\theta}{\xi}.\]

§.§ The Wadge hierarchy

We are now in the position to define the Wadge hierarchy of a general topological space. Later in the article we will focus on the specific case of the Wadge hierarchy of the Cantor space $2^\w$.

Let $X$, $Y$ be two topological spaces. We say that a set $A \subseteq X$ continuously reduces to $B\subseteq Y$ if there is a continuous function $\fun{f}{X}{Y}$ such that the pre/̄image $f^{-1}(B)=\{x\in X \mid f(x) \in B\}$ is equal to $A$ (i.e. $x \in A \Leftrightarrow f(x) \in B$ for every $x \in X$).

The following proposition shows that continuous reductions preserve the topological classes defined above.

Let $\Gamma$ be a level of the Borel hierarchy or of the difference hierarchy. Then $\Gamma$ is closed under continuous preimages: if $B$ is a subset of a topological space $Y$ such that $B \in \Gamma(Y)$ and $\fun{f}{X}{Y}$ is a continuous function from a topological space $X$ to $Y$, then $f^{-1}(B) \in \Gamma(X)$.

Now we are in place to define the Wadge order.

Let $X$ and $Y$ be two topological spaces and let $A \subseteq X$ and $B \subseteq Y$. We say that $A$ is Wadge reducible to $B$, and we denote it by $A \wadgeq B$, if there exists a continuous reduction of $A$ to $B$. We say that $A$ is Wadge equivalent to $B$, in symbols $A \wadgee B$, if $A \wadgeq B$ and $B \wadgeq A$. Finally, we write $A \wadge B$ if $A \wadgeq B$ and $B \wadgeq A$ does not hold.

${\wadgeq}$ is an equivalence relation.

The relation ${\wadgeq}$ induces a partial order between the ${\wadgee}$/̄classes, called Wadge degrees, of subsets of topological spaces. If we fix a space $X$ and we restrict the ordering induced by $\wadgeq$ to the sets of $X$, we obtain the Wadge hierarchy of $X$. If $A$ is a subset of $X$, then by ${[A]}_{\mathrm{W}}$ we denote its Wadge degree:

\[ {[A]}_{\mathrm{W}} = \{B \subseteq X \mid B \wadgee A\}.\]

Even tough the Wadge hierarchy can be defined for any topological space, its shape for a generic space can be very complicated (for example the Wadge hierarchy of many non zero/̄dimensional topological spaces, including the space of real numbers, is very complicated: see for instance [28] and [29]).
Also, the good properties of the hierarchy (like its width or well/̄foundedness) depend on the determinacy of related games. Therefore, in our work we will restrict our attention to the order ${\wadgeq}$ restricted to the first levels of the Borel hierarchy of the Cantor space $2^\omega$. We refer the reader to [1] for a description of the structure of the Wadge hierarchy for $2^\omega$.

For any $A, B \in \borel(2^\w)$ it holds that

\[ A \wadgeq B \quad \text{or} \quad B\complemento \wadgeq A.\]

The ordering ${\wadgeq}$ among the Borel sets of $2^\w$ is well/̄founded.

A set which is Wadge reducible to its complement is called self/̄dual, otherwise it is called non self/̄dual.

It is easy to check that every non/̄trivial (i.e. different than $\emptyset$ and $2^\w$) clopen subset of $2^\w$ is self/̄dual.

Since the notion of self/̄duality is invariant under $\wadgee$ we can speak of self/̄dual and non self/̄dual Wadge degrees. If ${[A]}_{\mathrm{W}}$ is a non self/̄dual Wadge degree then we say that the pair $\{{[A]}_{\mathrm{W}},{[A\complemento]}_{\mathrm{W}}\}$ is a non self/̄dual pair.

The anti/̄chains in the Wadge degrees have length at most $2$ and are of the form

\[ \big\{{[A]}_{\mathrm{W}}, {[A\complemento]}_{\mathrm{W}}\big\},\]

with $A$ non self/̄dual.

Notice that technically every Wadge degree does not contain the elements contained in the previous degrees of the hierarchy. For example, the Wadge degree ${[C]}_{\mathrm{W}}$, where $C$ is a clopen set different from $2^\w$ and $\emptyset$, contains all the clopen sets except the whole space $2^\w$ and the empty set $\emptyset$. This is obvious, since any Wadge degree is an equivalence class of the relation ${\wadgee}$. We define the Wadge class of a set as the union of its Wadge degree with all its predecessors in the hierarchy. For example the Wadge class $\bdelta{1}$ is obtained by taking the union of the Wadge degree $\bdelta{1} \setminus \{ \emptyset, 2^\w\}$ with its predecessors $\{\emptyset\}$ and $\{ 2^\w\}$. It is clear that the two hierarchies, the one of Wadge degrees and the one of Wadge classes, are isomorphic as orders, so we can treat both the hierarchies in the same way. In the pictures of this section we show the hierarchy of the Wadge classes, because they are more intuitive and easier to describe.

In the Cantor space, ${[2^\w]}_{\mathrm{W}}=\{2^\w\}$ and ${[\emptyset]}_{\mathrm{W}}=\{ \emptyset\}$ are the two minimal Wadge degrees and they clearly form a non self/̄dual pair. Then we have the Wadge degree formed by any clopen set different from $2^\w$ and $\emptyset$  and this is a self/̄dual Wadge degree. The hierarchy continues with a constant alternation of a non self/̄dual pair and one self/̄dual Wadge degree. All the limit levels of the Wadge hierarchy consist of a non self/̄dual pair. Certain specific Wadge classes coincide with the levels of the Borel hierarchy.

Hence, the Wadge hierarchy of the Cantor space has the shape as depicted in Figure <ref>.

Now we can assign an ordinal to any level of the hierarchy. This ordinal is the Wadge rank of a Wadge degree (or of the corresponding Wadge class). The two bottom Wadge degrees $\{\emptyset\}$ and $ \{2^\w\}$ have Wadge rank $1$, the Wadge degree $\bdelta{1} \setminus \{\emptyset, 2^\w\}$ has Wadge rank $2$ (so it has the Wadge class $\bdelta{1}$), and so on.

Among the non self/̄dual Wadge classes we find the classes $\bsigma{n}$ and $\bpi{n}$. The classes $\bsigma{1}$ and $\bpi{1}$ are immediately after the Wadge class $\bdelta{1}$, so their Wadge rank is $3$. Then, between the non self/̄dual pair

\[\{\bsigma{n}, \bpi{n}\}\]

and the successive

\[\{\bsigma{n+1}, \bpi{n+1}\}\]

there are $\omega_1^{\omega_1^{\iddots_{n \text{ times} }^{\omega_1}}}$ Wadge classes. In particular, there are $\omega_1$ Wadge classes between the pair $\{\bsigma{1}, \bpi{1}\}$ and $\{\bsigma{2} , \bpi{2} \}$. Hence, the Wadge rank of the Wadge classes $\bsigma{2}$ and $\bpi{2}$ is $\omega_1$, and the Borel class $\bdelta{2}$ contains $\omega_1$ different levels of the Wadge hierarchy.

[dot, scale=2.0] at (-10,+1) ;
[toC, inner sep=0, anchor=north] at (-10, +1.8) $\{2^\w\}$;
[dot, scale=2.0] at (-10,-1) ;
[toC, inner sep=0, anchor=south] at (-10, -1.8) $\{\emptyset\}$;
[dot, scale=2.0] at (-9,0) ;
[toC, inner sep=0, anchor=north] at (-9, +0.6) $\bdelta{1}$;
[dot, scale=2.0] at (-8,+1) ;
[toC, inner sep=0, anchor=north] at (-8, +1.8) $\bsigma{1}$;
[dot, scale=2.0] at (-8,-1) ;
[toC, inner sep=0, anchor=south] at (-8, -1.8) $\bpi{1}$;
[scale=3.0] at (-6,0) …;
[toC, inner sep=0, anchor=north] at (-6, +0.6) $\omega_1$ alternations;
[dot, scale=2.0] at (-4,+1) ;
[toC, inner sep=0, anchor=north] at (-4, +1.8) $\bsigma{2}$;
[dot, scale=2.0] at (-4,-1) ;
[toC, inner sep=0, anchor=south] at (-4, -1.8) $\bpi{2}$;
[dot, scale=2.0] at (0,+1) ;
[scale=3.0] at (-2,0) …;
[toC, inner sep=0, anchor=north] at (-2.1, +0.6) $\omega_1^{\omega_1}$ alternations;
[toC, inner sep=0, anchor=north] at (0, +1.8) $\bsigma{3}$;
[dot, scale=2.0] at (0,-1) ;
[toC, inner sep=0, anchor=south] at (0, -1.8) $\bpi{3}$;
[scale=3] at (1,0) …;

An initial fragment of the Wadge hierarchy inside the Borel hierarchy of $2^\w$.

Now we focus on the segment that we will study in this article, that is the initial segment from the beginning of the hierarchy until the Wadge classes $\bsigma{2}$ and $\bpi{2}$. Using this notion we can express a characterisation of the first $\omega_1$ levels of the Wadge hierarchy in $2^\omega$ in terms of the difference hierarchy.

For every $m\geq 1$ every class $\ndiff{\theta}{m}$ corresponds to a Wadge class of a non self/̄dual pair. For $m=1$ these are essentially all Wadge classes: there is no non self/̄dual Wadge class between $\ndiff{\theta}{1}$ and $\ndiff{\theta+1}{1}$. Therefore, Figure <ref> depicts the first $\omega_1$ levels of the Wadge hierarchy.

Hence, in the Cantor space the difference hierarchy is an important tool to understand the Wadge hierarchy, especially in the initial part up to $\bsigma{2}$. Beyond that level, the difference hierarchy becomes much coarser (i.e. it skips a lot of Wadge degrees).

§ THE GAME FOR WADGE RANKS

In this section we define a game that we will use in this article to obtain results of decidability of Wadge degrees with Wadge ranks up to $\omega$ (i.e. the classes $\ndiff{n}{1}$ for $n\in\w$). This game is played by two players, named Alternator and Constrainer and it is a finite duration game. In this article we work on the space $\trees_A$, but a priori this game can be defined in any topological space and the characterization that it gives holds in general. Yet, in the case of regular languages of trees, it is possible to decide which player wins the game. This fact will be crucial to state the results about decidability.

Let us describe the game. Let $X$ be a topological space, $U_0\subseteq X$ open and non/̄empty, and let $X_1, \ldots,X_n$ be arbitrary subsets of $X$. We define the game

\[ \gameH_{U_0}(X_1, \ldots, X_n)\]

played by Constrainer (choosing open subsets of $X$) and Alternator (choosing points of $X$). The game will last for $n$ rounds, a round $i$ for $1,\ldots, n$ of the game is played as follows:

* Alternator chooses a point $x_i \in U_{i{-}1}\cap X_i$.
If there is no such point $x_i$, the game is interrupted and Constrainer wins immediately.

* Constrainer chooses an open set $U_i\subseteq U_{i-1}$ that contains $x_i$ and the next round is played.

If Alternator manages to survive $n$ rounds then he wins, otherwise Constrainer wins.

A special variant of the game, when $U_0=X$ is the whole space, is denoted simply as $\gameH(X_1,\ldots,X_n)$.
Now we prove some properties of this game.

Let $(X, \tau)$ be a topological space, $U\subseteq X$ open non/̄empty, and let $X_1, \ldots, X_n$ be subsets of $X$. Consider the game $\gameH_U(X_1, \ldots, X_n)$. In this framework we can represent a position of a play trough a tuple

\[ \langle U_0, x_1, U_1, x_2, U_2, \ldots, x_i, U_i\rangle,\]

where $x_1, \ldots, x_i \in X$ and $U_0, U_1, \ldots, U_i \in \tau$ with $U_0=U$.
A strategy for Constrainer in the game $\gameH_U(X_1, \ldots, X_n)$ is a function

\[ \fun{\sigma}{X^{\leq n}}{\tau}.\]

If $s$ is a word belonging to $X^{\leq n}$ compatible with the game $\gameH$ and with $\sigma$, then $\sigma(s)$ is the open set played by Constrainer in the position

\[\langle s_0, \sigma(s_0), s_1, \sigma(s_0s_1),\ldots, s_{\lunghezza(s)-1}, \sigma(s)\rangle.\]

If $s$ does not represent a position compatible with the game $\gameH$ and with $\sigma$ (for example because the second letter of $s$ is not an element of $X_2$ or it is not an element of $\sigma(s_0)$), then we put $\sigma(s)= \emptyset$ by convention. As usual, a strategy $\sigma$ for Constrainer is winning if Constrainer wins every play where he follows $\sigma$. In a specular way we could define strategies for Alternator, but we will not use them in this article.

Since the duration of the game is finite, it is determined — one of the players has a winning strategy. The following remark is not used in this article but provides a simplified form for the strategies of the players.

The game $\gameH_U(X_1,\ldots,X_n)$ is positionally determined: the winner of the game does not change if we insist that the players' strategies depend only on the number of the round and the last move of the opponent. This means that we can freely assume that Alternators's point $x_i$ depends only on $i$ and the current open set $U_{i-1}$; while Constrainer's open set $U_i$ depends only on $i$, the current point $x_i$, and the previous open set $U_{i-1}$.

The first property we prove is Refinement Lemma, that states that if the sets $X_1, \ldots, X_n$ are split into finitely many parts each and Alternator wins $\gameH(X_1, \ldots ,X_n)$ then he can win for some choice of parts of $X_1, \ldots, X_n$.

Let $X_1, \ldots, X_n$ be subsets of a topological space $X$. For $i \in \{1,\ldots, n\}$, let $\mathcal{Y}_i$ a finite family
of sets partitioning $X_i$. For any non/̄empty open $U\subseteq X$, if Alternator wins

\[ \gameH_U(X_1, \ldots ,X_n)\]

then there exist $Y_1 \in  \mathcal{Y}_1, \ldots, Y_n \in \mathcal{Y}_n$ such that Alternator wins

\[\gameH_U(Y_1, \ldots, Y_n).\]

We prove the theorem by induction on $n$.
The induction base is immediate, because Alternator always wins when $n = 0$ and he wins when $n=1$ if and only if $X_1\neq\emptyset$. Now prove the induction step. Consider the first move by Alternator, and assume that he chooses the same point $x \in U$ as chosen by his winning strategy in $\gameH_U(X_1, \ldots ,X_n)$. This point necessarily belongs to some $Y_1 \in \mathcal{Y}_1$. For $i \in \omega$, let $U_i$ be the open ball around $x$ of radius $\frac{1}{i}$. By the definition of the game, we know that for every $i<\w$ Alternator wins

\[\gameH_{U_i} (X_1, \ldots , X_n).\]

Thus, he also wins $\gameH_{U_i}(X_2,\ldots,X_n)$ and by the inductive assumption, we know that for every $i$ there exist $Y^{(i)}_2 \in
\mathcal{Y}_2$, …, $Y^{(i)}_n \in \mathcal{Y}_n$ such that Alternator wins

\[ \gameH_{U_i}(Y^{(i)}_2, \ldots, Y^{(i)}_n).\]

By Pigeon/̄hole Principle,
there must be some $Y_2$, …, $Y_n$ such that

\[ (Y_2, \ldots, Y_n) = (Y^{(i)}_2, \ldots, Y^{(i)}_n)\]

holds for infinitely many $i$. Since the game $\gameH_V(Y_2, \ldots, Y_n)$ grows more difficult for Alternator as the open set $V$ becomes smaller, and since every open set $V$ that contains $x$ contains some $U_i$, we conclude that Alternator wins

\[\gameH_V (Y_2, \ldots ,Y_n)\]

for every $V$ that contains $x$. By viewing $V$ as a response of Constrainer to Alternator's move
$x \in Y_1$, we conclude that Alternator wins the game

\[\gameH_U(Y_1, \ldots ,Y_n). \qedhere\]

Now let $Y$ be a subset of our topological space $X$ and consider a particular case of the game where the sets $X_1, \ldots, X_n$ alternate between $Y$ and its complement, i.e. we consider $\gameH(X_1, \ldots, X_n)$ where $X_i$ is $Y$ if $i$ is odd, $Y\complemento$ otherwise. We denote by $\gameHs(Y,n)$ that game and by $\gameHs_U(Y,n)$ the variant relativised to a non/̄empty open set $U\subseteq X$.

Consider the game where the topological space $X$ is the space of real numbers $\R$ and $Y=\Q$, i.e. the rational numbers. Then for every $n$, Alternator wins the game $\gameHs(Y,n)$.

Notice that if Alternator wants to survive in $\gameHs(Y,n)$ as long as possible, he has to avoid to play points in the interior[Recall that the interior of a set $Y$ is the union of all open sets contained in $Y$.] of $Y$ and the interior of $Y\complemento$. For example, if at the first round Alternator plays $x$ belonging to the interior of $Y$ then Constrainer can play (a subset of) the interior of $Y$ and Alternator loses because he cannot go outside $Y$ any more.

In the real numbers $\R$, let $Y$ be the complement of $\{ \frac{1}{n}\in\R \mid n \in \omega\}$.
Alternator wins $\gameHs(Y,3)$. Indeed, in the first round Alternator can play $0 \in Y$. In the second round, Alternator plays $\frac{1}{n}\notin Y$ for some large $n$ depending on Constrainer's move. In the third round, Alternator plays $\frac{1}{n} + \epsilon \in Y$, for some small $\epsilon$ depending on Constrainer's move.

We now argue that Constrainer wins $\gameHs(Y,n)$ for $n \geq 4$. Notice that since $x_2$ must belong to $Y^\cp=\{ \frac{1}{n}\in\R \mid n \in \omega\}$, Constrainer can choose $U_2\subseteq U_1$ in such a way to guarantee that $x_2\in U_2$ but $0\notin U_2$. Then Alternator chooses a point $x_3\in Y\cap U_2$ that must be distinct from $0$. Thus, there exists an open set $U_3$ such that $x_3\in U_3\subseteq U_2$ but $U_3\subseteq Y$. This guarantees that Alternator is not able to choose $x_4\in Y^\cp\cap U_3$, making him lose the game $\gameHs(Y,4)$.

Let $\sigma_1$ and $\sigma_2$ be two strategies for Constrainer such that $\sigma_1 (s) \subseteq \sigma_2(s)$ for any finite word $s\in X^{\leq n}$. If $\sigma_2$ is winning for Constrainer then $\sigma_1$ is winning for Constrainer too.

Choose some basis $B$ for the topology of the topological space $X$. If Constrainer has a winning strategy in $\gameHs(Y,n)$ then he has a winning strategy which uses only basic open sets from $B$.

Consider any function $f$ that to every pair $(U,x)$, where $U$ is an open set and $x \in U$, assigns a basic open set $V\in B$ such that $x \in V$ and $V \subseteq U$. Let $\sigma$ be a winning strategy for Constrainer. We can define another winning strategy $\bar{\sigma}$ that always takes sets from $B$: given a finite word $s$ of length $i$, we define $\bar{\sigma}(s)= f\big(\sigma(s),s_i\big)$. Since $\sigma$ was winning for Constrainer, by Remark <ref> also $\bar{\sigma}$ is winning.

Now we are ready to give a characterization of $\ndiff{n}{1}$ sets in terms of the game $\gameH$.

Let $X$ be a topological space and let $Y \subseteq X$. The following conditions are equivalent:

* $Y$ belongs to $\ndiff{n}{1}$.

* Constrainer wins the game $\gameHs(Y,n+1)$.

We have to prove both directions separately.

*Implication $1 \Rightarrow 2$. Suppose that $n$ is odd and let

\begin{equation}
\label{eq:form-of-Y}
Y = A_0 \cup (A_2 \setminus A_1) \cup  \cdots \cup (A_{n{-}1} \setminus A_{n{-}2}),
\end{equation}

where $A_0 \subseteq A_1 \subseteq A_2 \subseteq \cdots \subseteq A_{n-2} \subseteq A_{n-1}$ and every $A_i$ is open for $0 \leq i \leq n-1$. Then, a winning strategy for Constrainer in $\gameHs(Y,n)$ is to play $A_{n-1}$ as the first move, $A_{n-2}$ as the second move, and so on. Equation (<ref>) implies that this is a valid strategy of Constrainer. The $n$th move will be $A_0$, and since $A_0 \subseteq Y$, at that point Alternator loses at the $(n{+}1)$th round. The case of $n$ even is completely dual, in that case $A_0 \subseteq Y\complemento$.

*Implication $2 \Rightarrow 1$.

Suppose that $n$ is odd, the opposite case can be solved by an entirely dual argument. Our aim is to present $Y$ as in (<ref>). For $i=0,1,2,\ldots$ define sets

\begin{align*}
A_i &\eqdef \bigcup\big\{ U\mid \text{Constrainer wins $\gameHs_U(Y,i+1)$}\big\}&\text{for odd $i$}\\
A_i &\eqdef \bigcup\big\{ U\mid \text{Constrainer wins $\gameHs_U(Y\complemento,i+1)$}\big\}&\text{for even $i$}
\end{align*}

where the unions range over open sets $U\subseteq X$. Notice that if Constrainer wins $\gameHs_U(Y,i)$ then he also wins $\gameHs_U(Y\complemento,i+1)$ by the same strategy, just playing $U$ in the first round. Therefore, the family $(A_i)$ is increasing. By the definition, all the sets $A_i$ are open. Clearly, the assumption that Constrainer has a winning strategy in $\gameHs(Y,n+1)$ implies that $A_{n}$ is the whole space. Thus, it is enough to inductively prove the following claim.

For $i=0,1,\ldots$ the following holds

\begin{align*}
Y\cap A_i &= A_0\cup (A_2\setminus A_1) \cup\cdots\cup(A_{i-1}\setminus A_{i-2}) &\text{for odd $i$}\\
Y\complemento\cap A_i &= (A_1\setminus A_0)\cup (A_3\setminus A_2) \cup\cdots\cup(A_{i-1}\setminus A_{i-2}) &\text{for even $i$}
\end{align*}

Notice that by the definition $A_0\subseteq Y$ — whenever there exists $x\in U\cap Y\complemento$ then Alternator wins $\gameHs_U(Y\complemento,1)$ by playing $x$. Therefore, the above claim holds for $i=0$ as $Y\complemento\cap A_0=\emptyset$.

Assume that Claim <ref> holds for $i{-}1$ and consider the two cases for $i$.

*The case of odd $i$.
In that case we need to prove that $Y\cap A_i$ is of the form from (<ref>). Consider a point $x\in A_i$. First consider the case that $x\in A_{i-1}$. Then by the inductive assumption $x\in Y$ if and only if

\[x\notin (A_1\setminus A_0)\cup(A_3\setminus A_2)\cup\cdots\cup(A_{i-2}\setminus A_{i-3})\]

what is equivalent to the disjunction of $x\in (A_{i-1}\setminus A_{i-2})$ or

\[x\in A_0\cup (A_2\setminus A_1)\cup\cdots\cup(A_{i-3}\setminus A_{i-4}).\]

Thus, $x\in Y$ if and only if

\[x\in A_0\cup (A_2\setminus A_1)\cup\cdots\cup(A_{i-1}\setminus A_{i-2}).\]

Thus, the statement of Claim <ref> holds in that case.

Now assume that $x\notin A_{i-1}$. We will prove that in that case $x\notin Y$. Assume contrarily that $x\in Y$. Since $x\in A_i$, there exists an open set $U$ such that $x\in U \subseteq A_i$ and Constrainer wins $\gameHs_U(Y,i+1)$. Consider the first round of $\gameHs_U(Y,i+1)$ in which Alternator plays $x$ and a winning strategy of Constrainer replies with $V\ni x$. This means that Constrainer has a winning strategy in $\gameHs_V(Y\complemento,i)$ and therefore by the definition $x\in V\subseteq A_{i-1}$, a contradiction.

*The case of even $i$. This case is entirely dual: we take $x\in A_i$ and consider the case that $x\in A_{i-1}$. Then the following conditions are equivalent:

\begin{align*}
x&\notin Y\\
x&\notin A_0\cup (A_2\setminus A_1)\cup\cdots\cup(A_{i-2}\setminus A_{i-3})\\
x&\in (A_1\setminus A_0)\cup(A_3\setminus A_2)\cup\cdots\cup(A_{i-3}\setminus A_{i-4})\text{ or }x\in (A_{i-1}\setminus A_{i-2})\\
x&\in (A_1\setminus A_0)\cup(A_3\setminus A_2)\cup\cdots\cup(A_{i-1}\setminus A_{i-2})
\end{align*}

and therefore Claim <ref> holds in that case. If $x\notin A_{i-1}$ then we need to prove that $x\in Y$. Since $x\in A_i$, we know that $x\in U\subseteq A_i$ with Constrainer winning $\gameHs_U(Y\complemento, i+1)$ for some open $U$. Assume contrarily that $x\notin Y$ and as before we see a contradiction, as $x$ is a valid move of Alternator in $\gameHs_U(Y\complemento,i+1)$ and therefore $x\in A_{i-1}$.

The following conditions are equivalent for a set $Y$:

* $Y$ belongs to $\bigcup_{n \in \omega} \ndiff{n}{1}=\boolcomb{1}$.

* Constrainer wins the game $\gameHs(Y,n)$ for all but finitely many $n$.

It follows directly from Theorem <ref> and Fact <ref>.

Since the family of sets defined by prefixes $N_p$ for all finite prefixes $p$ is a basis of the topology on $\trees_A$, we obtain the following corollary for the case $X=\trees_A$.

Assume that $X=\trees_A$ is the space of all trees and $L\subseteq \trees_A$. Then, when considering strategies of Constrainer in $\gameHs(L,n)$ we can assume that each open set $U_i$ played by him is a basic open set, i.e. $U_{i+1}=N_p$ for a finite prefix $p$ of the currently played tree $t_i$. Then the condition that $U_{i+2}\subseteq U_{i+1}$ boils down to the assumption that $p_{i+2}\supseteq p_{i+1}$.

§.§ Decidability of finite levels of the Wadge hierarchy

In this short subsection we use the game $\gameH(L_1,\ldots , L_n)$ to show that, given a natural number $n$, it is decidable if a regular language $L$ is an $n$/̄difference of open sets (i.e. belongs to $\ndiff{n}{1}$). Recall that, without loss of generality (see Corollary <ref>) we can assume that Constrainer plays finite prefixes of the trees played by Alternator, and Alternator has to extend the finite prefixes played by Constrainer.

Consider the language

\[ L= \{ t\in\trees_A \mid \text{infinitely many letters $a$ appear in $t$}\}.\]

$L$ is regular and it is easy to check that Alternator wins the game $\gameHs(L,n)$ for every $n \in \omega$. This is because every finite prefix can be extended to a tree with finitely many $a$ or to a tree with infinitely many $a$. So $L$ is not a Boolean combination of open sets (it is easy to see, indeed, that $L$ is a $\bpi{2}$ set but it is not a $\bsigma{2}$ set).

Given regular tree languages $L_1, \ldots, L_n$, one can decide who wins the game $\gameH(L_1,\ldots , L_n)$. In particular, given $L$ and $n$, one can decide who wins $\gameHs(L,n)$.

We prove the statement for two regular languages $L_1, L_2$. It is easy to generalise it to $n$ regular languages. The sentences “Alternator wins the game $\gameH(L_1, L_2)$” and “Constrainer wins the game $\gameH(L_1,L_2)$” can be effectively formalized in Monadic Second/̄order Logic on the complete binary tree. For instance, the sentence for

\[\lq \lq \text{Alternator wins the game } \gameH(L_1, L_2)\text{''} \]

\[\text{there exists a~tree $t_1 \in L_1$ such that for any finite prefix $p$ of $t_1$} \]

\[\text{there exists a~tree $t_2 \in L_2$ that extends $p$}.\]

In a similar way we can write the sentence that says that Constrainer wins for $n>2$.

So we obtain:

It is decidable, given a regular tree language $L$ and $n\in\omega$, whether $L$ is an $n$/̄difference of open sets.

It directly follows from Theorem <ref> and Lemma <ref>.

Hence, since Wadge degrees with Wadge ranks below $\omega$ are formed by Boolean combinations of the levels of the difference hierarchy, we easily obtain:

Given a regular language $L$ and a Wadge degree ${[A]}_W$ with Wadge rank less than $\omega$, it is decidable if $L$ belongs to ${[A]}_W$.

§.§ The infinite variant of the game

We denote by $\gameHinfty(Y)$ the infinite variant of $\gameHs(Y,n)$: $\gameHinfty(Y)$ is the infinite duration game played the same way as $\gameHs(Y,n)$ but the winning condition for Alternator is that he has to survive for infinitely many turns. By $\gameHinfty_U(Y)$ we denote the relativised game.

The game $\gameHinfty(Y)$ is determined: every play where Constrainer wins is finite. Therefore, the winning condition for Constrainer is an open condition, while the winning condition for Alternator is a closed condition, both in the space[Since Alternator chooses points in $X$ and Constrainer chooses open sets in $\tau$, each round of the game can be represented as an element of $X\times\tau$. Thus, the winning condition of the game is a subset of ${\big(X\times \tau\big)}^\w$.] ${\big(X\times \tau\big)}^\w$, where the sets $X$ and $\tau$ are taken with the discrete topology. Hence, the game is determined by Gale–Stewart Theorem [20] (see also [27] for the more general result for Borel sets).

In the same fashion as in the case of the finite game, without loss of generality we can assume that Constrainer in his strategies uses only basic open sets, see Corollary <ref>.

The following fact follows directly from the definition of the two variants of the game.

If Alternator wins $\gameHinfty(Y)$ then he wins $\gameHs(Y,n)$ for any $n$.

The converse to Fact <ref> is not true, even for regular tree languages $L$.

This proposition follows a posteriori from Theorem <ref> and Proposition <ref>, using the fact that the involved games are determined and there exist sets in $\bdelta{2}\setminus \bc{\bsigma{1}}$. However, the proof provided here is supposed to provide an informative illustration of the considered games.

We have to exhibit a counterexample. To do that it is convenient to work with an alphabet with three different symbols, so let $A$ be the alphabet $\{a,b,c\}$.
For the sake of this example, assume that if $t_1, \ldots, t_n$ are trees, by $[t_1, \ldots, t_n]$ we denote the tree

[trnode] (r0) at (-3, 0) $a$;
[toC] (l0) at ($(r0) + (-0.6, -0.8)$) $t_1$;

[trnode] (r1) at ($(r0) + (+0.6, -0.8)$) $a$;
[toC] (l1) at ($(r1) + (-0.6, -0.8)$) $t_2$;

(r2) at ($(r1) + (+0.6, -0.8)$);

(r3) at ($(r2) + (+0.6*0.6, -0.8*0.6)$);

[trnode] (r4) at ($(r3) + (+0.6, -0.8)$) $a$;
[toC] (l4) at ($(r4) + (-0.6, -0.8)$) $t_n$;

[trnode] (r5) at ($(r4) + (+0.6, -0.8)$) $b$;

[tredge] (r0) – (l0);
[tredge] (r1) – (l1);
[tredge] (r4) – (l4);

[tredge] (r0) – (r1);
[tredge] (r1) – (r2);
[trdots] (r2) – (r3);
[tredge] (r3) – (r4);
[tredge] (r4) – (r5);

[tredge] (r5) edge[trlole] (r5);
[tredge] (r5) edge[trlore] (r5);

Now let $L$ be the language of all the trees of the form $[t_1, \ldots, t_n]$ where for every $i \in \{1,\ldots,n\}$ the tree $t_i$ is

* either a tree with every node labelled by $a$,

* or a tree that contains only finitely many letters different than $c$, i.e. a tree for which there exists a finite prefix $p$ of $t_i$ such that $t_i(u)=c$ for any node $u \notin p$.

If $t_i$ respects the first condition we say that $t_i$ is a first case tree, if it respects the second condition we say it is a second case tree.  We first prove that Alternator wins $\gameHs(L,n)$ for any $n$. Fix a natural number $n$, we provide a winning strategy for Alternator for the game $\gameHs(L,2n)$. We define the following sets of trees:

* For $i \in \{1,\ldots, n\}$ let $L_i$ be the set of trees $[t_1, \ldots, t_n]$ such that the trees $t_1, \ldots, t_{i-1}$ are second case trees and the trees $t_i, \ldots, t_n$ are first case trees. It is clear that $L_i \subseteq L$ for any $i$.

* We define $L'_i$ as $L_i$ except that the tree $t_i$ contains both $a$ and $b$ nodes, but no $c$ nodes. Obviously $L'_i$ is disjoint from $L$.

Every prefix of a tree in $L_i$ can be completed into a tree in $L'_i$ and every prefix of a tree in $L'_i$ can be completed into a tree in $L_{i+1}$. It follows that Alternator wins the game

\[ \gameH(L_1,L'_1, L_2, L'_2, \ldots, L_n, L'_n)\]

and therefore also Alternator wins $\gameHs(L,2n)$.

Now we move to a proof that Alternator loses $\gameHinfty(L)$. Consider the tree played by
Alternator in the first round. Since this tree belongs to $L$, it must be of the
form $[t_1, \ldots, t_n]$ with $t_1, \ldots, t_n$ either first case trees or second case trees. Let $p_1$ be a finite prefix of this tree which contains the node $\dR^n$. Constrainer uses a strategy, which preserves the following properties:

* All prefixes played by Constrainer extend the prefix $p_1$. Consequently, all the trees played by Alternator are of the form $[s_1, \ldots, s_n]$. Indeed, the prefix $p_1$ guarantees that the played trees $t$ satisfy $t(\dR^n)=b$ and $t(\dR^k)=a$ for $k<n$. Hence, all the modifications done by Alternator are relative to the trees $t_1, \ldots, t_n$ and  therefore for $k \in \{1, \ldots, n\}$ it is meaningful to talk about the $k$th coordinate of the tree played by Alternator in a round which refers to the tree $s_k$.

* Suppose that Alternator plays a tree $[s_1, \ldots, s_n]$ in some round $i$. Let $p_i$ be a finite prefix of this tree such that for every coordinate $k \in \{1, \ldots, n\}$ we have:

* If $s_k$ is a second case tree then $p_i$ contains a prefix of $s_k$ such that under that prefix every node is labelled by $c$.

* If $s_k$ contains some $b$ then $p_i$ contains some $b$ in the subtree $s_k$.

In the next round Constrainer chooses $p_i$. Consequently, if $i,j$ are rounds with $i < j$ and $k \in \{1, \ldots,n\}$ then

* If the $k$th coordinate of Alternator's tree in round $i$ is a second case tree then also the $k$th coordinate of Alternator's tree in round $j$ has to be a second case tree.

* If the $k$th coordinate of Alternator's tree in round $i$ contains a $b$ then also the $k$th coordinate of Alternator's tree in round $j$ contains a $b$.

So, in an odd/̄numbered round, Alternator's tree belongs to the language and therefore all the coordinates with a $b$ are second case trees. In an even/̄numbered round, Alternator's tree is outside the language. Therefore, when going from an odd/̄numbered round to the next even/̄numbered round, Alternator must change some coordinate from a first case tree without $b$ to a tree with $b$. It follows that the number coordinates with $b$ increases in each even/̄numbered round. Since this can happen at most $n$ times, Alternator must lose after at most $2n$ rounds.

The proof is complete.

Now we can give a non/̄effective characterisation of the class $\bdelta{2}$ for topological spaces that are completely metrizable (for the levels $\ndiff{n}{1}$ we gave a characterisation that holds in general for any topological space, but here we are forced to require complete metrizability).

Let $X$ be a completely metrizable topological space with a countable basis of the topology (i.e. $X$ is second/̄countable). The following conditions are equivalent for a subset $Y$ of $X$:

* Constrainer wins $\gameHinfty(Y)$.

* $Y \in \bdelta{2}(X)$.

The proof is very similar to the analysis of other games of this kind, for instance Banach–Mazur game, see <cit.>.

*Implication $1 \Rightarrow 2$.

Assume that Constrainer has a winning strategy $\sigma$ in $\gameHinfty(Y)$. By Remark <ref> we can assume that $\sigma$ plays only basic open sets.

Notice that $\sigma$ (seen as a tree) is well/̄founded because the strategy is winning and therefore it admits no infinite play. We will prove by induction on the structure of $\sigma$ that if $\langle U_0,x_1,U_1,\ldots,U_{i-1}\rangle $ is a position compatible with $\sigma$ then $Y\cap U_{i-1}\in\bdelta{2}$. Consider such a position $P=\langle U_0,x_1,U_1,\ldots,U_{i-1}\rangle$ and assume that the thesis holds for all the positions extending that one. If the position $P$ is instantly winning for Constrainer (i.e. Alternator cannot play a single round from $P$) then, depending on parity of $i$, either $U_{i-1}\subseteq Y\complemento$ or $U_{i-1}\subseteq Y$. In both cases the inductive thesis holds. Now assume that $P$ is not instantly winning for Constrainer. By the symmetry lets assume that $i$ is odd, i.e. Alternator is forced to play $x_i\in U_{i-1}\cap Y$. Let ${(B_x)}_{x\in U_{i-1}\cap Y}$ be the indexed family of basic open sets $B_x$ played by $\sigma$ as a response to Alternator playing $x$. By the inductive assumption we know that for each $x\in U_{i-1}\cap Y$ we have $Y\cap B_x\in\bdelta{2}$.

By the definition of the family $B_x$ we know that

\[Y\cap U_{i-1}=\bigcup_{x\in U_{i-1}\cap Y} \big(B_x\cap Y\big),\]

where the union is in fact countable since there is only countably many basic open sets in $X$. As every set taken in the union is $\bsigma{2}$ (in fact $\bdelta{2}$) we know that $Y\cap U_{i-1}$ is $\bsigma{2}$. Dually

\[Y\complemento\cap U_{i-1}=\left(U_{i-1}\setminus \bigcup_{x\in U_{i-1}\cap Y} B_x\right)\ \cup\ \bigcup_{x\in U_{i-1}\cap Y} \big(B_x\cap Y\complemento\big),\]

which again is a $\bsigma{2}$ presentation of $Y\complemento\cap U_{i-1}$.

Thus, the above induction implies that $Y\cap U_0=Y\cap X = Y$ is $\bdelta{2}$.

*Implication $2 \Rightarrow 1$.

We need to prove that if $Y \in \bdelta{2}$ then Constrainer wins $\gameHinfty(Y)$. Indeed, if $Y$ is in $\bdelta{2}$ we can write $Y$ and its complement as

\[ Y= \bigcap_{j \in \omega} A_j\quad \text{ and }\quad Y\complemento = \bigcap_{j \in \omega} B_j,\]

where all the sets $A_i$ and $B_i$ are open. Now we can describe a winning strategy for Constrainer in $\gameHinfty(Y)$. Suppose $i=1,2,\ldots$ is the round we are playing and $i$ is odd (resp. $i$ is even). Let $j=\lfloor \frac{i-1}{2} \rfloor$. Assume that $U_{i-1}$ is the open set that was played last ($U_0=X$) and let $x_i$ be the point played by Alternator in the current round. By the definition of the game, if $i$ is odd then $x_i\in Y$ and otherwise $x_i\in Y\complemento$. Let Constrainer play $U_i$ such that $\overline{U_i}\subseteq U_{i-1}$; $U_i\subseteq A_j$ (resp. $U_i\subseteq B_j$); and the diameter of $U_i$ is smaller than $2^{-i}$. Such a set exists because $x_i\in U_{i-1}\cap A_j$ (resp. $x_i\in U_{i-1}\cap B_j$).

Clearly it is a valid strategy of Constrainer. Consider an infinite play consistent with this strategy. Since $X$ is Polish and the sets $U_i$ are of decreasing diameter with $\overline{U_i}\subseteq U_{i-1}$, there must exists $x\in\bigcap_{n\in\w} U_i$. But by the construction of $U_i$, such $x$ must belong to both $\bigcap_{j\in\w}A_j=Y$ and $\bigcap_{j\in\w}B_j=Y\complemento$, a contradiction. Thus, each play consistent with the above strategy is finite and therefore winning for Constrainer.

Let $X$ be a completely metrizable topological space and $Y$ be a subset of $X$. Then $Y \in \bdelta{2} \setminus \boolcomb{1}$ if and only if Alternator wins $\gameHs(Y,n)$ for all $n$ but he loses $\gameHinfty(Y)$.

§ THE ALGEBRA ON TREES

Our next goal is decidability of the class $\bigcup_{n \in \omega} \ndiff{n}{1}=\boolcomb{1}$. Notice that Corollary <ref> gives us a semi/̄algorithm for deciding if a regular language is in $\bigcup_{n \in \omega} \ndiff{n}{1}$. Indeed, for $n = 1, 2, \ldots$ we can use Corollary <ref> to decide if $L\in\ndiff{n}{1}$. If for some $n$ this is the case then $L\in\bigcup_{n \in \omega} \ndiff{n}{1}$ and the algorithm terminates. Otherwise, the algorithm does not terminate. Section <ref> provides an alternative algebraic algorithm that always terminates and solves the above decision problem.

The algebraic approach we define in this section is based on the so/̄called Myhill–Nerode equivalence that allows to distinguish trees based on their behaviour when put into certain contexts.

A multicontext over an alphabet $A$ is a partial tree $t$ over $A\sqcup \{\hole\}$ where $\hole\notin A$ such that: $t$ does not contain any unary nodes and a node of $t$ is a leaf if and only if it is labelled $\hole$. A port of a multicontext $C$ is any node of $t$ that is labelled $\hole$ (i.e. any leaf of $t$).

The number of ports is called the arity of the multicontext. A priori a multicontext may have infinitely many ports and in that case the arity is $\infty$. A multicontext with exactly one port is called a context. Given a multicontext $C$ and a valuation $\eta$ which maps ports of $C$ to trees in $\trees_A$, we write $C[\eta]$ for the tree obtained by replacing each port $u$ by the tree $\eta(u)$. The tree $C[\eta]$ is said to extend the multicontext $C$. If $L$ is a set of trees and $C$ is a multicontext then by $C[L]$ we denote the set of trees obtained by plugging trees of $L$ in the ports of $C$ in all the possible ways. The set of all trees extending a multicontext $C$ is denoted by $C[\ast]$. If $C$ is a multicontext, possibly with infinitely many ports, and $t$ is a tree, we denote by $C[t]$ the tree obtained by putting $t$ in every port of $C$.

The multicontext $C_0$ consists of only one node — the root. It is called the trivial context and denoted $\hole$. $C_1$ is a tree, it has no ports, and $C_1[\ast]$ is $\{C_1\}$. The multicontext $C_2$ is a context and if we complete $C_2$ with a tree we obtain a tree where the root label is $a$ and the left subtree of the root is labelled with only letters $b$. Finally, $C_3$ is a finite multicontext and $C_3[\ast] = \{ t \mid t(\epsilon)=a\}$.

[trport] (z0) at (-6, 0) ;
[toC] at ($(z0)+(0, 1.0)$) $C_0$;

[trnode] (z1) at (-3, 0) $a$;
[toC] at ($(z1)+(0, 1.0)$) $C_1$;
[trnode] (l1) at ($(z1) + (-0.6, -0.8)$) $b$;
[trnode] (r1) at ($(z1) + (+0.6, -0.8)$) $a$;

[tredge] (z1) – (l1);
[tredge] (z1) – (r1);
[tredge] (l1) edge[trlole] (l1);
[tredge] (l1) edge[trlore] (l1);
[tredge] (r1) edge[trlole] (r1);
[tredge] (r1) edge[trlore] (r1);

[trnode] (z2) at (-0, 0) $a$;
[toC] at ($(z2)+(0, 1.0)$) $C_2$;
[trnode] (l2) at ($(z2) + (-0.6, -0.8)$) $b$;
[trport] (r2) at ($(z2) + (+0.6, -0.8)$) ;

[tredge] (z2) – (l2);
[tredge] (z2) – (r2);
[tredge] (l2) edge[trlole] (l2);
[tredge] (l2) edge[trlore] (l2);

[trnode] (z3) at (+3, 0) $a$;
[toC] at ($(z3)+(0, 1.0)$) $C_3$;
[trport] (l3) at ($(z3) + (-0.6, -0.8)$) ;
[trport] (r3) at ($(z3) + (+0.6, -0.8)$) ;

[tredge] (z3) – (l3);
[tredge] (z3) – (r3);

Now we focus on contexts, i.e. multicontexts with exactly one port. We write $\Context$ for the set of all non/̄trivial contexts over $A$. Given two contexts $C,D$ we write $C\cdot D$ for the context obtained by replacing the port of $C$ with $D$. Moreover, if $C\neq\hole$ (i.e. $C$ is non/̄trivial) then we write $C^\infty$ for the infinite tree

\[ C \cdot C \cdot C \cdot C \cdots\]

Notice that the above definition does not construct a tree for $C=\hole$ (the trivial context). That is why we restrict the set of contexts $\Context$ to only non/̄trivial ones.

It is easy to verify that $\cdot$ is associative, therefore $\big(\Context\sqcup\{\hole\},\cdot\big)$ is an infinite monoid, with ${\cdot}$ associative and the trivial context $\hole$ as the neutral element.

Now we define the two Myhill–Nerode equivalence relations: one for trees and one for contexts. These equivalence relations depend on a fixed language $L\subseteq \trees_A$.

In the Myhill–Nerode equivalence for trees, we say that two trees $t$ and $t'$ are $L$/̄equivalent (denoted $t\Teq_L t'$) if

\[ C[t] \in L \Longleftrightarrow C[t'] \in L\quad \text{ for every multicontext $C$.}\]

Notice that because of the duality between $L$ and the complement $L^\cp$ in the above definition, we know that the equivalence relations $\Teq_L$ and $\Teq_{L^\cp}$ coincide. Moreover, since $\hole$ (i.e. the trivial context) is a multicontext we know that if $t\in L$ and $t'\in L^\cp$ then $t\not\Teq_L t'$.

The above remark says that the equivalence relation $\Teq_L$ is always able to distinguish trees from $L$ from those not in $L$. In the following example these are the only two classes of $\Teq_L$, i.e. $\Teq_L$ is not able to distinguish anything else.

Consider the language $L = \{ t \in \trees_A \mid t(\epsilon) = a\}$. In this case we have just two equivalence classes that are $L$ and the complement $L\complemento$. The multicontext that establishes if a tree belongs to $L$ or $L\complemento$ is the trivial context $\hole$.

To give a similar definition for contexts, we use a variant of multicontexts where the ports can be substituted by contexts and not trees.

A context environment over an alphabet $A$ is a partial tree labelled by $A\sqcup\{\hole\}$ such that: $t$ has no leaves and a node of $t$ is unary if and only if it is labelled $\hole$. A port of a context environment is any node of $t$ that is labelled $\hole$ (i.e. any unary node of $t$).

Given a context environment $E$ and a non/̄trivial context $C$, we write $E[C]$ for the tree obtained by substituting $C$ for every port of $E$ in the following way. For each port $v$ of $E$ we first plug a copy of $C$ into that port and then plug the subtree of $E$ below that port into the port of $C$. Notice that there may be more than one occurrence of $\hole$ on a branch of $E$ and the above plugging needs to be performed in each of them, see the left/̄most branch of $E[C]$ in Example <ref>. This guarantees that $E[C]$ is a tree — it does not contain any port of $E$ nor any of the copies of the port of $C$.

The assumption that $C$ is non/̄trivial is important in the above construction, because if $E$ is a unary tree labelled everywhere $\hole$ (i.e. a $\hole$/̄labelled infinite path) and $C=\hole$ is the trivial context, then $E[C]$ (if defined at all) does not contain any node.

In the following figure, $C$ is a context, $E$ is a context environment, and $E[C]$ is a tree.

[trnode, szary] (z1) at (-10, 0) $c$;
[toC] at ($(z1)+(0, 1.0)$) $C$;
[trnode, szary] (l1) at ($(z1) + (+0.6, -\vstr)$) $d$;
[trport] (r1) at ($(z1) + (-0.6, -\vstr)$) ;

[tredge] (z1) – (l1);
[tredge] (z1) – (r1);

[trnode] (z2) at (-6, 0) $e$;
[toC] at ($(z2)+(0, 1.0)$) $E$;
[trport] (l2) at ($(z2) + (-1.0, -\vstr)$) ;
[trport] (r2) at ($(z2) + (+1.0, -\vstr)$) ;

[tredge] (z2) – (l2);
[tredge] (z2) – (r2);

[trnode] (ll2) at ($(l2) + (-0.0, -\vstr)$) $f$;
[trnode] (rr2) at ($(r2) + (+0.0, -\vstr)$) $g$;

[tredge] (l2) – (ll2);
[tredge] (r2) – (rr2);

[trport] (lll3) at ($(ll2) + (-0.6, -\vstr)$) ;
[trnode] (llr3) at ($(ll2) + (+0.6, -\vstr)$) $h$;

[trnode] (llr4) at ($(lll3) + (+0.0, -\vstr)$) $i$;

[tredge] (ll2) – (lll3);
[tredge] (ll2) – (llr3);
[tredge] (lll3) – (llr4);

[trnode] (z3) at (0.5, 0) $e$;
[toC] at ($(z3)+(0, 1.0)$) $E[C]$;
[trnode, szary] (l3) at ($(z3) + (-1.4, -\vstr)$) $c$;
[trnode, szary] (r3) at ($(z3) + (+1.4, -\vstr)$) $c$;
[trnode, szary] (lr3) at ($(l3) + (+0.9, -\vstr)$) $d$;
[trnode, szary] (rr3) at ($(r3) + (+0.7, -\vstr)$) $d$;
[trnode] (ll3) at ($(l3) + (-0.9, -\vstr)$) $f$;
[trnode] (rl3) at ($(r3) + (-0.7, -\vstr)$) $g$;

[trnode] (llr4) at ($(ll3) + (+0.8, -\vstr)$) $h$;
[trnode, szary] (lll4) at ($(ll3) + (-0.8, -\vstr)$) $c$;

[trnode, szary] (lllr5) at ($(lll4) + (+0.6, -\vstr)$) $d$;
[trnode] (llll5) at ($(lll4) + (-0.6, -\vstr)$) $i$;

[tredge] (z3) – (l3);
[tredge] (z3) – (r3);
[tredge] (l3) – (ll3);
[tredge] (l3) – (lr3);
[tredge] (r3) – (rl3);
[tredge] (r3) – (rr3);
[tredge] (ll3) – (lll4);
[tredge] (ll3) – (llr4);
[tredge] (lll4) – (llll5);
[tredge] (lll4) – (lllr5);

We define two non/̄trivial contexts $C$ and $C'$ to be $L$/̄equivalent (denoted $C\Ceq_L C'$) if

\[ E[C] \in L \Longleftrightarrow E[C'] \in L\quad \text{ for every context environment $E$}.\]

§.§ The syntactic tree algebra (HL,VL)

We denote by $H_L$ the set of the equivalence classes of trees with respect to $L$, the elements of $H_L$ are called tree types. Similarly we denote by $V_L$ the set of the equivalence classes of non/̄trivial contexts with respect to $L$, the elements of $V_L$ are called context types. By $\one_L$ we denote an additional type corresponding to the trivial context $\hole$. Since $V_L$ denotes types of the non/̄trivial contexts, in general $\one_L\notin V_L$.

We will now prove a number of results, showing that the sets $H_L$ and $V_L$ bear certain algebraic structure. We start with a simple fact following directly from the definition of $L$/̄equivalence.

For every multicontext $D$ and context environment $E$, the following two operations preserve the $L$/̄equivalence:

* the operation $t \rightarrow D[t]$, i.e. if $t\Teq_L t'$ then $D[t]\Teq_L D[t']$,

* the operation $C \rightarrow E[C]$, i.e. if $C\Ceq_L C'$ then $E[C]\Teq_L E[C']$.

The following corollary follows directly from Fact <ref>.

Given a multicontext $D$, a context environment $E$, and elements $h\in H_L$, $v\in V_L$, the sets

\begin{align*}
D[h] &\eqdef \{D[t]\mid t\in h\}\subseteq \trees_A,\\
E[v] &\eqdef \{E[C]\mid C\in v\}\subseteq \trees_A.
\end{align*}

are $L$/̄equivalence classes, i.e. elements of $H_L$.

Thus, each multicontext $D$ (resp. context environment $E$) induces an operation $H_L\to H_L$ (resp. $V_L\to H_L$).

As expressed by the next lemma, the following natural operations on contexts and trees respect the $L$/̄equivalence.

The following operations respect $L$/̄equivalence.

* The composition of contexts $(C_1,C_2) \rightarrow C_1 \cdot C_2$.

* Substituting a tree in the port of a context $(C,t) \rightarrow C[t]$.

* Infinite iteration of a non/̄trivial context $C \rightarrow C^\infty$.

* For every symbol $c \in A$, the operations $t \mapsto c(t,\hole)$ and $t \mapsto c(\hole, t)$, that produce new contexts with roots labelled $c$, and $t$ plugged as the left or the right subtree under the root, respectively.

We prove all the items.

*Item 1 Let $C_1$, $C_2$, $D_1$, $D_2$ be contexts such that $C_1$ is $L$/̄equivalent with $D_1$ and $C_2$ is $L$/̄equivalent with $D_2$. Let $E$ be some context environment, we prove that

\[E[C_1\cdot C_2] \in L \Leftrightarrow E[D_1\cdot D_2]  \in L.\]

We construct from $E$, $C_1$ and $E$, $D_2$ respectively two new context environments
$E_C$ and $E_D$ such that

\[E_C[C_2] = E[C_1\cdot C_2] \text{ and } E_D[D_1] =E[D_1\cdot D_2].\]

By the symmetry, lets focus on $E_C$. This context environment is obtained from $E$ by inserting into each occurrence of $\hole$ a whole copy of $C_1$ (including its own $\hole$). Thus, the overall number of holes of $E_C$ and $E$ is the same and the above equality follows.

Using the $L$/̄equivalence, we have:

\[
\begin{array}{lll}
E_D[C_1] \in L & \Leftrightarrow & E_D[D_1] \in L \\
E_C[C_2] \in L & \Leftrightarrow & E_C[D_2] \in L
\end{array}
\]

Note that by the definition of $E_C$ and $E_D$ we have $E_C[D_2]=E_D[C_1]$. It follows that

\[E[C_1\cdot C_2] \in L \Leftrightarrow E_C[C_2] \in L \Leftrightarrow E_C[D_2] \in L \Leftrightarrow E_D[C_1] \in L \Leftrightarrow E_D[D_1] \in L.\]

Therefore, $C_1\cdot C_2$ and $D_1\cdot D_2$ are $L$/̄equivalent.

*Item 2 Let $C$, $C'$ be $L$/̄equivalent contexts and $t$, $t'$ be $L$/̄equivalent trees. We want to prove that $C[t]$ and $C'[t']$ are two $L$/̄equivalent trees. Let $D$ be a generic multicontext. We prove that

\[D[C[t]] \in L \Leftrightarrow D[C'[t']]  \in L.\]

Let $D'$ be a multicontext such that $D'[t]=D[C[t]]$ and $E$ a context environment such that
$E[C'] = D[C'[t']]$. Using the $L$/̄equivalence we have:

\[
\begin{array}{lll}
D'[t] \in L & \Leftrightarrow & D'[t'] \in L, \\
E [C] \in L & \Leftrightarrow & E[C'] \in L.
\end{array}
\]

By the definition of $E$ and $D'$ we have $D'[t']=E[C]$. It follows that

\[D[C[t]] \in L \Leftrightarrow
D'[t] \in L \Leftrightarrow
D'[t'] \in L \Leftrightarrow
E[C] \in L \Leftrightarrow
E[C'] \in L \Leftrightarrow
D[C'[t']] \in L.\]

Therefore, $C[t]$ and $C'[t']$ are $L$/̄equivalent.

*Item 3 Let $C$, $C'$ be $L$/̄equivalent non/̄trivial contexts. We want to prove that $C^\infty$ and $C'^\infty$ are two $L$/̄equivalent trees. Let $D$ be some
multicontext, we prove that

\[ D[C^\infty] \in L \Leftrightarrow D[C'^\infty] \in L.\]

Consider a context environment $E$ constructed from $D$ by replacing each port of $D$ with an infinite chain of ports. Using $L$/̄equivalence of $C$ and $C'$ we get:

\[
E[C] \in L \Leftrightarrow E[C'] \in L
\]

By definition of $E$ we have $E[C]=D[C^\infty]$ and $E[C']=D[C'^\infty]$. It follows that

\[D[C^\infty] \in L \Leftrightarrow D[C'^\infty] \in L.\]

Therefore, $C^\infty$ and $C'^\infty$ are $L$/̄equivalent.

*Item 4 We only do the proof for $t \mapsto c(t,\hole)$, the other operations is handled symmetrically. Let $t,t'$ be $L$/̄equivalent trees. Let $E$ be some context environment, we prove that

\[E[c(t,\hole)] \in L \Leftrightarrow E[c(t',\hole)] \in L.\]

By inserting $c$ into the ports of $E$ we construct a multicontext $C$ such that for all trees $s$,
$C[s]=E[c(s,\hole)]$. Using $L$/̄equivalence of $t$ and $t'$ we get:

\[
C[t] \in L \Leftrightarrow C[t'] \in L
\]

Therefore, $c(t,\hole)$ and $c(t',\hole)$ are $L$/̄equivalent.

The above operations on $\trees_A$ and $\Context$ induce the following algebraic structure on $(H_L, V_L)$:

* composition of context types $V_L\ni u,v\longmapsto u\cdot v\in V_L$,

* action of $V_L$ on $H_L$ i.e. $V_L\times H_L\ni (u,h)\longmapsto u\cdot h\in H_L$,

* infinite composition $V_L\ni u \longmapsto u^\infty \in H_L$,

* creation of contexts $H_L\ni h \longmapsto c(\hole, h), c(h,\hole)\in V_L$ for $c\in A$.

Moreover, $(V_L,{\cdot})$ is a semigroup acting over $H_L$ via $\cdot$, $\big(V_L\sqcup\{\one_L\},\cdot\big)$ is a monoid, and $(H_L,V_L)$ satisfy the axioms of a Wilke algebra [45].

A pair of sets $(H,V)$, equipped with the operations as in Corollaries <ref> and <ref>, is called a tree algebra. Once restricted to the operations from Corollary <ref>, it becomes a thin algebra[The name comes from the theory of thin trees, sometimes called scattered trees, see [24].]. An advantage of a thin algebra is that (given that $H$ and $V$ are finite) it can be represented effectively on a computer by giving the sets and the multiplication tables for the five involved operations. Because of the simplicity of the considered classes of topological complexity, the operations involved in our characterisations involve only operations of thin algebras, see Equations (<ref>) and (<ref>).

Notice that the pair $(\trees_A,\Context)$ with the actual operations of composition of trees and contexts is in fact a tree algebra, we call it the free tree algebra.

The syntactic morphism of a language $L$, denoted by $\alpha_L$, is the two/̄sorted function

\[ \fun{\alpha_L}{(\trees_A,\Context)}{(H_L,V_L)},\]

that maps a tree $t\in\trees_A$ into its ${\Teq_L}$/̄equivalence class $\alpha_L(t)\in H_L$ and a context $C\in\Context$ into its ${\Ceq_L}$/̄equivalence class $\alpha_L(C)\in V_L$.

The next fact is considered folklore, see for instance <cit.>. The usual notation for the number $\monoid$ is $\w$, however it is better not to use that symbol in this paper to avoid confusion with the infinite repetition.

Given any finite semigroup $V$, there is a number $\monoid_V$ (denoted just $\monoid$ if $V$ is known from the context) such that for each element $v$ of $V$ the element $v^\monoid$ is an idempotent, i.e. $v^\monoid = v^\monoid \cdot v^\monoid$.

§.§ Congruences

To be able to compute the syntactic tree algebra $(H_L,V_L)$ we will need to start with its approximation. This notion is formalised as follows.

Consider a two/̄sorted function $\fun{\alpha}{(\trees_A,\Context)}{(H,V)}$ that is surjective onto a pair of sets $(H,V)$. We say that it is a congruence if the following two conditions hold:

* for every multicontext $D$ and every pair of trees $t,t'\in\trees_A$ such that $\alpha(t)=\alpha(t')$ we have

\[\alpha\big(D[t]\big)=\alpha\big(D[t']\big),\]

* for every context environment $E$ and every pair of contexts $C,C'\in\Context$ such that $\alpha(C)=\alpha(C')$ we have

\[\alpha\big(E[C]\big)=\alpha\big(E[C']\big).\]

We say that $\alpha$ recognises a set of trees $L\subseteq\trees_A$ if $L=\alpha^{-1}(S)$ for some subset $S\subseteq H$.

If $\alpha$ is a congruence that recognises $L$ then its kernel is finer than the $L$/̄equivalence in the sense that for each pair of trees $t$, $t'$ and pair of contexts $C$, $C'$ we have:

\[\alpha(t)=\alpha(t') \Rightarrow t\Teq_L t'\quad\text{ and }\quad \alpha(C)=\alpha(C')\Rightarrow C\Ceq_L C'.\]

Assume that $S\subseteq H$ is such that $\alpha^{-1}(S)=L$. Consider the first claim and take two trees $t,t'\in\trees_A$ such that $\alpha(t)=\alpha(t')$. We need to prove that $t\Teq_L t'$. Take a multicontext $D$ and assume by the symmetry that $D[t]\in L$, i.e. $\alpha\big(D[t]\big)\in S$. However, the assumption that $\alpha$ is a congruence implies that $\alpha\big(D[t']\big)=\alpha\big(D[t]\big)$ and therefore $D[t']\in \alpha^{-1}(S)=L$.

Corollary <ref> implies that the syntactic morphism $\fun{\alpha_L}{(\trees_A,\Context)}{(H_L,V_L)}$ is a congruence. Lemma <ref> implies that $\alpha_L$ is a homomorphism of thin algebras, i.e. it commutes with the operations of these algebras — for instance for the operation $v\cdot v'$ one needs to observe that for every two contexts $C,C'\in\Context$ we have

\[\alpha_L(C)\cdot \alpha_L(C') = \alpha_L\big(C\cdot C'\big).\]

Additionally, Remark <ref> implies that $\alpha_L$ recognises $L$.

§.§ Computing (HL,VL)

We will now prove that the syntactic algebras can be constructed effectively, as stated by the following proposition.

If $L$ is a regular language then both $H_L$ and $V_L$ are finite. Moreover, given a parity non/̄deterministic automaton $\Aa$ recognising $L$, one can compute in the syntactic algebra $(H_L,V_L)$ for $L$, together with the structure of thin algebra on $(H_L,V_L)$. Additionally, both $H_L$ and $V_L$ have at most exponentially many elements in the number of states of $\Aa$.

The following remark shows that finiteness of $H_L$ and $V_L$ is not sufficient for regularity (the remark is motivated by Running Example 2 in [7]).

Both $H_L$ and $V_L$ are finite for any language defined in (see [5]).

The rest of this subsection is devoted to a proof of Proposition <ref>. We follow implicitly the approach from [7], see <cit.> in the full version of the paper. A very similar construction is also given in <cit.> or [23].

The proof is divided into two stages. The first stage shows how to construct some congruence $\fun{\alpha}{(\trees_A,\Context)}{(H,V)}$ recognising $L$, such that the sets $H$ and $V$ are at most exponential in the number of states of $\Aa$ — a non/̄deterministic automaton recognising $L$. The second stage merges certain elements of that congruence to obtain the syntactic algebra $(H_L,V_L)$.

*The first stage — a congruence $\alpha$ We assume the notions of parity automata over infinite trees as in [41]: such an automaton is a tuple $\Aa=\langle A, Q, q_\init, \delta,\Omega\rangle$, where $A$ is an alphabet, $Q$ is a set of states, $q_\init\in Q$ is an initial state, $\delta\subseteq Q\times A \times Q^2$ is a transition relation and $\fun{\Omega}{Q}{\{i,\ldots,j\}}$ is a priority assignment. We use the standard concepts of an accepting run of a given automaton over a given tree.

Define a two/̄sorted function $\fun{\alpha}{(\trees_A,\Context)}{\Big(2^Q,2^{Q\times\{i,\ldots,j\}\times Q}\Big)}$ as follows:

\begin{align*}
\alpha(t) &\eqdef \big\{q\in Q\mid \text{$\Aa$ has an accepting run over $t$ from $q$}\big\},\\
\alpha(C) &\eqdef \big\{(q,\ell,q')\in Q\times\{i,\ldots,j\}\times Q\mid\\
&\qquad\qquad\text{$\Aa$ has an accepting run over $C$ that:}\\
&\qquad\qquad\qquad \text{starts from $q$ in the root of $C$,}\\
&\qquad\qquad\qquad \text{reaches $q'$ in the port of $C$,}\\
&\qquad\qquad\qquad \text{and the maximal priority seen in that run}\\
&\qquad\qquad\qquad\qquad \text{on the path to from the root to the port equals $\ell$}\big\}.\\
\end{align*}

Let $(H,V)$ be the range of $\alpha$. Intuitively, the value $\alpha(t)$ says from which states the automaton $\Aa$ can accept a given tree. In particular, $t\in L$ if and only if $q_\init\in\alpha(t)$ (thus, $\alpha$ recognises $L$). Similarly, the value $\alpha(C)$ for a context $C$ contains information about the relation between the states $\Aa$ can have in the root and in the port of $C$. However, as our algebra needs to deal with the operation $C^\infty$, we additionally need to know what is the maximal priority on the considered path, to make sure that it satisfies the parity condition once repeated infinitely many times.

$\alpha$ is a congruence.

We start with the first bullet of the definition (the second bullet speaking about contexts is analogous). Consider two trees $t,t'\in \trees_A$ such that $\alpha(t)=\alpha(t')=h\in H$ and let $D$ be a multicontext. Our aim is to prove that $\alpha\big(D[t]\big)=\alpha\big(D[t']\big)$. Assume by the symmetry that $q\in \alpha\big(D[t]\big)$, i.e. the tree $D[t]$ can be accepted from a state $q\in Q$. We need to prove that $q\in \alpha\big(D[t']\big)$ (the symmetric case is analogous). There exists a run of $\Aa$ over $D[t]$ that is accepting and starts from the state $q$ in the root of $D[t]$. By the assumption that $\alpha(t)=\alpha(t')$ we can construct a new run of $\Aa$ over $D[t']$ that is also accepting and starts from $q$, it is enough to replace the runs over $t$ by the respective runs over $t'$, below each of the ports of $D$.

We will now define explicitly the operations of thin algebra on $(H,V)$, for $h\in H_{\Aa}$, $v,v'\in V_{\Aa}$, and $c\in A$:

\begin{align*}
v\cdot v' &\eqdef \{(q,\max(\ell,\ell'), q'')\mid (q,\ell,q')\in v, (q',\ell',q'')\in v'\},\\
v\cdot h &\eqdef \{q\in Q\mid (q,\ell,q')\in v, q' \in h\},\\
v^\infty &\eqdef {(v^\monoid)}^\infty &\text{see Fact~\ref{fact_monoid},}\\
e^\infty &\eqdef \{q\in Q\mid (q,\ell,q')\in e, (q', 2\ell',q')\in e\}&\text{for $e\in V$ idempotent,}\\
c(\hole,h) &\eqdef \{(q,\Omega(q), q_{\dL})\mid (q,c,q_\dL,q_\dR)\in \delta, q_\dR\in h\},\\
c(h,\hole) &\eqdef \{(q,\Omega(q), q_{\dR})\mid (q,c,q_\dL,q_\dR)\in \delta, q_\dL\in h\}.
\end{align*}

It is relatively easy to check that the above operations are compatible with $\alpha$, i.e. $\alpha$ is a homomorphism of thin algebras. Thus, we have constructed a congruence $\fun{\alpha}{(\trees_A,\Context)}{(H,V)}$ that recognises $L$ and additionally we have given explicitly a structure of thin algebra on $(H,V)$.

*The second stage — a quotient of $(H,V)$.
We now provide a sketch of the second stage of the construction: computing the equivalence relation $\approx$ on $(H,V)$ defined as:

\begin{equation}
t\Teq_L t' \Leftrightarrow \alpha(t) \approx \alpha(t')\quad\text{ and }\quad C\Ceq_L C' \Leftrightarrow \alpha(C) \approx \alpha(C').
\label{eq:def-of-approx}
\end{equation}

First notice that this is a correct definition that does not depend on the choice of witnesses because of Remark <ref>.

For the sake of simplicity we will focus on the case of trees, i.e. we need to compute in if $h\approx h'$. However, Equation (<ref>) says that $h\not\approx h'$ if and only if there exists a multicontext $D$ such that $D[h] \in L \Leftrightarrow D[h']\notin L$ (the question whether $D[h]\in L$ is well/̄posed because $\alpha$ is a congruence recognising $L$).

This goal is achieved by constructing a non/̄deterministic parity tree automaton $\Cc_{h}$ of size polynomial in $\Aa$, that recognises the language of those multicontexts $D$ such that $D[h] \in L$. The automaton $\Cc_h$ non/̄deterministically guesses an accepting run of $\Aa$ over $D[t]$ for some hypothetical tree $t$. When it reaches a port of $D$, it verifies if the current state $q$ of $\Aa$ belongs to $h$. Once these automata are constructed, the question whether $h\approx h'$ boils down to checking if $\lang(\Cc_h)=\lang(\Cc_{h'})$, which can be done in .

Now, that the equivalence relation $\approx$ is computed, it is enough to divide $(H,V)$ by it. Because of (<ref>), there is a bijection between the quotient $(H,V)/\approx$ and the syntactic algebra $(H_L,V_L)$. Moreover, since both $\alpha$ and $\alpha_L$ are homomorphisms of thin algebras, the thin algebra operations in $(H,V)$ must preserve $\approx$. This means that we can obtain the structure of a thin algebra on $(H,V)/\approx$ that corresponds to the thin algebra structure of $(H_L, V_L)$. This concludes the proof of Proposition <ref>.

§.§ Quotients

Similarly as in the case of finite words, the syntactic algebra induces a natural notion of a quotient of a language: given a multicontext $D$ with $n$ holes and a language $K$ of trees, by $D^{-1}(K)$ we denote the set of tuples $(t_1,\ldots,t_n)$ such that the valuation $\eta$ mapping the $i$th port of $D$ into $t_i$ satisfies

\[D[\eta]\in K.\]

Notice that if $D$ is a context then in fact $D^{-1}(K)$ is a set of $1$/̄tuples of trees, which we identify with trees, i.e. $D^{-1}(K)\subseteq \trees_A$.

If $L$ is a language recognised by a morphism $\alpha_L$ then the fact whether $D[t]\in L$ depends only on $\alpha_L(D)\in V_L\sqcup\{\one_L\}$ and $\alpha_L(t)\in H_L$. Therefore, it makes sense to write $v^{-1}(L)$ for $v\in V_L\sqcup\{\one_L\}$. Also in that case $v^{-1}(L)$ is a language recognised by the morphism $\alpha_L$. Directly from the definition we get that

\begin{equation}%
\label{eq:quot-comp}
\end{equation}

§.§ The game on types

Now we want to extend the definition of the game $\gameH$ to sets of contexts. Recall that contexts are defined as a special case of partial trees, with an additional port label that appears in exactly one leaf. Notice that if $p$ is a finite partial context (i.e. $p$ has exactly one leaf labelled $\hole$) then every context in the basic open set $N_p$ must have the same port as $p$ — in such a case we say that $p$ fixes the port. Also, if $U$ is an open set of contexts and $C\in U$ then there exists a sufficiently big prefix $p\subset C$ such that $C\in N_p\subseteq U$ and $p$ fixes the port. Thus, without loss of generality we can assume that we consider only those basic open sets $N_p$ where $p$ does fix the port. This means that every two contexts $C,C'\in N_p$ must have the same position of the port.

This yields the definition of a game $\gameV(K_1,\ldots,K_n)$ for a sequence $K_1,\ldots ,K_n$ of context languages (i.e. subsets of $\Context\sqcup\{\hole\}$), which is played by Alternator and Constrainer. The game is played in $n$ rounds. Round $i=1$ is special: Alternator chooses a context $C_1 \in K_1$. Let $u$ be the port of the context $C_1$. This port will stay fixed for the rest of the game; all contexts produced by Alternator
will have their port in the node $u$. Next, Constrainer chooses a finite prefix $D_1$ of $C_1$, which has one of its leaves in the node $u$ (i.e. fixes the port).

A subsequent round $i \in \{2,\ldots,n\}$ is played as follows. Let $D_{i-1}$ be the finite partial tree over $A\sqcup\{\hole\}$ chosen by Constrainer in the previous round with a leaf in the node $u$.

* Alternator provides a context $C_i$, which extends $D_{i-1}$, belongs to $K_i$, and has its port in the node $u$. If there is no such context, the game is interrupted and Constrainer wins immediately.

* Constrainer chooses a finite prefix $D_i$ of $C_i$ and which has a leaf in the node $u$.

If Alternator manages to survive $n$ rounds then he wins. Recall that by the definition of the syntactic morphism, a tree type $h \in H_L$ is actually equal to the set of trees $\alpha_L^{-1}(h)$, similarly for a context type $v\in V_L$. Therefore, it makes sense to talk about the games $\gameH(h_1, \ldots, h_n)$, and $\gameV(v_1,\ldots,v_n)$ for sequences of types. Using these games we define the following sets of sequences of types:

We define two sets:

\begin{align*}
\gameH_L&=\{ (h_1, \ldots, h_n) \in {(H_L)}^\ast \mid \text{ Alternator wins $\gameH(h_1, \ldots, h_n)\}$},\\
\gameV_L&= \{ (v_1, \ldots, v_n) \in {(V_L)}^\ast \mid \text{ Alternator wins $\gameV(v_1, \ldots, v_n)\}$}.
\end{align*}

A comment on notation is in order here. The sets $\gameH_L$ and $\gameV_L$ contain words, over alphabets $H_L$ and $V_L$, respectively. Usually when dealing with words, one omits the brackets and commas and writes $abc$ instead of $(a, b, c)$. When the alphabet is $V_L$ this leads to ambiguity, since the expression $vwu$ can be interpreted as a word with a single letter obtained by multiplying the three context types $v$, $w$, and $u$, or a three/̄letter word over the alphabet $V_L$. These two interpretations should not be confused, so we write $(v_1, \ldots , v_n)$ for $n$/̄letter words over the alphabet $V_L$. For the sake of uniformity, we also write $(h_1, \ldots, h_n)$ for $n$/̄letter words over the alphabet $H_L$, although there is no risk of ambiguity here.

It turns out that the sets of words $\gameH_L$ and $\gameV_L$ have specific structure. We say that a word $u$ is a subword of $w$ if $u$ can be obtained from $w$ by removing some letters.

Both sets $\gameH_L$ and $\gameV_L$ are closed under removing letters, i.e. if $u$ is a subword of $w$ and $w\in\gameH_L$ then also $u\in \gameH_L$ (similarly for $\gameV_L$).

It is clear from the definitions of the games $\gameH$ and $\gameV$.

The order induced by the subword relation (known also as the Higman's order) has the following finiteness property.

The set of finite words $A^\ast$ over a finite alphabet $A$ with the subword ordering is a well/̄quasi order: there is no infinite antichain nor an infinite descending chain.

If $L\subseteq A^\ast$ is closed under removing letters then $L$ is regular.

Consider $L\subseteq A^\ast$ that is closed under removing letters. Then $L$ forms a downward/̄closed set with respect to the subword relation. Thus, Higman's Lemma implies that there exists a finite set of words $w_1,\ldots,w_N$ such that $w$ does not belong to $L$ if and only if one of $w_1,\ldots,w_N$ is a subword of $w$. Such a condition is a regular condition.

Both $\gameH_L$ and  $\gameV_L$ are regular languages of finite words.

Both languages are closed under removing letters and therefore Fact <ref> applies.

The above corollary is amusing, but useless for our needs, because it does not say how to compute automata for $\gameH_L$ and $\gameV_L$ as a function of a representation of the language $L$.

The following properties hold for each context $C$ and context environment $E$:

* $(h_1, \ldots, h_n) \in \gameH_L$ implies $(C[h_1], \ldots, C[h_n])\in \gameH_L$.

*  $(v_1, \ldots, v_n) \in \gameV_L$ implies $(E[v_1], \ldots, E[v_n]) \in \gameH_L$.

$(v_1,\ldots,v_n),(w_1,\ldots,w_n)  \in \gameV_L$ implies $(v_1w_1,\ldots,v_{n}w_{n}) \in \gameV_L$.

*  $(v_1,\ldots,v_n)\in \gameV_L ,(h_1,\ldots,h_n)  \in \gameH_L$ implies $(v_1h_1,\ldots,v_{n}h_{n}) \in \gameH_L$.

*  $(v_1,\ldots,v_n) \in \gameV_L$  implies $(v_1^\infty,\ldots,v_n^\infty) \in \gameH_L$.

* $(h_1,\ldots,h_n)  \in \gameH_L$ implies $(c[\hole,h_1],\ldots,c[\hole,h_n]) \in \gameV_L$.

* $(h_1,\ldots,h_n)  \in \gameH_L$ implies $(c[h_1,\hole],\ldots,c[h_n,\hole]) \in \gameV_L$.

All properties are proved by composing strategies, we prove the first one. All other properties are proved similarly. Assume that $(h_1,\ldots,h_n)  \in \gameH_L$, and consider some multicontext $C$ (possibly with infinitely many ports). For all $i\leq n$ let $L_i$ be the set of trees that are Alternator's first move in some winning strategy for $\gameH(h_i,\dots,h_n)$. Note that since $(h_1,\dots,h_n)\in \gameH_L$, $L_i$ is non/̄empty for all $i$.

Lemma <ref> follows directly from the following claim.

For all $i \leq n$, for all trees $t$ obtained by plugging trees of $L_i$ in the ports of $C$, Alternator has a winning strategy in $\gameH(C[h_i],\dots, C[h_n])$ such that the tree chosen in round $1$ is $t$.

We proceed by induction on $i$. For $i=n$ this is obvious. Assume the result holds for $i$ and we prove it for $i-1$. Let $p$ be a prefix of $t$, for all subtree $s$ plugged into a port of $C$, $p$ yields some (possibly empty) prefix $p_s$ of $s$. Since $s \in L_{i-1}$, $p_s$ can be completed into a tree $s'\in L_i$. It follows that $p$ can be completed into $t'$ obtained by plugging trees of $L_i$ in the ports of $C$. By induction hypothesis, Alternator has winning strategy in $\gameH(C[h_i],\dots, C[h_n])$ such the tree chosen in round $1$ is $t'$. Finally we conclude that Alternator has winning strategy
in $\gameH(C[h_{i-1}],\dots,C[h_n])$ such the tree chosen in round $1$ is $t$.

This completes the proof of Lemma <ref>.

We define the alternation of a finite word to be the length of the word obtained by iteratively eliminating letters that are identical to their predecessors. We say that a set of words has unbounded alternation if it contains words with arbitrarily large alternation. In the other case we say that a set has bounded alternation. A word is alternating if every two consecutive letters are distinct.

For example the alternation of $abccbbb$ is $4$ and $abcb$ is the alternating word witnessing that. The notion of alternation gives us another characterization of the class $\boolcomb{1}$.

For a regular language $L$ of infinite trees, the following conditions are equivalent:

* Alternator wins the game $\gameHs(L,n)$ for infinitely many $n$.

* The set $\gameH_L$ has unbounded alternation.

Clearly, if $n\leq n'$ and Constrainer wins the game $\gameHs(L,n)$ then he also wins the game $\gameHs(L,n')$. This means that in fact there are only two possibilities: either Alternator wins $\gameHs(L,n)$ for all $n$; or Constrainer wins $\gameHs(L,n)$ for all except finitely many $n$. Thus, the conditions of Lemma <ref> are in fact equivalent to saying that Alternator wins the game $\gameHs(L,n)$ for all $n$.

We have to prove both implications.

$1 \Rightarrow 2$.
We show that for $n\in\w$ if Alternator wins the game $\gameHs(L,n)$, then $\gameH_L$ contains an alternating word of length $n$. Suppose that Alternator wins $\gameHs(L,n)$. Both $L$ and $L\complemento$ can be partitioned into tree types, see Remark <ref>. By Lemma <ref>, Alternator wins $\gameH(h_1,\ldots,h_n)$ for some sequence of types, such that $h_i$ is included in $L$ or its complement, depending on the parity of $i$. In particular, the consecutive types are different.

$2 \Rightarrow 1$. Suppose that $\gameH_L$ has unbounded alternation. By Fact <ref> we know that $\gameH_L$ is closed under removing letters. We will now argue that there must be some $g,h \in H_L$ with $g\neq h$ such that $\gameH_L$ contains all the words

\[(g,h), (g,h,g,h), (g,h,g,h,g,h), \ldots\]

Assume contrarily and use finiteness of $H_L$: there must exist a global bound $B$ on the number of times any pair of distinct types $g\neq h$ can appear in a word in $\gameH_L$ in the alternating way as above. Consider an alternating word of length $|H_L|^2\cdot (B+1)+1$ in $\gameH_L$. This word contains $|H_L|^2\cdot (B+1)$ pairs of consecutive distinct letters and therefore some pair of those must appear there at least $B+1$ times — a contradiction.

Since $g$ and $h$ are different elements of the syntactic algebra, it follows that there must be some multicontext $C$ such that the tree type $C[g]$ is contained in $L$, while the tree type $C[h]$ is disjoint with $L$. By the first item of Lemma <ref>, we can conclude that $\gameH_L$ contains  all the words

\[\big(C[g],C[h]\big), \big(C[g],C[h],C[g],C[h]\big), \big(C[g],C[h],C[g],C[h],C[g],C[h]\big), \ldots\]

It follows that Alternator can alternate arbitrarily long between the language $L$ and its complement.

If $\gameV_L$  has unbounded alternation then so does $\gameH_L$.

Assume that $\gameV_L$ has unbounded alternation. Take $n>0$, we will find a sequence in $\gameH_L$ of alternation at least $n$. Let $N\eqdef 2\cdot n\cdot |V_L|^2$ and let $(v_1, \ldots, v_{N})$ be an alternating sequence in $\gameV_L$ of length $N$ — such a sequence exists by the assumption and Fact <ref>.
By Pigeon/̄hole Principle, there exist two types $v\neq v'\in V_L$ such that the word ${(v,v')}^n$ can be obtained from $(v_1, \ldots, v_{N})$ by removing letters. By the definition of $V_L$ (see Definition <ref>) we know that there exists a context environment $E$ such that $E[v]\neq E[v']$. Thus, by Item <ref> of Lemma <ref> we know that the word ${\big(E[v],E[v']\big)}^n$ is a member of $\gameH_L$. Since this word is alternating and has length $2n$, the claim holds.

§ EFFECTIVE CHARACTERISATION OF BC(SIGMA01)

In this section we state the crucial result of the paper, providing an effective characterisation of the class of regular tree languages in $\boolcomb{1}$.

For a regular language $L$ of infinite trees, the following conditions are equivalent.

* $L$ is a Boolean combination of open sets, i.e. $L \in \boolcomb{1}$.

* Constrainer wins the game $\gameHs(L,n)$ for all but finitely many $n$.

* The set $\gameH_L$ has bounded alternation.

* The following identities are satisfied in the algebra $(H_L, V_L)$:

\begin{align}
\label{eq:cond-bool}
u^\monoid u w^\monoid = u^\monoid v w^\monoid &= u^\monoid w w^\monoid  &\text{ if $(u,v,w) \in \gameV_L$ or $(w,v,u) \in \gameV_L$}\\
\label{eq:cond-limit}
{(u_2 w_2^\monoid v)}^\monoid u_1 w_1^\infty &= {(u_2 w_2^\monoid v)}^\infty &\text{ if $v\in V_L$ and $(u_1,u_2), (w_1,w_2) \in \gameV_L$}
\end{align}

We have already proved the implications $1 \Leftrightarrow 2 \Leftrightarrow 3$ respectively in Corollary <ref> and Lemma <ref>.
It remains to prove $3 \Leftrightarrow 4$.
The direction $3 \Rightarrow 4$ is not hard and we prove it in the next section, whereas the direction $4 \Rightarrow 3$ forms the technical core of the paper.

The problem whether a regular language $L$ belongs to $\boolcomb{1}$ is /̄complete, when the language $L$ is given as a parity non/̄deterministic automaton $\Aa$ recognising $L$.

Given a representation of $L$, one can compute the algebra $(H_L,V_L)$ in , see Fact <ref>. Then, verifying the equations from condition 4 of Theorem <ref> can be done in time polynomial in the size of the algebra (which is exponential in the number of states of the given automaton for $L$).

Hardness follows immediately from hardness of the universality problem for non/̄deterministic automata over finite trees [38], see <cit.> for a generic reduction of problems about complexity of infinite tree languages to universality of finite tree languages.

§.§ Overview of the proof

The remaining part of the proof of Theorem <ref> consists of two implications: $3\Rightarrow 4$ (Subsection <ref>) and $4\Rightarrow 3$ (Subsection <ref>).

The proof of the implication $3\Rightarrow 4$ is rather straightforward: we assume that either (<ref>) or (<ref>) is violated and prove that the set $\gameH_L$ has unbounded alternation. This is achieved by providing concrete strategies for Alternator in the game $\gameH_L$.

The proof of the implication $4\Rightarrow 3$ is more demanding. First, we introduce a concept of strategy trees that represent specific strategies of Alternator in $\gameH$ (Subsections <ref> to <ref>). We study properties of the set $\Sigma_L$ of those strategies and notice two distinct cases of their behaviour: Case (C1) leading to a violation of (<ref>); and Case (C2) leading to a violation of (<ref>). See Subsection <ref> for the case distinction.

The first argument, provided in Subsection <ref>, utilises the assumption of Case (C1) to construct strategy matrices — finite combinatorial objects witnessing the assumptions of Case (C1). By applying Erdös–Szekeres Theorem and Ramsey Theorem for hypergraphs, we gradually simplify the structure of these matrices. Ultimately, we construct a strategy matrix that literally encodes a violation of (<ref>) (see Lemma <ref>).

The second argument, given in Subsection <ref>, works under the assumption of Case (C2). This proof involves another object for representing certain strategies in $G_L$: a strategy graph $G_L$. The edges of that directed graph encode special types of strategies of Alternator in the game $\gameV$, see Lemma <ref>. A relatively easy observation (Lemma <ref>) shows that if the graph is recursive (i.e. contains certain loops) then it witnesses a violation of (<ref>). Subsection <ref> constructs inductively such a loop in $G_L$ based on the assumption of Case (C2).

§.§ The implication 3 => 4

In this section we prove the implication $3 \Rightarrow 4$ of Theorem <ref> in the contra positive, as stated below.

If one of the identities (<ref>) and (<ref>) of Theorem <ref> is violated then the set $\gameH_L$ has unbounded alternation.

§.§.§ The case when (<ref>) is violated.

The assumption that (<ref>) is violated says that there are $u,v,w \in V_L$ such that

\[(u,v,w) \in \gameV_L \qquad \text{or}\qquad (w,v,u) \in \gameV_L,\]

but the three context types $u^\monoid u w^\monoid$,  $u^\monoid v w^\monoid$, and $u^\monoid w w^\monoid$ are not all equal. If the three context types are not equal then the second one must be different from either the first one or the third one. We only do the proof for the case when $(u,v,w) \in \gameV_L$ and when $ u^\monoid u w^\monoid \neq
u^\monoid v w^\monoid$; the other cases are entirely dual. For $n \geq 0$ and $i \in \{1,\ldots,n\}$, define

\[\vec w_{(i,n)} \eqdef \big(\overbrace{u,u,\ldots,u}^{2(n{-}i){+}1},\ v,\ \overbrace{w,w,\ldots,w}^{2(i{-}1)}\big) \quad \in {(V_L)}^{2n}.\]

This word is obtained from $(u,v,w)$ by duplicating some letters, and therefore it  belongs to $\gameV_L$. For a given $n$, consider the words

\[\vec w_{(1,n)},  \ldots, \vec w_{(n,n)} \in \gameV_L.\]

These are $n$  words of length $2n$. Let us multiply all these words coordinate/̄wise, yielding a word $\vec w_{n}$, also of length $2n$, which
is depicted in the following picture:

[gray!50] (-6+5*0.7-0.2, 0.35-0.5) rectangle ++(0.4, -4*0.5-0.7);

[gray!50] (-6+6*0.7-0.2, 0.35-0.5) rectangle ++(0.4, -4*0.5-0.7);

ıin 1,...,5
[toL] at (-5.7, -ı*0.5) $\vec{w}_{(\i,n)}=$;
in 1,...,
[toC] at (-6 + *0.7, -ı*0.5) $u$;

[toC] at (-6 + *0.7, -ı*0.5) $v$;
< 11
in ,...,10
[toC] at (-6 + *0.7, -ı*0.5) $w$;

[toL] at (-6+5*0.7, -0.5 + 0.9) letter $2i{-}1$;
[toR] at (-6+6*0.7, -0.5 + 0.9) letter $2i$;

[edge,<-] (-6+5*0.7, -0.5 + 0.4) – ++(-0.5, +0.3);
[edge,<-] (-6+6*0.7, -0.5 + 0.4) – ++(+0.5, +0.3);

[toL] at (-6+5*0.7, -5*0.5 - 1.0) $u^{n-i+1}w^{i-1}$;
[toR] at (-6+6*0.7, -5*0.5 - 1.0) $u^{n-i}vw^{i-1}$;

[edge,<-] (-6+5*0.7, -5*0.5 - 0.4) – ++(-0.5, -0.3);
[edge,<-] (-6+6*0.7, -5*0.5 - 0.4) – ++(+0.5, -0.3);

As $\vec{w}_{n}$ is obtained by a coordinate/̄wise multiplication of the rows of the above matrix, and all these rows belong to $\gameV_L$, Lemma <ref> implies that also $\vec{w}_{n}\in\gameV_L$.

Recall that $\monoid$ is a number dependant on $V_L$ such that for every $z\in V_L$ we know that $z^\monoid$ is an idempotent. Choose some $k$, and take  $n = k \cdot \monoid+1$, and $i \in \{\monoid{+}1,2\monoid{+}1, \ldots,(k-1) \cdot  \monoid{+}1\}$. Consider the letters $2i-1$ and $2i$ in the word $\vec w_{n}$, which are

\[u^{n-i+1}w^{i-1} = u^\monoid uw^{\monoid}  \qquad u^{n-i} v w^{i-1} = u^\monoid v w^\monoid.\]

By the assumption, these letters are different, and therefore the word $\vec w$ has alternation at least $k$. Because $k$ was chosen
arbitrarily, it follows that $\gameV_L$ has unbounded alternation. Lemma <ref> implies that in that case also $\gameH_L$ has unbounded alternation.

§.§.§ The case when (<ref>) is violated.

The assumption that (<ref>) is violated says that $\gameV_L$ contains pairs $(u_1,u_2)$ and $(w_1,w_2)$ such that for some $v \in V_L$,

\begin{align*}
e^\infty \neq e u_1 w_1^\infty \qquad \mbox{ for }e \eqdef {(u_2w_2^\monoid v)}^\monoid.
\end{align*}

Let $h_1=e^\infty$ and $h_2=e u_1 w_1^\infty$, by the above assumption we know that $h_1\neq h_2$. It turns out that a violation of Equation (<ref>) has even stronger consequences than a violation of Equation (<ref>), as expressed by the following claim. It speaks about the infinite variant of the game of types, which is defined analogously to the finite one, see Subsection <ref>.

If Equation (<ref>) is violated then Alternator wins $\gameHinfty(h_1,h_2,h_1,\ldots)$.

The above claim implies in particular that for every $n$ the sequence

\[{\big(h_1, h_2\big)}^n\]

belongs to $\gameH_L$, and thus $\gameH_L$ has unbounded alternation.

Let $C_{u_1}$, $C_{w_1}$ be contexts of types $u_1$, $w_1$ that witness that $(u_1,u_2), (w_1,w_2)\in \gameV_L$ i.e. they are contexts played by Alternator in the first rounds of the respective games. Let $C_{u_2}$, $C_{w_2}$, and $C_v$ be any three contexts of types $u_2$, $w_2$, and $v$ respectively. Let $C_e\eqdef {\big(C_{u_2} C_{w_2}^\monoid C_v\big)}^\monoid$. The type of the context $C_e$ is $e$.

Our aim is to provide an explicit strategy of Alternator in the game $\gameHinfty(h_1,h_2,h_1,\ldots)$. This will be done inductively, considering the consecutive rounds of the game. The outcome will be a set of trees ${(t_i)}_{i<\w}$ that are played in the considered play of the game, with $\alpha_L(t_i)=h_1$ for odd $i$ and $\alpha_L(t_i)=h_2$ for even $i$.

The strategy of Alternator starts with the tree $t_1={\big(C_e\big)}^\infty$. We will demonstrate how it works for the first three rounds of the game, the rest is analogous.

Consider a prefix $p_1$ of the tree $t_1$ that is fixed by Constrainer. It must be the case that $p_1$ is a prefix of ${\big(C_e\big)}^{n_1}$ for some $n_1$. Thus, Alternator can now provide the tree

\[t_2={\big(C_e\big)}^{n_1}\cdot C_{u_1}\cdot C_{w_1}^\infty.\]

Now Constrainer chooses a prefix $p_2$ of the above tree, in fact $p_2$ is a prefix of ${\big(C_e\big)}^{n_1}\cdot C_{u_1}\cdot C_{w_1}^{\monoid\cdot n_2}$ for some $n_2$. Thus, by the assumptions on $C_{u_1}$ and $C_{u_2}$, Alternator is able to provide a tree of the form

\[t_2 = {\big(C_e\big)}^{n_1}\cdot \big( D_{u_2}\cdot D_{w_2}^{\monoid\cdot n_2}\cdot C_v\big) \cdot {\big(C_e\big)}^{\infty},\]

where the contexts $D_{u_2}$ and $D_{w_2}$ depend on the prefix $p_2$ and have types $u_2$ and $w_2$ respectively. Now we proceed inductively as before, because any prefix $p_3$ of $t_2$ must be a prefix of ${\big(C_e\big)}^{n_1}\cdot \big( D_{u_2}\cdot D_{w_2}^{\monoid\cdot n_2}\cdot C_v\big) \cdot {\big(C_e\big)}^{n_3}$.

Notice that by the choice of $e$, the type of the context $D_{u_2}\cdot D_{w_2}^{\monoid\cdot n_2}\cdot C_v$ is $e$. Therefore, $\alpha_L(t_i)=e^\infty=h_1$ for odd $i$ and $\alpha_L(t_i)=e u_1 w_1^\infty=h_2$ for even $i$.

Consider a pair of trees $t_1$ and $t_2$ of types $h_1$ and $h_2$ respectively. Since $t_1\not\Teq_L t_2$, there exists a multicontext $C$ such that[We swap $h_1$ and $h_2$ if needed.]

\begin{equation}
C[t_1]\in L\ \land\ C[t_2]\notin L,
\label{eq:distinction}
\end{equation}

see Definition <ref>. Now, by Item 1 of Lemma <ref> we know that the types $\alpha_L\big(C[t_1]\big)$, $\alpha_L(C[t_2]\big)$ (and therefore the conditions in (<ref>)) do not depend on the actual choice of the trees $t_1\in h_1$ and $t_2\in h_2$. Thus, by using the above strategy for Alternator under the multicontext $C$, we obtain the following corollary.

If Equation (<ref>) is violated then Alternator wins $\gameHinfty(L)$.

§.§ The implication 4=>3 — case distinction

We now move to the implication $4 \Rightarrow 3$ of Theorem <ref>, which is the most involved part of the article. To prove it, we need to introduce a crucial concept witnessing a large alternation of the set $\gameH_L$. The objects witnessing that will be called strategy trees and locally optimal strategy trees. Using these objects we will split the proof of that implication into two separate cases, see Subsection <ref>. We deal with these cases in Subsections <ref> and <ref>..

§.§.§ Strategy trees

First, a  is a tree such that the nodes are labelled with tree types, i.e. it is a tree over the alphabet $H_L$.

If $t$ is a tree over the alphabet $A$, the induced by $t$ is the $\sigma$ where the label of a node $u$ is the tree type of the subtree $t.u$, i.e. $\sigma(u)=\alpha_L(t.u)$. In particular $\sigma(\epsilon)=\alpha_L(t)$.

Let $\sigma$ be a and let $t$ be a tree over $A$. We say that $\sigma$ is locally consistent with $t$ if for every node $u \in {\{\dL,\dR\}}^\ast$, whose label in $t$ is $a$, we have that $\sigma(u)$ is the type obtained by applying the letter $a$ to the pair of types $\sigma(u\dL)$ and $\sigma(u\dR)$, that is

\begin{equation}
\sigma(u)=a\big(\sigma(u\dL),\hole\big)\cdot \sigma(u\dR).
\label{eq:local-consistency}
\end{equation}

In other words, if we take a tree $t_1$ inside $\sigma(u\dL)$ and a tree $t_2$ inside $\sigma(u\dR)$ and we plug these two trees as the left and the right children of $a$, then the type of the result is $\sigma(u)$.

The induced by $t$ is locally consistent with $t$.

Consider the language

\[ L = \{ t \in \trees_A \mid \text{$t$ contains at least one $b$}\}\]

over the alphabet $A = \{a,b\}$. $H_L$ contains two tree types that (treated as sets of trees) are $L$ and $L\complemento$. Now consider a $\sigma$ where every node is labelled with $L$. It is easy to check that $\sigma$ is locally consistent with every tree $t \in \trees_A$, even with the tree that contains only letters $a$.

The set of pairs

\[\big\{(t,\sigma)\in\trees_A\times\trees_{H_L}\mid \text{$\sigma$ is locally consistent with $t$}\big\}\]

is closed in the product topology.

As Condition (<ref>) speaks about finitely many values of $\sigma$ and $t$, it corresponds to a clopen set of pairs. A $\sigma$ is locally consistent with a tree $t$ if they obey the local consistency conditions from (<ref>) in all the vertices. Thus, the above defined set of pairs is an intersection of a family of clopen sets.

Let ${(t_n)}_{n\in \N}$ be a sequence of trees that converges to $t_\ast$ and let ${(\sigma_n)}_{n\in \N}$ be a sequence of s that converges to $\sigma_\ast$. If $\sigma_n$ is locally consistent with $t_n$ for every $n$ then $\sigma_\ast$ is locally consistent with $t_\ast$.

Follows directly from Fact <ref>.

Now we are ready to define strategy trees, a key concept of this paper.

A strategy tree is a tuple $\sigma = (t, \sigma_1, \ldots, \sigma_n)$

* $t$ is a tree over $A$, called the support of $\sigma$.

* $\sigma_1$ is the induced by $t$.

* The s $\sigma_2, \ldots, \sigma_n$ are locally consistent with $t$.

* For each node $u$ of $t$, the sequence $\big(\sigma_2(u), \ldots, \sigma_n(u)\big)$ belongs to $\gameH_L$.

Notice that the fourth condition of Definition <ref> does not mention the $\sigma_1$. By the definition, $\sigma$ can be interpreted as a single tree over the alphabet $A \times H_L^n$.

Intuitively speaking, a strategy tree represents a special kind of strategy for Alternator. In the first round, Alternator plays the support $t$ of $\sigma$. However,
Alternator also declares all the types that will appear in the nodes of $t$ as the game progresses. More specifically, he declares that for every
node $u$ of $t$ and round $k \in \{2,\ldots,n\}$, he has a
strategy so that for the tree played in the round $k$, the subtree in the node $u$ has type $\sigma_k(u)$.

The number $n$ is called the duration of a strategy tree $\sigma=(t,\sigma_1,\ldots,\sigma_n)$. We define the root sequence of a strategy tree to be the sequence of root labels of $\sigma_1,\ldots,\sigma_n$. If the duration is $n$, the root sequence is in $H_L^n$. We define the root alternation of a strategy tree $\sigma$ to be the alternation of its root sequence. We define the limit alternation of $\sigma$ to be the maximal number $\ell$ such that infinitely many subtrees of $\sigma$ have root alternation at least $\ell$. This means that if the limit alternation of $\sigma$ is $\ell$ then there exist infinitely many nodes $u$ such that their root sequence (i.e. the root sequence of the strategy tree obtained by truncating $\sigma$ in the node $u$) has alternation at least $\ell$.

*Context zones.

A context zone is a set $X$ of nodes for which there exists a node $u$, called the root of $X$, and a node $y$, called the port of $X$, such that $u\prec y$ and $X$ contains the nodes that are in the subtree of $u$, but not in the subtree of $y$:

\[X=\big\{x\in{\{\dL,\dR\}}^\ast\mid u\preceq x \land y\not\preceq x\big\}.\]

We say that context zones $X_1,\ldots,X_n$ are consecutive if for each $i \in \{1,\ldots,n-1\}$, the port of $X_i$ is the root of $X_{i+1}$. The union of consecutive context zones is a context zone.

Consider a tree $t$, a $\sigma$, and a context zone $X$. $X$ can be seen as a context inside $t$ taking into account the types of the subtrees of $t$ as declared in $\sigma$. This is achieved by defining a value $\val(t,\sigma,X)\in V_L$. The definition of $\val(t,\sigma,X)$ is inductive on the number of nodes $v$ in $X$ such that $v \preceq y$, where $y$ is the port of $X$. If there is only one such node then the port $y$ of $X$ is a child of its root $u$. Let $a$ be the label of
$u$ in $t$ and $v\in X$ be the other child of $u$. We set $\val(t,\sigma,X)$
as $a(\hole,\sigma(v))$ if $v$ is the right child and $a(\sigma(v)
,\hole)$ if $v$ is the left child. Otherwise, let $u$ be the root of
$X$, $y$ its port and $z$ the child of $u$ such that $z \preceq y$. Let $X_1$ be the context zone with root $u$ and port $z$ and $X_2$
the context zone of root $z$ and port $y$. We define

\[\val(t,\sigma,X)\eqdef\val(t,\sigma,X_1) \cdot \val(t,\sigma,X_2).\]

Figure <ref> illustrates an example of a tree and a context zone with

\[\val(t,\sigma,X)=b(\hole,h_1)\cdot c(h_2,\hole)\in V_L.\]

In other words, $\val(t,\sigma,X)$ is the value of the context $C\eqdef t\restr X$ when we assume that the subtrees of $t$ aside of the branch leading to the port of $C$ have types as declared by $\sigma$.

[thick] (-1*, -1**) – (0,0) – (+1*, -1**);

(tu) at (+*0.35,0.1);
(hu) at (+*0.35,0);

(lu) at ($(-1*\hHu, -1*\hHu*\vVs-\vMu) + (hu)$);
(uu) at ($(0,-\vMu) + (tu)$);
(ru) at ($(+1*\hHu, -1*\hHu*\vVs-\vMu) + (hu)$);

(ll) at ($(-1*\hHl*0.8, -1*\hHl*\vVs-\vMl) + (hu)$);
(ul) at ($(0,-\vMl) + (tu)$);
(rl) at ($(+1*\hHl*0.8, -1*\hHl*\vVs-\vMl) + (hu)$);

(ll)[rounded corners=15pt, draw] –
(ul)[rounded corners=0pt] –
(rl)[draw=white!0] –
(ru)[rounded corners=15pt, draw] –
(uu)[rounded corners=0pt] –
(lu)[draw=white!0] –

trlabb = [scale=0.7]

[trlabb] (n1) at ($(0,-\vMu)+(-\hTp*0.5,+\hTp*\vTs*0.5)$) $(\ast,\ast)$;
[trlabb] (n2) at ($(n1)+(+\hTp,-\hTp*\vTs)$) $(b,\ast)$;
[trlabb] (n3r) at ($(n2)+(+\hTp,-\hTp*\vTs)$) $(\ast,h_1)$;
[trlabb] (n3l) at ($(n2)+(-\hTp,-\hTp*\vTs)$) $(c,\ast)$;
[trlabb] (n4r) at ($(n3l)+(+\hTp,-\hTp*\vTs)$) $(\ast,\ast)$;
[trlabb] (n4l) at ($(n3l)+(-\hTp,-\hTp*\vTs)$) $(\ast,h_2)$;

[tredge] (n1) – (n2);
[tredge] (n2) – (n3l);
[tredge] (n2) – (n3r);
[tredge] (n3l) – (n4l);
[tredge] (n3l) – (n4r);

(d0) at ($(0,-\vMu*0.5)+(-\hTp*0.5*0.5,+\hTp*\vTs*0.5*0.5)$);
(d1) at ($(n1)+(-\hTp*0.5,-\hTp*\vTs*0.5)$);
(d2r) at ($(n3r)+(+\hTp*0.5,-\hTp*\vTs*0.5)$);
(d3l) at ($(n4l)+(-\hTp*0.5,-\hTp*\vTs*0.5)$);
(d4r) at ($(n4r)+(+\hTp*0.5,-\hTp*\vTs*0.5)$);
(d4l) at ($(n4r)+(-\hTp*0.5,-\hTp*\vTs*0.5)$);

[trdots] (n1) – (d0);
[trdots] (n1) – (d1);
[trdots] (n3r) – (d2r);
[trdots] (n4l) – (d3l);
[trdots] (n4r) – (d4r);
[trdots] (n4r) – (d4l);

[toC] at (2, -5.5) $X$;

An illustration to the value $\val(t,\sigma,X)$. The grey area is the set $X$, a label $(a,h)$ of a node $u$ represents the values of $t(u)=a$ and $\sigma(u)=h$ respectively. The symbol $\ast$ indicates values that are irrelevant for the value of the set $X$.

Now assume that $\sigma= (t, \sigma_1,\ldots,\sigma_n)$ is a strategy tree. Let $X$
be a context zone of $\sigma$ (we can see $\sigma$ as a single tree). For a round $i \in \{1,\ldots,n\}$, we define the type

\[\val(\sigma,X,i) \eqdef \val(t,\sigma_i,X)\in V_L.\]

Let $\sigma=(t,\sigma_1,\dots,\sigma_n)$ be a strategy tree and $X$ be
a context zone. Then

\[\big(\val(\sigma,X,1),\dots,\val(\sigma,X,n)\big) \in \gameV_L.\]

This is by construction and Items 3, 6 and 7 of Lemma <ref>.

§.§.§ Existence of strategy trees

We will now prove that whenever Alternator has a strategy in $\gameH$ then this fact is witnessed by a strategy tree. This fact is expressed by the following two lemmas. For inductive reasons these lemmas are parametrised by a finite multicontext $C$. The games $\gameH_C(h_1,\ldots,h_n)$ and $\gameV_C(h_1,\ldots,h_n)$ are defined as the games $\gameH_U(h_1,\ldots,h_n)$ and $\gameV_U(h_1,\ldots,h_n)$ respectively, where $U$ is the open set of all trees (resp. contexts) that can be obtained from $C$, i.e. $C[\ast]$.

Let $C$ be a finite multicontext for strategy trees. Consider a sequence of valuations $\eta_1,\ldots,\eta_n$ that map ports of $C$ to $H_L$. If

\[ (\eta_1(u),\ldots,\eta_n(u)) \in \gameH_L\]

for every port $u$, then Alternator wins the game

\[\gameH_C(C[\eta_1],\ldots,C[\eta_n]).\]

For every port $u$ of $C$, Alternator has a winning strategy for the game

\[\gameH(\eta_1(u),\ldots, \eta_n(u)).\]

We describe a winning strategy for Alternator in $\gameH_C(C[\eta_1],\ldots,C[\eta_n])$. Alternator starts with a tree obtained by plugging the initial tree from his winning strategy in the game $\gameH(\eta_1(u),\ldots, \eta_n(u))$ in every port $u$ of $C$. Then every prefix of this tree yields a prefix for each subtree plugged into a port of $C$ and Alternator can then use his strategies for the game $\gameH(\eta_1(u),\ldots, \eta_n(u))$ to answer.

For a sequence $(h_1, \ldots, h_n) \in H_L^\ast$ and a finite multicontext $C$ the
following conditions are equivalent:

* Alternator wins $\gameH_C(h_1, \ldots, h_n)$.

* There is a strategy tree  whose support extends $C$, with root sequence  $(h_1, \ldots, h_n)$.

We prove the lemma by induction on $n$. The base case when $n=0$ or $n=1$, is trivial. We do the induction
step. Let us begin with the easier implication from 2 to 1. Suppose that

\begin{align*}
\sigma \equiv (t,\sigma_1,  \ldots, \sigma_n)
\end{align*}

is a strategy tree as in item 2. Alternator's strategy is as follows. In the first round, he plays the tree $t$, which has type $h_1$. Suppose Constrainer chooses a prefix $p$ of
$t$. Let $D$ be the multicontext obtained from $p$ by labelling all the ${\preceq}$/̄minimal elements outside of $\dom(p)$ by $\hole$. Consider the valuations $\eta_2,\ldots,\eta_n$ that map all the ports of $D$ to $H_L$ with $\eta_i(u)= \sigma_i(u)$ for any port $u$ of $D$. For every $i \in \{2,\ldots,n\}$, the root label of $\sigma_i$ is the same as $D[\eta_i]$, because $\sigma_i$ is locally consistent with $t$ and $D$ is obtained from a prefix of $t$.
By Lemma <ref>, Alternator wins the game

\begin{align*}
\gameH_D(D[\eta_2], \ldots, D[\eta_n]).
\end{align*}

This shows  that for every choice of $p$, Alternator has a winning strategy in the remaining part of the game.

Now we move to the more difficult implication from 1 to 2.

Suppose that Alternator wins $\gameH_C(h_1, \ldots, h_n)$. Let $t$ be
the tree of type $h_1$ that Alternator plays in the first round. This tree
has prefix $C$. Also, for every finite prefix $D$ of $t$, Alternator
wins $\gameH_D(h_2, \ldots, h_n)$. By the induction assumption, for every finite
prefix $D$ of $t$, there is a strategy tree

\begin{align*}
\sigma_D = (t_D,\sigma_{D_2},\ldots,\sigma_{D_n})
\end{align*}

such that  $t_D$ has  prefix $D$, and the root sequence
of $\sigma_D$ is $(h_2, \ldots, h_n)$.

A sequence of finite multicontexts ${(D_i)}_{i \in \omega}$ is said to converge to $t$ if all of the multicontexts are prefixes of $t$, and for every $j \in \omega$, only finitely many multicontexts have some port at depth at most $j$. By compactness, there is an infinite sequence of finite multicontexts ${(D_i)}_{i \in \omega}$ which converges to the tree $t$ and such that all of the sequences

\begin{align*}
{(t_{D_i})}_{i \in \omega} \qquad  {(\sigma_{D_i 2})}_{i \in \omega} \qquad \ldots \qquad  {(\sigma_{D_i n})}_{i \in \omega}
\end{align*}

are convergent. Let the limits of these sequences be

\begin{align*}
t_* \qquad \sigma_{*2} \qquad \ldots \qquad \sigma_{*n}.
\end{align*}

Because the sequence ${(D_i)}_{i \in \omega}$ converges to $t$, it follows that $t_*=t$.
For each $D$, the type trees

\begin{align*}
\end{align*}

are locally consistent with $t_D$. Therefore, by Lemma <ref>
it follows that the limits  $\sigma_{*2},\ldots,\sigma_{*n}$ are locally consistent with $t$.
Finally, define $\sigma_{*1}$ to be the unique type tree that is globally consistent with $t$.
We have just proved that

\[(\sigma_{*1},\ldots,\sigma_{*n})\]

is a strategy tree. Because root values are preserved under limits, the root value of
this strategy tree is the desired $(h_1,\ldots,h_n)$.

§.§.§ Locally optimal strategy trees

To make the structure of a strategy tree more rigid, we will introduce the notion of a locally optimal strategy tree. In such a strategy tree, whenever $\sigma_i(u)\neq\sigma_{i+1}(u)$, there is some concrete reason for that fact.

Consider a strategy tree $(t,\sigma_1,\ldots,\sigma_n)$ and let $v \in V_L\sqcup\{\one_L\}$. The strategy tree is called locally optimal for $v$ if for every $i \in \{2,\ldots,n\}$ and for every $\sigma'$, if $\sigma'$ is locally consistent with $t$ and
$v \cdot \sigma'(\epsilon) = v \cdot \sigma_i(\epsilon)$, then

\[\topdisc(\sigma_{i-1},\sigma_i) \leq \topdisc(\sigma_{i-1},\sigma'),\]

where $\topdisc$ is the discounted distance.

If $\sigma$ is optimal for the context type $\one_L$ of the trivial context $\hole$ then we just say that $\sigma$ is locally optimal. Let $\Sigma_L$ denote the set of all locally optimal strategy trees for $L$.

If $\sigma$ is locally optimal for $u\cdot v$ then $\sigma$ is locally optimal for $v$ as well.

Consider a strategy tree $\sigma$ with root sequence $(h_1,\ldots,h_n)$. Let $v\in V_L\sqcup\{\one_L\}$ be a context type. Then there exists a locally optimal strategy tree $\sigma'$ for $v$ with root sequence $(h_1',\ldots,h_n')$ such that

\begin{equation}
v\cdot (h_1,\ldots,h_n)=v\cdot (h_1',\ldots,h_n').
\label{eq:preserve-types}
\end{equation}

Take a strategy tree $\sigma = (t, \sigma_1, \ldots, \sigma_n)$. Consider the set $\Sigma_2$ of type/̄labelled trees $\sigma_2'$ that are:

* locally consistent with $t$,

* if $h$ (resp. $h'$) is the root value of $\sigma_2$ (resp. $\sigma_2')$ then $v\cdot h = v\cdot h'$.

Fact <ref> implies that $\Sigma_2$ is a closed set. As a closed subset of the compact space of all trees, $\Sigma_2$ is compact. It follows that some elements of $\Sigma_2$ minimise the discounted distance with respect to $\sigma_1$. We choose such an element as the new $\sigma_2$ and we iterate this mechanism to build a locally optimal strategy tree $\bar{\sigma}$. This tree satisfies condition (<ref>).

Notice that in the above construction, if $v\neq\one_L$ then the root sequence of the new strategy tree might be different than the original root sequence. However, if $v=\one_L$ then the root sequence is not modified.

If $(h_1,h_2,\ldots,h_n)\in\gameH_L$ then there exists a locally optimal strategy tree $\sigma$ with root sequence $(h_1,\ldots,h_n)$.

Using the above properties, without loss of generality we can restrict our attention to locally optimal strategy trees. One of the direct consequences of working with such strategy trees is expressed by the following lemma.

If $\sigma$ is a locally optimal strategy tree, $u\preceq y$ two nodes of $\sigma$ then for all $i=1,\ldots,n$ we have

\[\sigma_i(y)\neq \sigma_{i+1}(y)\Rightarrow \sigma_i(u)\neq\sigma_{i+1}(u).\]

Assume that $\sigma_{i}(y) \neq \sigma_{i+1}(y)$ and $\sigma_{i}(u) =
\sigma_{i+1}(u)$. We show that this contradicts local optimality.
Consider the $\sigma'_{i+1}$ defined as follows:

* for every $z$ such that $u\preceq z$, $\sigma'_{i+1}(z)=\sigma_i(z)$,

* for all other nodes $z$, $\sigma'_{i+1}(z) = \sigma_{i+1}(z)$.

By the construction, $\sigma'_{i+1}$ is locally consistent with $t$ (this
is by the definition for all nodes $z \neq u$, and because $\sigma_{i}(u)
= \sigma_{i+1}(u)$). Note that by the definition, for all nodes

\[ \dist(\sigma_{i}(z),\sigma'_{i+1}(z)) \leq \dist(\sigma_{i}(z),\sigma_{i+1}(z))\]

Moreover, $\dist(\sigma_{i}(y),\sigma'_{i+1}(y))=0$ and $\dist(\sigma_{i}(y)
,\sigma_{i+1}(y))=1$. Combining all this we obtain:

* $\topdisc(\sigma_{i},\sigma'_{i+1}) < \topdisc(\sigma_{i},\sigma_{i+1})$.

* $\sigma'_{i+1}(\epsilon) = \sigma_{i+1}(\epsilon)$, as sequences in ${(H_L)}^n$.

This contradicts local optimality of $\sigma$.

If $\sigma$ is a locally optimal strategy tree and $u\preceq y$ are two nodes of $\sigma$ then the root alternation of $\sigma.u$ is not smaller than the root alternation of $\sigma.y$.

§.§.§ Case distinction

We can now split the proof of the implication $4 \Rightarrow 3$ of Theorem <ref> into two subcases, as discussed below. Then we will treat these cases separately, as expressed by Propositions <ref> and <ref>.