17318 LABEL:LastPageSep. 08, 2020Aug. 13, 2021

# Ambiguity Hierarchy of
Regular Infinite Tree Languages

Alexander Rabinovich  and  Doron Tiferet  Tel Aviv University, Israel
<EMAIL_ADDRESS><EMAIL_ADDRESS>https://www.cs.tau.ac.il/~rabinoa

###### Abstract.

An automaton is unambiguous if for every input it has at most one accepting
computation. An automaton is $k$-ambiguous (for $k>0$) if for every input it
has at most $k$ accepting computations. An automaton is boundedly ambiguous if
it is $k$-ambiguous for some $k\in\mathbb{N}$. An automaton is finitely
(respectively, countably) ambiguous if for every input it has at most finitely
(respectively, countably) many accepting computations.

The degree of ambiguity of a regular language is defined in a natural way. A
language is $k$-ambiguous (respectively, boundedly, finitely, countably
ambiguous) if it is accepted by a $k$-ambiguous (respectively, boundedly,
finitely, countably ambiguous) automaton. Over finite words every regular
language is accepted by a deterministic automaton. Over finite trees every
regular language is accepted by an unambiguous automaton. Over $\omega$-words
every regular language is accepted by an unambiguous Büchi automaton and by a
deterministic parity automaton. Over infinite trees Carayol et al. showed that
there are ambiguous languages.

We show that over infinite trees there is a hierarchy of degrees of ambiguity:
For every $k>1$ there are $k$-ambiguous languages that are not $k-1$
ambiguous; and there are finitely (respectively countably, uncountably)
ambiguous languages that are not boundedly (respectively finitely, countably)
ambiguous.

###### Key words and phrases:

regular tree languages, parity tree automata, automata ambiguity

##  1\. Introduction

#### Degrees of Ambiguity

The relationship between deterministic and nondeterministic machines plays a
central role in computer science. An important topic is a comparison of
expressiveness, succinctness and complexity of deterministic and
nondeterministic models. Various restricted forms of nondeterminism were
suggested and investigated (see [Col15, HSS17] for recent surveys).

Probably, the oldest restricted form of nondeterminism is unambiguity. An
automaton is unambiguous if for every input there is at most one accepting
run. For automata over finite words there is a rich and well-developed theory
on the relationship between deterministic, unambiguous and nondeterministic
automata [HSS17]. All three models have the same expressive power. Unambiguous
automata are exponentially more succinct than deterministic ones, and
nondeterministic automata are exponentially more succinct than unambiguous
ones [Lei81, Leu05].

Some problems are easier for unambiguous than for nondeterministic automata.
As shown by Stearns and Hunt [SHI85], the equivalence and inclusion problems
for unambiguous automata are in polynomial time, while these problems are
PSPACE-complete for nondeterministic automata.

The complexity of basic regular operations on languages represented by
unambiguous finite automata was investigated in [JJŠ16], and tight upper
bounds on state complexity of intersection, concatenation and many other
operations on languages represented by unambiguous automata were established.

It is well-known that the tight bound on the state complexity of the
complementation of nondeterministic automata is $2^{n}$. In [JJŠ16], it was
shown that the complement of the language accepted by an $n$-state unambiguous
automaton is accepted by an unambiguous automaton with $2^{0.79n+\log n}$
states.

Many other notions of ambiguity were suggested and investigated. A recent
paper [HSS17] surveys works on the degree of ambiguity and on various
nondeterminism measures for finite automata on words.

An automaton is _$k$ -ambiguous_ if on every input it has at most $k$
accepting runs; it is _boundedly ambiguous_ if it is $k$-ambiguous for some
$k$; it is _finitely ambiguous_ if on every input it has finitely many
accepting runs.

It is clear that an unambiguous automaton is $k$-ambiguous for every $k>0$,
and a $k$-ambiguous automaton is finitely ambiguous. The reverse implications
fail. For $\epsilon$-free automata over words (and over finite trees), on
every input there are at most finitely many accepting runs. Hence, every
$\epsilon$-free automaton on finite words and on finite trees is finitely
ambiguous. However, over $\omega$-words there are nondeterministic automata
with uncountably many accepting runs. Over $\omega$-words and over infinite
trees, finitely ambiguous automata are a proper subclass of the class of
countably ambiguous automata, which is a proper subclass of nondeterministic
automata.

The cardinality of the set of accepting computations of an automaton over an
infinite tree $t$ is bounded by the cardinality of the set of functions from
the nodes of $t$ to the state of the automaton, and therefore, it is at most
continuum $2^{\aleph_{0}}$. The set of accepting computations on $t$ is
definable in Monadic Second-Order Logic (MSO). In Bárány et al. in [BKR10] it
was shown that the continuum hypothesis holds for MSO-definable families of
sets. Therefore, if the set of accepting computations of an automaton on a
tree $t$ is uncountable, then its cardinality is $2^{\aleph_{0}}$. Hence,
there are exactly two infinite degrees of ambiguity.

The degree of ambiguity of a regular language is defined in a natural way. A
language is $k$-ambiguous (respectively, boundedly, finitely, countably
ambiguous) if it is accepted by a $k$-ambiguous (respectively, boundedly,
finitely, countably ambiguous) automaton.

Over finite words, every regular language is accepted by a deterministic
automaton. Over finite trees, every regular language is accepted by a
deterministic bottom-up tree automaton and by an unambiguous top-down tree
automaton. Over $\omega$-words every regular language is accepted by an
unambiguous Büchi automaton [Arn83] and by a deterministic parity automaton.

Hence, the regular languages over finite words, over finite trees and over
$\omega$-words are unambiguous.

In [CLNW10] it was shown that the aforementioned situation is different for
infinite trees. Carayol et al. [CLNW10] proved that the language $L_{\exists
a}$ of infinite full-binary trees over the alphabet $\\{a,c\\}$, defined as
$L_{\exists a}:=\\{t\mid t$ has at least one node labeled by $a\\}$ is
ambiguous. The proof is based on the undefinability of a choice function in
Monadic Second-Order logic (MSO) [GS83, CL07].

Our results imply that the complement of every countable regular language is
not finitely ambiguous. Since $L_{\exists a}$ is the complement (with respect
to the alphabet $\\{a,c\\}$) of the language that consists of a single tree
(i.e. the tree with all nodes labeled by $c$), we conclude that $L_{\exists
a}$ is not finitely ambiguous (this strengthens the above mentioned result of
[CLNW10]). Our main result states that over infinite trees there is a
hierarchy of degrees of ambiguity:

######  Theorem 1 (Hierarchy).

  1. (1)

For every $k>1$ there are $k$-ambiguous languages that are not
$(k-1)$-ambiguous.

  2. (2)

There are finitely ambiguous languages that are not boundedly ambiguous.

  3. (3)

There are countably ambiguous languages that are not finitely ambiguous.

  4. (4)

There are uncountably ambiguous languages that are not countably ambiguous.

Some natural tree languages that witness items (1), (3) and (4) of Theorem 1
are described in the examples below. We have not found a “natural” finitely
ambiguous language which is not boundedly ambiguous (Theorem 1(2)). Let
$T_{\Sigma}^{\omega}$ be the set of all infinite full-binary trees over an
alphabet $\Sigma$. Let $\Sigma_{k}=\\{c,a_{1},a_{2},...,a_{k}\\}$, and let
$L_{\neg a_{i}}:=\\{t\in T_{\Sigma_{k}}^{\omega}\mid$ no node in $t$ is
labeled by $a_{i}\\}$ for $1\leq i\leq n$. Define:

  1. (1)

$L_{\neg a_{1}\vee\dots\vee\neg a_{k}}:=L_{\neg a_{1}}\cup\dots\cup L_{\neg
a_{k}}$. We show that this language is $k$-ambiguous, but is not
$(k-1)$-ambiguous (see Section 5). In [BS13] it was shown that $L_{\neg
a_{1}\vee\neg a_{2}}$ is two ambiguous.

  2. (2)

$L_{\exists a_{1}}:=\\{t\in T_{\Sigma_{1}}^{\omega}\mid$ there exists an
$a_{1}$-labeled node in $t\\}$. This is a countably ambiguous language that is
not finitely ambiguous (see Section 4).

  3. (3)

$L_{no-\max-a_{1}}:=\\{t\in T_{\Sigma_{1}}^{\omega}\mid$ above every
$a_{1}$-labeled node in $t$ there is an $a_{1}$-labeled node$\\}$. This is an
uncountably ambiguous language that is not countably ambiguous (see Section
7).

#### Organization of the Paper:

In Section 2 we recall notations and basic results about automata and monadic
second-order logic. In Section 3 simple properties of languages are proved.
Section 4 gives a sufficient condition for a language to be not finitely
ambiguous. The proof techniques used in Section 4 refine the proof techniques
of [CLNW10] – we rely on the fact that a choice function is not MSO-definable
to obtain a lower bound for degree of ambiguity that is higher than the bound
which was presented in [CLNW10]. Section 5 deals with $k$-ambiguous languages
– for every $k\in\mathbb{N}$, we describe a $k$-ambiguous language that is not
$(k-1)$-ambiguous. Section 6 provides an example of a finitely ambiguous
language which is not boundedly ambiguous. Section 7 introduces a scheme for
obtaining uncountably ambiguous languages from languages that are not
boundedly ambiguous, and presents some natural examples of uncountably
ambiguous languages. In Section 8, relying on the characterization of
countable regular languages given by Niwiński [Niw91], we prove that every
countable tree language is unambiguous. The conclusion is given in Section 9.

An extended abstract of this paper was published in [RT20]. Here we added the
proofs that were sketched or missing in [RT20], presented natural examples of
uncountably ambiguous languages (in Section 7), and added Section 8 in which
we prove that countable languages are unambiguous using Niwiński’s
Representation for Countable Languages.

##  2\. Preliminary

We recall here standard terminology and notations about trees, automata and
logic [PP04, Rab69]. In Subsection 2.3 we also recall Gurevich-Shelah’s
theorem about undefinability of choice function and derive Lemma 6 which plays
an important role in our proofs.

###  2.1. Trees

We view the set $\\{l,r\\}^{*}$ of finite words over alphabet $\\{l,r\\}$ as
the domain of a full-binary tree, where the empty word $\epsilon$ is the root
of the tree, and for each node $v\in\\{l,r\\}^{*}$, we call $v\cdot l$ the
left child of $v$, and $v\cdot r$ the right child of $v$.

We define a tree order “$\leq$” as a partial order such that $\forall
u,v\in\\{l,r\\}^{*}:u\leq v$ iff $u$ is a prefix of $v$. Nodes $u$ and $v$ are
incomparable – denoted by $u\perp v$ – if neither $u\leq v$ nor $v\leq u$; a
set $U$ of nodes is an antichain, if its elements are incomparable with each
other.

We say that an infinite sequence $\pi=v_{0},v_{1},\dots$ is a tree branch if
$v_{0}=\epsilon$ and $\forall i\in\mathbb{N}:v_{i+1}=v_{i}\cdot l$ or
$v_{i+1}=v_{i}\cdot r$.

If $\Sigma$ is a finite alphabet, then a $\Sigma$-labeled full-binary tree $t$
is a labeling function $t:\\{l,r\\}^{*}\rightarrow\Sigma$. We denote by
$T^{\omega}_{\Sigma}$ the set of all $\Sigma$-labeled full-binary trees. We
often use “tree” for “labeled full-binary tree.”

Given a $\Sigma$-labeled tree $t$ and a node $v\in\\{l,r\\}^{*}$, the tree
$t_{\geq v}$ (called the subtree of $t$, rooted at $v$) is defined by $t_{\geq
v}(u):=t(v\cdot u)$ for each $u\in\\{l,r\\}^{*}$.

#### Grafting

Given two labeled trees $t_{1}$ and $t_{2}$ and a node $v\in\\{l,r\\}^{*}$,
the grafting of $t_{2}$ on $v$ in $t_{1}$, denoted by $t_{1}[t_{2}/v]$, is the
tree $t$ that is obtained from $t_{1}$ by replacing the subtree of $t_{1}$
rooted at $v$ by $t_{2}$. Formally, $t(u):=\begin{cases}t_{2}(w)&\exists
w\in\\{l,r\\}^{*}:u=v\cdot w\\\ t_{1}(u)&\text{otherwise}\end{cases}$

More generally, given a tree $t_{1}$, an antichain $Y\subseteq\\{l,r\\}^{*}$
and a tree $t_{2}$, the grafting of $t_{2}$ on $Y$ in $t_{1}$, denoted by
$t_{1}[t_{2}/Y]$, is obtained by replacing each subtree of $t_{1}$ rooted at a
node $y\in Y$ by the tree $t_{2}$.

#### Tree Language

A language $L$ over an alphabet $\Sigma$ is a set of $\Sigma$-labeled trees.
We denote by $\overline{L}:=T^{\omega}_{\Sigma}\setminus L$ the complement of
$L$.

###  2.2. Automata

We define the following notions of automata:

#### Parity $\omega$-word Automata (PWA)

A PWA is a tuple $(Q_{\mathcal{A}},\Sigma,Q_{I},\delta,\mathbb{C})$ where
$\Sigma$ is a finite alphabet, $Q$ is a finite set of states, $Q_{I}\subseteq
Q$ is a set of initial states, $\delta\subseteq Q\times\Sigma\times Q$ is a
transition relation, and $\mathbb{C}:Q\rightarrow\mathbb{N}$ is a coloring
function. A run of $\mathcal{A}$ on an $\omega$-word $y=a_{0}a_{1}\dots$ is an
infinite sequence $\rho=q_{0}q_{1}\dots$ such that $q_{0}\in Q_{I}$, and
$(q_{i},a_{i},q_{i+1})\in\delta$ for all $i\in\mathbb{N}$. We say that $\rho$
is accepting if the maximal number that occurs infinitely often in
$\mathbb{C}(q_{0})\mathbb{C}(q_{1})\dots$ is even.

#### Language

We denote the set of all accepting runs of $\mathcal{A}$ on $y$ by
$ACC(\mathcal{A},y)$. The language of $\mathcal{A}$ is defined as
$L(\mathcal{A}):=\\{y\in\Sigma^{\omega}\mid
ACC(\mathcal{A},y)\neq\emptyset\\}$.

#### Parity Tree Automata (PTA) on Infinite Trees

A PTA is a tuple $(Q_{\mathcal{A}},\Sigma,Q_{I},\delta,\mathbb{C})$ where
$\delta\subseteq Q\times\Sigma\times Q\times Q$, and $\Sigma$, $Q$, $Q_{I}$,
$F$ are defined as in PWA. A computation of $\mathcal{A}$ on a tree $t$ is a
function $\phi:\\{l,r\\}^{*}\rightarrow Q$ such that $\phi(\epsilon)\in
Q_{I}$, and $\forall v\in\\{l,r\\}^{*}:(\phi(v),t(v),\phi(v\cdot
l),\phi(v\cdot r))\in\delta$. We say that $\phi$ is accepting if for each tree
branch $\pi=v_{0}v_{1}\dots$, the maximal number that occurs infinitely often
in $\mathbb{C}(\phi(v_{0}))\mathbb{C}(\phi(v_{1}))\dots$ is even.

Given a PTA
$\mathcal{A}=(Q_{\mathcal{A}},\Sigma,Q_{I},\delta_{\mathcal{A}},\mathbb{C}_{\mathcal{A}})$
and a set $Q^{\prime}\subseteq Q_{\mathcal{A}}$, we define
$\mathcal{A}_{Q^{\prime}}:=(Q_{\mathcal{A}},\Sigma,Q^{\prime},\allowbreak\delta_{\mathcal{A}},\mathbb{C}_{\mathcal{A}})$
as the automaton obtained from $\mathcal{A}$ by replacing the set of initial
states $Q_{I}$ with $Q^{\prime}$. For a singleton $Q^{\prime}=\\{q\\}$, we
simplify this notation by $\mathcal{A}_{q}:=\mathcal{A}_{Q^{\prime}}$.

#### Language

We denote the set of all accepting computations of $\mathcal{A}$ on $t$ by
$ACC(\mathcal{A},t)$. The language of $\mathcal{A}$ is defined as
$L(\mathcal{A}):=\\{t\in T^{\omega}_{\Sigma}\mid
ACC(\mathcal{A},t)\neq\emptyset\\}$. A tree language is said to be _regular_
if it is accepted by a PTA.

A state $q\in Q$ of a PTA $\mathcal{A}$ is called useful if there is a tree
$t\in L(\mathcal{A})$, a computation $\phi\in ACC(\mathcal{A},t)$ and a node
$v\in\\{l,r\\}^{*}$ such that $\phi(v)=q$. Throughout the paper we will assume
that all states of PTA are useful.

#### Degree of Ambiguity of an Automaton

We denote by $|X|$ the cardinality of a set $X$. An automaton $\mathcal{A}$ is
$k$-ambiguous if $|ACC(\mathcal{A},t)|\leq k$ for all $t\in L(\mathcal{A})$;
$\mathcal{A}$ is unambiguous if it is $1$-ambiguous; $\mathcal{A}$ is
boundedly ambiguous if there is $k\in\mathbb{N}$ such that $\mathcal{A}$ is
$k$-ambiguous; $\mathcal{A}$ is finitely ambiguous if $ACC(\mathcal{A},t)$ is
finite for all $t$; $\mathcal{A}$ is countably ambiguous if
$ACC(\mathcal{A},t)$ is countable for all $t$.

The degree of ambiguity of $\mathcal{A}$ (notation $da(\mathcal{A})$) is
defined by $da(\mathcal{A}):=k$ if $\mathcal{A}$ is $k$-ambiguous and either
$k=1$ or $\mathcal{A}$ is not $k-1$ ambiguous, $da(\mathcal{A}):=finite$ if
$\mathcal{A}$ is finitely ambiguous and not boundedly ambiguous,
$da(\mathcal{A}):=\aleph_{0}$ if $\mathcal{A}$ is countably ambiguous and not
finitely ambiguous, and $da(\mathcal{A}):=2^{\aleph_{0}}$ if $\mathcal{A}$ is
not countably ambiguous.

We order the degrees of ambiguity in a natural way:
$i<j<finite<\aleph_{0}<2^{\aleph_{0}}$, for $i<j\in\mathbb{N}$.

##### Degree of Ambiguity of a Language

We say that a regular tree language $L$ is unambiguous (respectively,
$k$-ambiguous, finitely ambiguous, countably ambiguous) if it is accepted by
an unambiguous (respectively, $k$-ambiguous, finitely ambiguous, countably
ambiguous) automaton. We define
$da(L):=min_{\mathcal{A}}\\{da(\mathcal{A})\mid L(\mathcal{A})=L\\}$.

###  2.3. Monadic Second-Order Logic

We use standard notations and terminology about monadic second-order logic
(MSO) [Rab69, TB73, Tho90].

Let $\tau$ be a relational signature. A structure (for $\tau$) is a tuple
$M=(D,\\{R^{M}\mid R\in\tau\\})$ where $D$ is a domain, and each symbol
$R\in\tau$ is interpreted as a relation $R^{M}$ on $D$.

MSO-formulas use first-order variables, which are interpreted by elements of
the structure, and monadic second-order variables, which are interpreted as
sets of elements. Atomic MSO-formulas are of the following form:

  * •

$R(x_{1},\dots,x_{n})$ for an $n$-ary relational symbol $R$ and first order
variables $x_{1},\dots,x_{n}$

  * •

$x=y$ for two first-order variables $x$ and $y$

  * •

$x\in X$ for a first-order variable $x$ and a second-order variable $X$

MSO-formulas are constructed from the atomic formulas, using boolean
connectives, the first-order quantifiers, and the second-order quantifiers.

We write $\psi(X_{1},\dots,X_{n},x_{1},\dots,x_{m})$ to indicate that the free
variables of the formula $\psi$ are $X_{1},\dots,X_{n}$ (second order
variables) and $x_{1},\dots,x_{m}$ (first order variables). We write
$M\models\psi(A_{1},\dots,A_{n},a_{1},\dots a_{m})$ if $\psi$ holds in $M$
when subsets $A_{i}$ are assigned to $X_{i}$ for $i=1,\dots,n$ and elements
$a_{i}$ are assigned to variables $x_{1},\dots,x_{m}$ for $i=1,\dots,m$.

#### Coding

Let $\Delta$ be a finite set. We can code a function from a set $D$ to
$\Delta$ by a tuple of unary predicates on $D$. This type of coding is
standard, and we shall use explicit variables that range over such mappings
and expressions of the form “$F(u)=d$” (for $d\in\Delta$) in MSO-formulas,
rather than their codings.

Formally, for each finite set $\Delta$ we have second-order variables
$X_{1}^{\Delta},X_{2}^{\Delta},\dots$ that range over the functions from $D$
to $\Delta$, and atomic formulas $X_{i}^{\Delta}(u)=d$ for $d\in\Delta$ and
$u$ a first order variables [TB73]. Often the type of the second order
variables will be clear from the context and we drop the superscript $\Delta$.

#### Definable Relations

The powerset of $D$ is denoted by $\mathcal{P}(D)$. We say that a relation
$R\subseteq\mathcal{P}(D)^{n}\times D^{m}$ is MSO-definable in a structure $S$
with universe $D$ if there is an MSO-formula
$\psi(X_{1},\dots,X_{n},x_{1},\dots,x_{m})$ such that
$R=\\{(D_{1},\dots,D_{n},u_{1},\dots,u_{m})\in\mathcal{P}(D)^{n}\times
D^{m}\mid S\models\psi(D_{1}\dots,D_{n},u_{1}\dots,u_{m})\\}$.

An element $d\in D$ is MSO-definable in a structure $S$ if there is a formula
$\psi(x)$ such that $S\models\phi(u)$ iff $u=d$. A set $U\subseteq D$ is MSO-
definable if there is a formula $\phi(X)$ such that $S\models\phi(V)$ iff
$V=U$. A function is MSO-definable if its graph is.

The unlabeled binary tree is the structure $(\\{l,r\\}^{*},\\{E_{l},E_{r}\\})$
where $E_{l}$ and $E_{r}$ are binary symbols, respectively interpreted as
$\\{(v,v\cdot l)\mid v\in\\{l,r\\}^{*})\\}$ and $\\{(v,v\cdot r)\mid
v\in\\{l,r\\}^{*})\\}$.

It is easy to verify the correctness of the following lemma:

######  Lemma 2.

The following relations are MSO-definable in the unlabeled full-binary tree.

  * •

The ancestor relation $\leq$.

  * •

“A set of nodes is a branch,” “A set of nodes is an antichain.”

  * •

Let $\mathcal{A}=(Q,\Sigma,Q_{I},\delta,\mathbb{C})$ be a PTA. We use $\phi$
for a function $\\{l,r\\}^{*}\rightarrow Q$ and $\sigma$ for a function
$\\{l,r\\}^{*}\rightarrow\Sigma$.

    * –

“$\phi$ is a computation of $\mathcal{A}$ on the tree $\sigma$.”

    * –

“$\phi$ is an accepting computation of $\mathcal{A}$ on the tree $\sigma$.”

The following two fundamental theorems were proved by Rabin in his famous 1969
paper [Rab69].

######  Theorem 3 (Rabin [Rab69]).

A tree language is regular iff it is MSO-definable in the unlabeled binary
tree structure.

A labeled tree is regular iff it has finitely many different subtrees. An
equivalent definition is: a tree is regular iff its labeling is MSO-definable
[Rab69]. Hence, for every regular $\Sigma$-labeled tree $t_{0}$ there is an
MSO-formula $\psi_{t_{0}}(\sigma^{\Sigma}$), where $\sigma^{\Sigma}$ is the
coding of $\\{l,r\\}^{*}\rightarrow\Sigma$, that is satisfied by
$t:\\{l,r\\}^{*}\rightarrow\Sigma$ iff $t=t_{0}$.

######  Theorem 4 (Rabin’s basis theorem [Rab69]).

Any non-empty regular tree language contains a regular tree.

#### Choice Function

A choice function is a mapping that assigns to each non-empty set of nodes one
element from the set.

######  Theorem 5 (Gurevich and Shelah [GS83]).

There is no MSO-definable choice function on the full-binary tree.

The following lemma follows from Theorem 5. It plays a key role in our proofs
in Section 4, where sufficient conditions are provided for a language to be
not finitely ambiguous.

######  Lemma 6.

There is no MSO-definable function that assigns to every non-empty antichain
$Y$ a finite non-empty subset $X\subseteq Y$.

######  Proof 2.1.

Assume, for the sake of contradiction, that a function that returns a finite
non-empty subset for each non-empty antichain is MSO-definable in the
unlabeled full-binary tree, by an MSO-formula $FiniteAntichainSubset(X,Y)$.

######  Claim 7 (Choice function over finite sets).

There is an MSO-definable function that assigns to each non-empty finite set
$X\subseteq\\{l,r\\}^{*}$ an element $x\in X$.

######  Proof 2.2 (Proof).

We first define a lexicographic order “$\leq_{\mathit{lex}}$” on
$\\{l,r\\}^{*}$, by $u\leq_{\mathit{lex}}v$ iff $u$ is a prefix of $v$ or
$u=w\cdot l\cdot u^{\prime}$ and $v=w\cdot r\cdot v^{\prime}$ for some
$w,u^{\prime},v^{\prime}\in\\{l,r\\}^{*}$.

It is easy to verify that $\leq_{\mathit{lex}}$ is MSO-definable in the
unlabeled full-binary tree. $\leq_{\mathit{lex}}$ is a linear order, and
therefore each non-empty finite set has exactly one
$\leq_{\mathit{lex}}$-minimal element. We conclude that a finite set choice
function is definable by $FiniteChoice(X,x):=$“$x$ is the
$\leq_{\mathit{lex}}$-minimal element in $X$”.

Let $FiniteChoice(X,x)$ be an MSO-formula that defines a function as in Claim
7. We will use formulas $FiniteAntichainSubset(X,Y)$ and $FiniteChoice(X,x)$
to define a choice function by an MSO-formula $Choice(X,x)$ which is the
conjunction of the following conditions:

  1. (1)

$\exists Z:$ “$Z$ is the set of $\leq$-minimal elements in $X$”

  2. (2)

$\exists Y:FiniteAntichainSubset(Z,Y)$

  3. (3)

$FiniteChoice(Y,x)$

For each non-empty set $X$ there is a unique subset $Z\subseteq X$ of the
$\leq$-minimal elements in $X$. This set is a non-empty antichain, and
therefore $FiniteAntichainSubset(Z,Y)$ returns a finite subset $Y\subseteq Z$.
Therefore, $FiniteChoice(Y,x)$ returns an element in $Y$. We conclude that
$Choice(X,x)$ returns an element $x\in X$ and therefore defines a choice
function in the unlabeled full-binary tree, in contradiction to Theorem 5.

##  3\. Simple Properties of Automata and Languages

In this section some simple lemmas are collected.

######  Lemma 8.

Let
$\mathcal{A}_{1}=(Q_{1},\Sigma_{1},Q^{1}_{I_{1}},\delta_{1},\mathbb{C}_{1})$
and
$\mathcal{A}_{2}=(Q_{2},\Sigma_{2},Q^{2}_{I_{1}},\delta_{2},\mathbb{C}_{2})$
be two PTA. Then:

  1. (1)

There exists an automaton $\mathcal{B}$ such that
$L(\mathcal{B})=L(\mathcal{A}_{1})\cup L(\mathcal{A}_{2})$ and for each $t\in
L(\mathcal{A}_{1})\cup L(\mathcal{A}_{2})$,
$|ACC(\mathcal{B},t)|\leq|ACC(\mathcal{A}_{1},t)|+|ACC(\mathcal{A}_{2},t)|$.

  2. (2)

There exists an automaton $\mathcal{B}$ such that
$L(\mathcal{B})=L(\mathcal{A}_{1})\cap L(\mathcal{A}_{2})$ and for each $t\in
L(\mathcal{A}_{1})\cap L(\mathcal{A}_{2})$,
$|ACC(\mathcal{B},t)|\leq|ACC(\mathcal{A}_{1},t)|\cdot|ACC(\mathcal{A}_{2},t)|$.

######  Proof 3.1.

(1) Assume that $Q_{1}$ and $Q_{2}$ are disjoint, and let
$\mathcal{B}:=(Q_{1}\cup Q_{2},\Sigma_{1}\cup\Sigma_{2},Q^{1}_{I}\cup
Q^{2}_{I},\delta_{1}\cup\delta_{2},\mathbb{C}_{1}\cup\mathbb{C}_{2})$. It is
clear that $L(\mathcal{B})=L(\mathcal{A}_{1})\cup L(\mathcal{A}_{2})$.

Let $t\in L(\mathcal{B})$. By definition of $\mathcal{B}$, for each $\phi\in
ACC(\mathcal{B},t)$ we either have $\phi\in ACC(\mathcal{A}_{1},t)$ or
$\phi\in ACC(\mathcal{A}_{2},t)$. Therefore, we obtain
$|ACC(\mathcal{B},t)|=|ACC(\mathcal{A}_{1},t)|+|ACC(\mathcal{A}_{2},t)|$.

(2) It is easy to verify that there is an MSO-formula over $\omega$-words that
holds for
$w=(c_{1},c^{\prime}_{1}),\dots,(c_{i},c^{\prime}_{i}),\dots\in(Image(\mathbb{C}_{1})\times
Image(\mathbb{C}_{2}))^{\omega}$ iff the maximal color that appears infinitely
often in the first coordinate of $w$ and the maximal color that appears
infinitely often in the second coordinate of $w$ are both even. Therefore (by
McNaughton’s Theorem [McN66]) there is a deterministic PWA
$\mathcal{D}=(Q_{\mathcal{D}},\Sigma_{\mathcal{D}},q_{I}^{\mathcal{D}},\delta_{\mathcal{D}},\mathbb{C}_{\mathcal{D}})$
over alphabet $\Sigma_{\mathcal{D}}=Image(\mathbb{C}_{1})\times
Image(\mathbb{C}_{2})$ such that $w\in L(\mathcal{D})$ iff the maximal color
that appears infinitely often in the first coordinate of $w$ and the maximal
color that appears infinitely often in the second coordinate of $w$ are both
even.

We will use the automata $\mathcal{A}_{1},\mathcal{A}_{2}$ and $\mathcal{D}$
to define a PTA
$\mathcal{B}:=(Q_{\mathcal{B}},\Sigma_{\mathcal{B}},Q_{I}^{\mathcal{B}},\delta_{\mathcal{B}},\mathbb{C}_{\mathcal{B}})$
which accepts $L(\mathcal{A}_{1})\cap L(\mathcal{A}_{2})$.

  * •

$Q_{\mathcal{B}}=Q_{1}\times Q_{2}\times Q_{\mathcal{D}}$

  * •

$\Sigma_{\mathcal{B}}:=\Sigma_{1}\cap\Sigma_{2}$

  * •

$Q_{I}^{\mathcal{B}}:=Q_{I}^{1}\times
Q_{I}^{2}\times\\{q_{I}^{\mathcal{D}}\\}$

  * •

$((q,p,s),a,(q_{1},p_{1},s_{1}),(q_{2},p_{2},s_{2}))\in\delta_{\mathcal{B}}$
iff $(q,a,q_{1},q_{2})\in\delta_{1}$, $(p,a,p_{1},p_{2})\in\delta_{2}$, and
$s_{1}=s_{2}=\delta_{\mathcal{D}}(s,(\mathbb{C}_{1}(q),\mathbb{C}_{2}(p)))$.

  * •

$\mathbb{C}_{\mathcal{B}}(q_{1},q_{2},p):=\mathbb{C}_{\mathcal{D}}(p)$

It is easy to verify that $L(\mathcal{B})=L(\mathcal{A}_{1})\cap
L(\mathcal{A}_{2})$.

Assume, for the sake of contradiction, that there exists $t$ such that
$|ACC(\mathcal{B},t)|>|ACC(\mathcal{A}_{1},t)|\cdot|ACC(\mathcal{A}_{2},t)|$.
Since $\mathcal{D}$ is deterministic, it follows that there is a computation
in $ACC(\mathcal{B},t)$ such that either the projection of the first
coordinate of $\phi$ on $Q_{1}$, denoted $\phi_{1}$, is not in
$ACC(\mathcal{A}_{1},t)$ or the projection of the second coordinate of $\phi$
on $Q_{2}$, denoted $\phi_{2}$, is not in $ACC(\mathcal{A}_{2},t)$. Assume
w.l.o.g. that $\phi_{1}\notin ACC(\mathcal{A}_{1},t)$. Therefore, there is a
tree branch $\pi=v_{0},v_{1},\dots$ such that the maximal color that
$\mathbb{C}_{1}$ assigns to the states that occurs infinitely often in
$\phi_{1}(\pi)$ is odd. By definition of $\mathcal{D}$ we conclude that
$w:=(c_{0},c_{0}^{\prime}),(c_{1},c_{1}^{\prime}),\dots\notin L(\mathcal{D})$,
where $c_{i}:=\mathbb{C}_{1}(\phi_{1}(v_{i}))$ and
$c_{i}^{\prime}:=\mathbb{C}_{2}(\phi_{2}(v_{i}))$. Hence, by definition of
$\mathcal{B}$ we conclude that the sequence of colors that
$\mathbb{C}_{\mathcal{B}}$ assigns to the states $\phi(\pi)$ is exactly $w$,
and therefore $\phi\notin ACC(\mathcal{B},t)$ – a contradiction.

From Lemma 8, we obtain:

######  Corollary 9.

Boundedly, finitely and countably ambiguous tree languages are closed under
finite union and intersection.

We often use implicitly the following simple Lemma.

######  Lemma 10 (Grafting).

Let $\mathcal{A}$ be an automaton, $t$, $t_{1}$ trees, $v\in\\{l,r\\}^{*}$ and
$\phi\in ACC(\mathcal{A},t)$, and $\phi_{1}\in ACC(\mathcal{A}_{q},t_{1})$. If
$\phi(v)=q$, then $\phi[\phi_{1}/v]$ is an accepting computation of
$\mathcal{A}$ on $t[t_{1}/v]$.

A similar lemma holds for general grafting. As an immediate consequence, we
obtain the following lemma:

######  Lemma 11.

$da(\mathcal{A})\geq da(\mathcal{A}_{q})$ for every useful state $q$ of
$\mathcal{A}$.

######  Corollary 12.

Let $\mathcal{A}$ be a boundedly (respectively, finitely, countably) ambiguous
PTA with a set $Q$ of useful states, and let $Q^{\prime}\subseteq Q$. Then
$\mathcal{A}_{Q^{\prime}}$ is boundedly (respectively, finitely, countably)
ambiguous.

######  Lemma 13.

Let $L_{1}$ and $L_{2}$ be two tree languages such that $da(L_{1})\neq
da(L_{2})$ and $L_{1}\subseteq L_{2}$. Then, there exists a tree $t\in
L_{2}\setminus L_{1}$.

######  Proof 3.2.

The lemma follows immediately, since otherwise we have $L_{1}=L_{2}$ and
therefore $da(L_{1})=da(L_{2})$, in contradiction to $da(L_{1})\neq
da(L_{2})$.

######  Lemma 14.

Let $\mathcal{A}=(Q,\Sigma,Q_{I},\delta,\mathbb{C})$ be a PTA. Then, there
exists a PTA
$\mathcal{B}=(Q_{\mathcal{B}},\Sigma,\\{q_{I}^{\mathcal{B}}\\},\allowbreak\delta_{\mathcal{B}},\mathbb{C})$
with single initial state such that $L(\mathcal{B})=L(\mathcal{A})$, and
$da(\mathcal{B})\leq da(\mathcal{A})$.

######  Proof 3.3.

Let $Q_{\mathcal{B}}:=Q\cup\\{q_{I}^{\mathcal{B}}\\}$ and
$\delta_{\mathcal{B}}:=\delta_{\mathcal{A}}\cup\\{(q_{I}^{\mathcal{B}},a,q_{l},q_{r})\mid
q_{I}\in Q_{I}$ and $(q_{I},a,q_{l},q_{r})\in\delta\\}$. It is easy to see
that $L(\mathcal{B})=L(\mathcal{A})$.

Let $t\in L(\mathcal{A})$, and let $g_{t}$ be a function from
$ACC(\mathcal{A},t)$ to $ACC(\mathcal{B},t)$ that maps each computation
$\phi\in ACC(\mathcal{A},t)$ to a computation $\phi^{\prime}$ that assigns
$q_{I}^{\mathcal{B}}$ to node $\epsilon$, and $\phi(v)$ to other nodes. It is
easy to see that $\phi^{\prime}\in ACC(\mathcal{B},t)$, and that $g_{t}$ is
surjective, and therefore $\forall
t:|ACC(\mathcal{A},t)|\geq|ACC(\mathcal{B},t)|$, as requested.

[Moore machine] A Moore machine is a tuple
$M=(\Sigma,\Gamma,Q,q_{I},\delta,out)$, where $\Sigma$ is a finite input
alphabet, $Q$ is a finite set of states, $q_{I}\in Q$ is an initial state,
$\delta:Q\times\Sigma\rightarrow Q$ is a transition function, $\Gamma$ is an
output alphabet, and $out:Q\rightarrow\Gamma$ is an output function.

Define $\widehat{\delta}:\Sigma^{*}\rightarrow Q$ by
$\widehat{\delta}(\epsilon):=q_{I}$ and
$\widehat{\delta}(w):=\delta(\widehat{\delta}(w^{\prime}),a)$ for
$w=w^{\prime}\cdot a$ where $w^{\prime}\in\Sigma^{*}$ and $a\in\Sigma$. We say
that a function $F:\Sigma^{*}\rightarrow\Gamma$ is definable by a Moore
machine if there is a Moore machine $M$ such that
$F(w)=out(\widehat{\delta}(w))$ for all $w\in\Sigma^{*}$. Let
$F:\Sigma_{1}^{*}\rightarrow\Sigma_{2}$ be a function definable by a Moore
machine, and let $t_{1}\in T^{\omega}_{\Sigma_{1}}$. We define
$t_{2}:=\widehat{F}(t_{1})$ as a tree in $T^{\omega}_{\Sigma_{2}}$ such that
$t_{2}(v):=F(t_{1}(v_{1})\cdot\dots\cdot t_{1}(v_{k}))$ where
$v_{1},v_{2},\dots,v_{k}$ is the path from the root to $v$.

For a tree language $L\subseteq T^{\omega}_{\Sigma_{1}}$, we define
$\widehat{F}(L):=\\{\widehat{F}(t)\mid t\in L\\}\subseteq
T^{\omega}_{\Sigma_{2}}$.

######  Lemma 15 (Reduction).

Let $L_{1}$ and $L_{2}$ be regular tree languages over alphabets $\Sigma_{1}$
and $\Sigma_{2}$, respectively. Let $F:\Sigma_{1}^{*}\rightarrow\Sigma_{2}$ be
a function definable by a Moore machine. Assume that for each $t\in
T^{\omega}_{\Sigma_{1}}$, $t\in L_{1}$ iff $\widehat{F}(t)\in L_{2}$. Then
$da(L_{1})\leq da(L_{2})$.

######  Proof 3.4.

Let $\mathcal{A}_{2}=(Q_{2},\Sigma_{2},Q^{2}_{I},\delta_{2},\mathbb{C}_{2})$
such that $\mathcal{A}_{2}$ accepts $L_{2}$ and
$da(\mathcal{A}_{2})=da(L_{2})$.

Let $M=(\Sigma_{1},\Sigma_{2},Q_{M},q_{I}^{M},\delta_{M},out_{M})$ be a Moore
machine defining $F$. We will use $\mathcal{A}_{2}$ and $M$ to define an
automaton
$\mathcal{A}_{1}=(Q_{1},\Sigma_{1},Q^{1}_{I},\delta_{1},\mathbb{C}_{1})$ such
that $t\in L(\mathcal{A}_{1})$ iff $\widehat{F}(t)\in L(\mathcal{A}_{2})$, by:

  * •

$Q_{1}:=Q_{2}\times Q_{M}$

  * •

$Q^{1}_{I}:=Q^{2}_{I}\times\\{q^{M}_{I}\\}$

  * •

$((q,p),a,(q_{1},p_{1}),(q_{2},p_{2}))\in\delta_{1}$ iff
$p_{1}=p_{2}=\delta_{M}(p,a)$ and $(q,out_{M}(p),q_{1},q_{2})\in\delta_{2}$

  * •

$\mathbb{C}_{1}(q,p):=\mathbb{C}_{2}(q)$

First notice that $\forall t\in T^{\omega}_{\Sigma}:t\in
L(\mathcal{A}_{1})\Leftrightarrow\widehat{F}(t)\in
L(\mathcal{A}_{2})\Leftrightarrow\widehat{F}(t)\in L_{2}\Leftrightarrow t\in
L_{1}$, and therefore $L(\mathcal{A}_{1})=L_{1}$ as needed.

Let $\phi\in ACC(\mathcal{A}_{1},t)$, and define a computation $\phi^{\prime}$
by $\phi^{\prime}(v)=q_{1}$ for $\phi(v)=(q_{1},q_{2})\in Q_{2}\times Q_{M}$.
It is easy to see that $\phi^{\prime}\in ACC(\mathcal{A}_{2},\widehat{F}(t))$
and since $M$ is deterministic, we conclude that
$|ACC(\mathcal{A}_{1},t)|\leq|ACC(\mathcal{A}_{2},\widehat{F}(t)|)|$, and
therefore $da(\mathcal{A}_{1})\leq da(\mathcal{A}_{2})$.

We conclude that $da(L_{1})\leq da(\mathcal{A}_{1})\leq
da(\mathcal{A}_{2})=da(L_{2})$, as requested.

Let us state another well-known characterization of regular trees.

######  Fact 16.

A tree $t$ is regular iff its labeling
$t~{}:~{}\\{l,r\\}^{*}\rightarrow\Sigma$ is definable by a Moore machine.

##  4\. Not-Finitely Ambiguous Languages

We provide here sufficient conditions for a language to be not finitely
ambiguous. These conditions will allow us to present some natural languages
which are countably ambiguous and not finitely ambiguous, proving Theorem
1(3). In addition, these results are used in Sects. 5-7 where it is proved
that for every $k>1$ there is a language of ambiguity degree equal to $k$ and
there are languages with finite and uncountable degrees of ambiguity.

First, we state our main technical result – Proposition 17. Then, we derive
some consequences. Finally, a proof of Proposition 17 is given. Our proof
relies on the fact that there is no MSO-definable function that assigns to
every non-empty antichain $Y$ a finite non-empty subset $X\subseteq Y$ (Lemma
6), and our proof techniques refine the proof techniques of [CLNW10].

Recall that for trees $t$ and $t^{\prime}$ and an antichain $Y$, we denote by
$t[t^{\prime}/Y]$ the tree obtained from $t$ by grafting $t^{\prime}$ at every
node in $Y$.

######  Proposition 17.

Let $t_{0}$ and $t_{1}$ be regular trees and $L$ be a regular language such
that $t_{0}\not\in L$ and $t_{0}[t_{1}/Y]\in L$ for every non-empty antichain
$Y$. Then $L$ is not finitely ambiguous.

For a tree language $L$ over alphabet $\Sigma$, we denote by $Subtree(L)$ the
tree language $\\{t\in T^{\omega}_{\Sigma}\mid\exists t^{\prime}\in L\>\exists
v:t^{\prime}_{\geq v}=t\\}$.

######  Corollary 18.

Let $L$ be a non-empty regular language over an alphabet $\Sigma$ such that
$Subtree(L)\neq T^{\omega}_{\Sigma}$. Then, the complement of $L$ is not
finitely ambiguous.

######  Proof 4.1.

Let $L$ be as in Corollary 18. We claim that there are regular
$\Sigma$-labeled trees $t_{0}\in L$ and $t_{1}\not\in Subtree(L)$. Indeed, by
Rabin’s basis theorem there is a regular $t_{0}\in L$. Since $L$ is regular,
there is an automaton $\mathcal{B}=(Q,\Sigma,\\{q_{I}\\},\delta,\mathbb{C})$
(with only useful states) that accepts $L$. It is clear that $\mathcal{B}_{Q}$
accepts $Subtree(L)$, and therefore $Subtree(L)$ is regular. The complement of
$Subtree(L)$ is regular (as the complement of a regular language) and non-
empty (since $Subtree(L)\neq T^{\omega}_{\Sigma}$), and therefore contains a
regular tree $t_{1}$ (by Rabin’s basis theorem). Note that
$t_{0}[t_{1}/Y]\not\in{L}$ for every non-empty antichain $Y$.

The complement of $L$ satisfies the assumption of Proposition 17. Therefore,
it is not finitely ambiguous.

######  Corollary 19 (Not finitely ambiguous languages).

The following languages are not finitely ambiguous:

  1. (1)

The complement of a non-empty regular countable tree language.

  2. (2)

The complement of a regular language that contains a single tree.

  3. (3)

The language $L_{\exists a_{1}}:=\\{t\in T_{\Sigma}^{\omega}\mid t$ has at
least one node labeled by $a_{1}\\}$ over alphabet
$\Sigma=\\{a_{1},\dots,a_{m},c\\}$.

######  Proof 4.2.

(1) Let $L$ be a non-empty regular countable tree language. Every tree has
countably many subtrees, and since $L$ is countable we conclude that
$Subtree(L)$ is countable. Therefore, $Subtree(L)$ does not contain all trees.
By Corollary 18, we conclude that $\overline{L}$ is not finitely ambiguous.

(2) Follows immediately from (1).

(3) By the definition of $L_{\exists a_{1}}$ we have $L_{\exists a_{1}}\cap
T^{\omega}_{\\{c,a_{1}\\}}=T^{\omega}_{\\{c,a_{1}\\}}\setminus\\{t_{c}\\}$,
and therefore by (2), $L_{\exists a_{1}}\cap T^{\omega}_{\\{c,a_{1}\\}}$ is
not finitely ambiguous. It is easy to see that $T^{\omega}_{\\{c,a_{1}\\}}$ is
unambiguous (since there is a deterministic automaton that accepts it).
Therefore, by Corollary 9 we conclude that $L_{\exists a_{1}}$ is not finitely
ambiguous.

It is easy to prove that the complement of every finite language (i.e. a
language which consists of finitely many trees) is countably ambiguous.
Therefore, we obtain:

######  Corollary 20.

If $L$ is regular and its complement is finite and non-empty, then
$da(L)=\aleph_{0}$.

######  Proof 4.3 (Proof of Corollary 20).

We first prove the following claim:

######  Claim 21.

Let $L$ be a regular tree language containing a single tree. Then
$\overline{L}$ is countably ambiguous.

######  Proof 4.4 (Proof).

Assume that $L=\\{t\\}$. $L$ is a regular language, and therefore $t$ is
regular. By Fact 16 there is a Moore machine
$M=(\\{l,r\\},\Sigma,Q_{M},q_{I}^{M},\delta_{M},out_{M})$ such that for each
$v\in\\{l,r\\}^{*}$, $out(\widehat{\delta}(v))=\sigma$ iff $t(v)=\sigma$ (that
is, $M$ defines the function $t:\\{l,r\\}^{*}\rightarrow\Sigma$).

We will use $M$ to construct a countably ambiguous automaton $\mathcal{A}$
that accepts $\overline{L}$ by guessing a node $v\in\\{l,r\\}^{*}$ such that
$t(v)\neq t^{\prime}(v)$ for each tree $t^{\prime}\in\overline{L}$.

Let $\mathcal{A}:=(Q_{\mathcal{A}},\Sigma,Q_{I},\delta,\mathbb{C})$ such that:

  * •

$Q_{\mathcal{A}}:=\\{q,q^{\prime}\\}\times Q_{M}$

  * •

$Q_{I}:=\\{(q^{\prime},q_{I}^{M})\\}$

  * •

$\delta$ is defined by:

    * –

$((q,p),a,(q,p^{\prime}),(q,p^{\prime\prime}))\in\delta$ iff
$\delta_{M}(p,l)=p^{\prime}$, $\delta_{M}(p,r)=p^{\prime\prime}$

    * –

$((q^{\prime},p),a,(q,p^{\prime}),(q,p^{\prime\prime}))\in\delta$ iff
$\delta_{M}(p,l)=p^{\prime}$, $\delta_{M}(p,r)=p^{\prime\prime}$ and
$out(p)\neq a$

    * –

$((q^{\prime},p),a,(q^{\prime},p^{\prime}),(q,p^{\prime\prime})),((q^{\prime},p),a,(q,p^{\prime}),(q^{\prime},p^{\prime\prime}))\in\delta$
iff $\delta_{M}(p,l)=p^{\prime}$, $\delta_{M}(p,r)=p^{\prime\prime}$ and
$out(p)=a$.

  * •

$\forall p\in Q_{M}:\mathbb{C}(q,p):=0$ and $\mathbb{C}(q^{\prime},p):=1$

By definition of $\mathcal{A}$, it is clear that $t^{\prime}\in
L(\mathcal{A})$ iff there is a node $v$ such that $t^{\prime}(v)\neq t(v)$,
and therefore $t^{\prime}\in L(\mathcal{A})$ iff $t^{\prime}\neq t$.

For each computation $\phi$ of $\mathcal{A}$ on $t^{\prime}$, the $Q_{M}$
component is determined deterministically by $M$ and $t$. If $\phi$ is
accepting, there are finitely many nodes $v$ such that the first component of
$\phi(v)$ is $q^{\prime}$ – otherwise, there would be a branch where the
maximal color assigned infinitely often by $\mathbb{C}$ is odd, in
contradiction to $\phi$ being an accepting computation. Therefore, there are
countably many accepting computations on each tree $t^{\prime}\in
L(\mathcal{A})$, and $\mathcal{A}$ is countably ambiguous.

$L$ is finite and therefore there are $t_{1},\dots,t_{k}\in
T^{\omega}_{\Sigma}$ such that $L=\\{t_{1},\dots,t_{k}\\}$. A finite tree
language does not contain a non-regular tree, and therefore
$t_{1},\dots,t_{k}$ are regular. By Claim 21, for each tree $t_{i}\in L$,
there is a countably ambiguous automaton $\mathcal{A}_{i}$ such that $t\in
L(\mathcal{A}_{i})$ iff $t\neq t_{i}$. Notice that
$\overline{L}=L(\mathcal{A}_{1})\cap\dots,\cap L(\mathcal{A}_{k})$, and
therefore by Lemma 8 we conclude that $\overline{L}$ is countably ambiguous.

#### On the Proof of Proposition 17

In the rest of this section, Proposition 17 is proved. Let us sketch some
ideas of the proof. For a language $L$, as in Proposition 17, and any non-
empty antichain $Y$ we show that if $\mathcal{A}$ does not accept $t_{0}$ and
accepts $t:=t_{0}[t_{1}/Y]$, then every $\phi\in ACC(\mathcal{A},t)$ chooses
(in an MSO-definable way) an element from $Y$. Hence, the computations in
$ACC(\mathcal{A},t)$ choose together a subset $X$ of $Y$ of cardinality
$\leq|ACC(\mathcal{A},t)|$ (each computation chooses a single element).
Therefore, if $\mathcal{A}$ accepts ${L}$ and is finitely ambiguous, then $X$
is finite – a contradiction to Lemma 6. To implement this plan, in Subsection
4.1 we recall a game theoretical interpretation of “a tree is accepted by an
automaton.” Then, in Subsection 4.2 we analyze which concepts related to these
games are MSO-definable. Finally, in Subsection 4.3, the proof is completed.

###  4.1. Membership Game

Let $\mathcal{A}=(Q,\Sigma,\\{q_{I}\\},\delta,\mathbb{C})$ be a PTA, and let
$t$ be a $\Sigma$-labeled tree. A two-player game $G_{t,\mathcal{A}}$ (called
a “membership game”) between Automaton and Pathfinder is defined as follows.
The positions of Automaton are $\\{l,r\\}^{*}\times Q$, and the positions of
Pathfinder are $\\{l,r\\}^{*}\times Q\times Q$. The initial position is
$(\epsilon,q_{I})$.

From a position $(v,q)\in\\{l,r\\}^{*}\times Q$ Automaton chooses a tuple
$(q_{l},q_{r})\in Q\times Q$ such that $\exists
a\in\Sigma:(q,a,q_{l},q_{r})\in\delta$, and moves to the position
$(v,q_{l},q_{r})$. From a position $(v,q_{l},q_{r})\in\\{l,r\\}^{*}\times
Q\times Q$ Pathfinder chooses a direction $d\in\\{l,r\\}$, and moves to the
position $(v\cdot d,q_{d})$.

We define a play
$\overline{s}:=e_{0},d_{0},e_{1},d_{1},\dots,e_{i},d_{i},\dots\in(Q\times
Q\times\\{l,r\\})^{\omega}$ as an infinite sequence of moves, corresponding to
the choices of Automaton and Pathfinder from the initial position. We say that
the move $e_{i}=(q_{l},q_{r})$ from position $(v,q)$ is invalid for Automaton
if $(q,t(v),q_{l},q_{r})\notin\delta$.

A strategy for a player in $G_{t,\mathcal{A}}$ is a function that determines
the next move of the player based on previous moves of both players.

A positional strategy for a player in $G_{t,\mathcal{A}}$ is a strategy that
determines the next move of the player based only on the current position. A
positional strategy for Automaton is a function $str:\\{l,r\\}^{*}\times
Q\rightarrow Q\times Q$, and a positional strategy for Pathfinder is a
function $STR:\\{l,r\\}^{*}\times Q\times Q\rightarrow\\{l,r\\}$.

Let $\mathbb{C}_{G}$ be a coloring function that maps each position in
$G_{t,\mathcal{A}}$ to a color in $\mathbb{N}$. We define
$\mathbb{C}_{G}(v,q):=\mathbb{C}(q)$ for Automaton’s positions, and
$\mathbb{C}_{G}(v,q_{l},q_{r}):=0$ for Pathfinder’s positions.

For each play $\overline{s}$ define $\pi_{\overline{s}}$ as the infinite
sequence of positions corresponding to the moves in $\overline{s}$. A play
$\overline{s}$ is winning for Automaton iff $\overline{s}$ does not contain an
invalid move for Automaton, and the maximal color that $\mathbb{C}_{G}$
assigns infinitely often to the positions in $\pi_{\overline{s}}$ is even.
Since all Pathfinder’s positions are colored by $0$, it is sufficient to
consider the coloring of Automaton’s positions in $\pi_{\overline{s}}$.

We say that a play is consistent with a strategy of a player if all moves of
the player are according to the strategy. A winning strategy for a player is a
strategy such that each play that is consistent with the strategy is winning
for the player.

Parity games are positionally determined [EJ91], i.e., for each parity game,
one of the players has a positional winning strategy. Therefore, if a player
has a winning strategy, then he has a positional winning strategy.
Additionally, if a positional strategy of a player wins against all positional
strategies of the other player, then it is a winning strategy.

We recall standard definitions and facts about the connections between games
and tree automata [GH82, PP04].

Let $\phi:\\{l,r\\}^{*}\rightarrow Q$ be a function such that
$\phi(\epsilon)=q_{I}$ and $\forall v\in\\{l,r\\}:\exists
a\in\Sigma:(\phi(v),a,\phi(v\cdot l),\phi(v\cdot r))\in\delta$. We define a
positional strategy $str_{\phi}:\\{l,r\\}^{*}\times Q\rightarrow Q\times Q$
for Automaton, by $str_{\phi}(v,q):=(\phi(v\cdot l),\phi(v\cdot r))$.
Conversely, for each positional strategy $str:\\{l,r\\}^{*}\times Q\rightarrow
Q\times Q$ of Automaton we construct a function
$\phi_{\mathit{str}}:\\{l,r\\}^{*}\rightarrow Q$ by $\phi(\epsilon):=q_{I}$
and for all $v\in\\{l,r\\}^{*}$ we set $\phi(v\cdot l):=q_{l}$, and
$\phi(v\cdot r):=q_{r}$ where $str(v,\phi(v))=(q_{l},q_{r})$.

######  Claim 18.

  1. (1)

Let $\overline{s}$ be a play that is consistent with $str_{\phi}$, and let
$(v_{i},q_{i})$ be the $i$-th position of Automaton in $\pi_{\overline{s}}$.
Then, $\phi(v_{i})=q_{i}$.

  2. (2)

If $\phi\in ACC(\mathcal{A},t)$, then $str_{\phi}$ is a positional winning
strategy for Automaton.

  3. (3)

If $str$ is a positional winning strategy for Automaton, then
$\phi_{\mathit{str}}\in ACC(\mathcal{A},t)$.

######  Proof 4.5 (Proof).

(1) We will prove by induction on $i$. For $i=0$ we have
$(v_{0},q_{0})=(\epsilon,q_{I})$ (by definition of $G_{t,\mathcal{A}}$), and
indeed $\phi(v_{0})=\phi(\epsilon)=q_{I}$. Assume the claim holds for $i=k$
and we prove for $i=k+1$.

Let $d\in\\{l,r\\}$ be the $i$-th move of Pathfinder in $\overline{s}$. By
definition of $G_{t,\mathcal{A}}$ we have $v_{i+1}=v_{i}\cdot d$, and
$q_{i+1}=q_{d}$, where $str_{\phi}(v_{i},q_{i})=(q_{l},q_{r})$.

By definition $str_{\phi}$ we have $(q_{l},q_{r})=(\phi(v_{i}\cdot
l),\phi(v_{i}\cdot l))$, and therefore $q_{i+1}=\phi(v_{i}\cdot
d)=\phi(v_{i+1})$, as requested.

(2) and (3) are well known results about membership games [PP04].

The next claim describes what happens when Pathfinder plays his winning
strategy in $G_{t,\mathcal{A}}$ against an Automaton’s winning strategy in
$G_{t^{\prime},\mathcal{A}}$ (for $t^{\prime}\neq t$).

######  Claim 19.

Assume $t\notin L(\mathcal{A})$ and let $\phi$ be an accepting computation of
$\mathcal{A}$ on a tree $t^{\prime}$, and $STR$ be a winning strategy of
Pathfinder in $G_{t,\mathcal{A}}$. Let
$\overline{s}:=e_{0},d_{0},e_{1},d_{1},\dots,e_{i},d_{i},\dots$ be the play
that is consistent with $str_{\phi}$ and $STR$. Then, there is
$i\in\mathbb{N}$ such that $e_{i}$ is an invalid move for Automaton in
$G_{t,\mathcal{A}}$. Moreover, if $e_{i}$ is the first invalid move for
Automaton in $\overline{s}$, then $t(v)\neq t^{\prime}(v)$ for $v:=d_{0}\dots
d_{i-1}$.

######  Proof 4.6 (Proof).

Assume, for the sake of contradiction, that $\overline{s}$ does not contain an
invalid move for Automaton, and let $(v_{i},q_{i})$ be the $i$-th position of
Automaton in $\pi_{\overline{s}}$. By definition of $G_{t,\mathcal{A}}$ it is
easy to see that $\pi=v_{0},\dots,v_{i},\dots$ is a branch in the full-binary
tree. Since $\phi$ is an accepting computation of $\mathcal{A}$ on
$t^{\prime}$, we conclude that the maximal color that $\mathbb{C}$ assigns
infinitely often to states in $\phi(\pi)$ is even. By Claim 18(1) we have
$\phi(v_{i})=q_{i}$, and therefore $\phi(\pi)=q_{0}\dots q_{i}\dots$. By the
definition of $\mathbb{C}_{G}$ we have
$\mathbb{C}_{G}(v_{i},q_{i})=\mathbb{C}(q_{i})$ and we conclude that the
maximal color that $\mathbb{C}$ assigns infinitely often in
$\pi_{\overline{s}}$ is even, and therefore the play is winning for Automaton
– a contradiction to $STR$ being a winning strategy of Pathfinder.

Therefore, Automaton makes an invalid move in $\overline{s}$. Let
$e_{i}=(q_{l},q_{r})$ be the first invalid move of Automaton in
$\overline{s}$. Since $e_{i}$ is invalid we have
$(q_{i},t(v_{i}),q_{l},q_{r})\notin\delta$, and by definition of $str_{\phi}$
we obtain $(q_{l},q_{r})=(\phi(v_{i}\cdot l),\phi(v_{i}\cdot r))$. Since
$\phi(v_{i})=q_{i}$ we have $(\phi(v_{i}),t(v_{i}),\phi(v_{i}\cdot
l),\phi(v_{i}\cdot r))\notin\delta$. $\phi$ is a computation of $\mathcal{A}$
on $t^{\prime}$ and therefore
$(\phi(v_{i}),{t^{\prime}}(v_{i}),\phi(v_{i}\cdot l),\phi(v_{i}\cdot
r))\in\delta$, and we conclude that $t(v_{i})\neq{t^{\prime}}(v_{i})$. Notice
that by the definition of $G_{t,\mathcal{A}}$ we have $v_{i}=d_{0}\dots
d_{i-1}$, and the claim follows.

###  4.2. MSO-definability

Throughout this section we will use the following conventions and terminology.

Positional Pathfinder strategies as labeled trees:

We will define a positional strategy $STR$ for Pathfinder as a function in
$\\{l,r\\}^{*}\times Q\times Q\rightarrow\\{l,r\\}$. Hence, it can be
considered as a $Q\times Q\rightarrow\\{l,r\\}$ labeled tree. Below we will
not distinguish between a positional Pathfinder’s strategy and the
corresponding $Q\times Q\rightarrow\\{l,r\\}$ labeled full-binary tree. In
particular, we call such a strategy regular, if the corresponding tree is
regular.

MSO-definability:

We will use “MSO-definable” for “MSO-definable in the unlabeled full-binary
tree.”

The rest of the proof deals with MSO-definability. By Claim 19, there is a
function $Invalid_{\mathcal{A}}(\phi,STR,t,v)$ that, for every accepting
computation $\phi$ of $\mathcal{A}$ on $t^{\prime}$, returns a node $v$ such
that ${t^{\prime}}(v)\neq t(v)$. This function depends on the strategy $STR$
of Pathfinder. The restriction of $Invalid_{\mathcal{A}}$ to the Pathfinder
positional winning strategies in $G_{t,\mathcal{A}}$ is MSO-definable (with
parameters $t$ and $STR$) by the following formula
$Leads_{\mathcal{A}}(\phi,STR,t,v)$, that describes in MSO the play of $\phi$
against $STR$ up to the first invalid move of Automaton (at the position
$(v,\phi(v)$).

Define $Leads_{\mathcal{A}}(\phi,STR,t,v)$ as the conjunction of:

  1. (1)

$\phi(\epsilon)=q_{I}$ –the play starts from the initial position.

  2. (2)

$\forall u<v:((\phi(u),t(u),\phi(u\cdot l),\phi(u\cdot r))\in\delta$ – all
Automaton’s moves at the positions $(u,q)$, where $u$ is an ancestor of $v$
respect $\delta$. (By Claim 18(1), in any play consistent with $\phi$,
Automaton can reach only the positions of the form $(u,\phi(u))$).

  3. (3)

$(\phi(v),{t}(v),\phi(v\cdot l),\phi(v\cdot r))\notin\delta$ – the Automaton
move at $(v,\phi(v))$ is invalid.

  4. (4)

$\forall u<v:(STR(u,\phi(u\cdot l),\phi(u\cdot r))=l)\leftrightarrow u\cdot
l\leq v))$ – the Pathfinder moves $d_{0}\dots d_{j}\dots$ are consistent with
$STR$ and are along the path from the root to $v$, i.e., $d_{0}d_{1}\dots
d_{j}\leq v$.

To sum up, we have the following claim:

######  Claim 20.

$Leads_{\mathcal{A}}(\phi,STR,t,v)$ defines a function that, for every tree
$t\not\in L(\mathcal{A})$, every Pathfinder’s positional (in
$G_{t,\mathcal{A}}$) winning strategy $STR$, and every $\phi\in
ACC(\mathcal{A},t^{\prime})$, returns a node $v$ such that $t(v)\neq
t^{\prime}(v)$.

Claim 20 plays a crucial role in our proof. It is instructive to compare it
with Theorem 5 which implies that there is no MSO-definable function
$F(t,D,v)$ that for a tree $t\neq t^{\prime}$ and $D:=\\{u\mid t(u)\neq
t^{\prime}(u)\\}$ returns a node $v$ such that $t(v)\neq t^{\prime}(v)$.

The following claim is folklore. Due to the lack of references, it is proved
in the Appendix.

######  Claim 21.

Let $t_{0}$ be a regular tree such that $t_{0}\notin L(\mathcal{A})$. Then,
Pathfinder has a regular positional winning strategy in
$G_{t_{0},\mathcal{A}}$.

Let $t_{0}$ be a regular tree such that $t_{0}\notin L(\mathcal{A})$. By Claim
21 there is a regular positional winning strategy $\widehat{STR}$ of
Pathfinder in $G_{t_{0},\mathcal{A}}$. Now, we can substitute $\widehat{STR}$
and $t_{0}$ for arguments $STR$ and $t$ of $Leads_{\mathcal{A}}$ and obtain
the following Proposition:

######  Proposition 26.

For every regular tree $t_{0}\notin L(\mathcal{A})$ and a regular positional
winning strategy $\widehat{STR}$ for Pathfinder in $G_{t_{0},\mathcal{A}}$,
there is an MSO-definable function that, for each accepting computation $\phi$
of $\mathcal{A}$ on $t^{\prime}$, returns a node $v$ such that $t_{0}(v)\neq
t^{\prime}(v)$.

######  Proof 4.7 (Proof).

Let $\psi_{t_{0}}(\sigma)$ and $\psi_{\widehat{STR}}(STR)$ be MSO-formulas
that define $t_{0}$ and $\widehat{STR}$. Then, by Claim 20,
$\exists\sigma\exists
STR:\psi_{t_{0}}(\sigma)\wedge\psi_{\widehat{STR}}(STR)\wedge
Leads_{\mathcal{A}}(\phi,STR,\sigma,v)$ defines such a function.

Let us continue with the proof of Proposition 17. Recall that for trees $t$
and $t^{\prime}$ and an antichain $Y$, we denote by $t[t^{\prime}/Y]$ the tree
obtained from $t$ by grafting $t^{\prime}$ at every node in $Y$.

######  Claim 22.

Let $t_{0}$ and $t_{1}$ be regular trees. Then, there is an MSO-formula
$\mathit{graft}_{t_{0},t_{1}}(Y,\sigma)$ defining a function that for every
antichain $Y$ returns the tree $t_{0}[t_{1}/Y]$.

######  Proof 4.8 (Proof of Claim 22).

$t_{0}$ and $t_{1}$ are regular, and therefore there are MSO-formulas
$\psi_{t_{0}}(\sigma)$ and $\psi_{t_{1}}(\sigma)$ that defines $t_{0}$ and
$t_{1}$.

Let $\psi^{\geq y}_{t_{1}}(y,\sigma)$ be a formula that is obtained from
$\psi_{t_{1}}(\sigma)$ by relativizing the first-order quantifiers to $\geq
y$, i.e., by replacing subformulas of the form $\exists x(\dots)$ and $\forall
x(\dots)$ by $\exists x(x\geq y)\wedge(\dots)$ and $\forall x(x\geq
y)\rightarrow(\dots)$. Then, $v,t\models\psi^{\geq y}_{t_{1}}(y,\sigma)$ iff
$t_{\geq v}=t_{1}$. Hence, $\mathit{graft}_{t_{0},t_{1}}(Y,\sigma)$ can be
defined as the conjunction of:

  1. (1)

$\exists\sigma_{0}\psi_{t_{0}}(\sigma_{0})\wedge\forall v$ – “if no $Y$ node
is an ancestor of $v$ then $\sigma(v)=\sigma_{0}(v)$,” and

  2. (2)

$\forall y(y\in Y)\rightarrow\psi^{\geq y}_{t_{1}}(y,\sigma)$ – “at every node
in $Y$ a tree $t_{1}$ is grafted.”

###  4.3. Finishing the Proof of Proposition 17

Now, we have all the ingredients ready for the proof of Proposition 17.

Let $\mathcal{A}$ be such that $L(\mathcal{A})={L}$, and let
$\alpha_{t_{0},\mathcal{A},\widehat{STR}}(\phi,v)$ be a formula that defines
the function from Proposition 26 ($t_{0}[t_{1}/Y]$ now takes the role of
$t^{\prime}$).

Define a formula:
$Choice_{\mathcal{A},t_{0},t_{1},\widehat{STR}}(Y,\phi,y):=y\in Y\wedge\exists
v(\alpha_{t_{0},\mathcal{A},\widehat{STR}}(\phi,v)\wedge v\geq y)$.

######  Claim 23.

$Choice_{\mathcal{A},t_{0},t_{1},\widehat{STR}}(Y,\phi,y)$ defines a function
that for every non-empty antichain $Y$ and an accepting computation $\phi$ of
$\mathcal{A}$ on $t_{0}[t_{1}/Y]$, returns a node $y\in Y$.

######  Proof 4.9 (Proof).

By Proposition 26, $\alpha_{t_{0},\mathcal{A},\widehat{STR}}(\phi,v)$ returns
a node $v$ such that $t_{0}(v)\neq(t_{0}[t_{1}/Y])(v)$. By definition of
$t_{0}[t_{1}/Y]$, there is a unique node $y\in Y$ such that $v\geq y$.

Define $ChooseSubset_{\mathcal{A},t_{0},t_{1},\widehat{STR}}(Y,X):=\forall
x:x\in X$ iff the following conditions hold:

  1. (1)

$x\in Y$ and

  2. (2)

$\exists\sigma$ such that

    1. (a)

$\mathit{graft}_{t_{0},t_{1}}(Y,\sigma)$ – “$\sigma=t_{0}[t_{1}/Y]$” and

    2. (b)

$\exists\phi AcceptingRun_{\mathcal{A}}(\sigma,\phi)\wedge
Choice_{\mathcal{A},t_{0},t_{1},\widehat{STR}}(Y,\phi,x)$, where
$AcceptingRun_{\mathcal{A}}(\sigma,\phi)$ defines “$\phi$ is an accepting
computation of $\mathcal{A}$ on the tree $\sigma$.”

######  Claim 24.

$ChooseSubset_{\mathcal{A},t_{0},t_{1},\widehat{STR}}(Y,X)$ defines a function
that maps every non-empty antichain $Y$ to a non-empty subset $X\subseteq Y$.
Moreover, $|X|\leq|ACC(A,t_{0}[t_{1}/Y])|$.

######  Proof 4.10 (Proof).

If $Y$ is non-empty, then $t_{0}[t_{1}/Y]\in{L}$. Hence, $\mathcal{A}$ has at
least one accepting computation on $t_{0}[t_{1}/Y]$. Therefore, $X$ is non-
empty, by Claim 23. The “Moreover” part immediately follows from Claim 23.

Let $\mathcal{A}$ be such that $L(\mathcal{A})={L}$ and assume, for the sake
of contradiction, that $\mathcal{A}$ is finitely ambiguous. In particular,
there are finitely many accepting computations of $\mathcal{A}$ on
$t_{0}[t_{1}/Y]$, and therefore by Claim 24, we conclude that
$ChooseSubset_{\mathcal{A},t_{0},t_{1},\widehat{STR}}(Y,X)$ assigns to every
non-empty antichain $Y$ a finite non-empty $X\subseteq Y$ – a contradiction to
Lemma 6.

##  5\. $k$-Ambiguous Languages

In this section we prove that for every $0<k\in\mathbb{N}$, there is a tree
language with the degree of ambiguity equal to $k$. First, we introduce some
notations. For a letter $\sigma$, we denote by $t_{\sigma}$, the full-binary
tree with all nodes labeled by $\sigma$. Let $L_{\neg a_{1}\vee\dots\vee\neg
a_{k}}:=L_{\neg a_{1}}\cup\dots\cup L_{\neg a_{k}}$ be a tree language over
alphabet $\Sigma_{n}=\\{c,a_{1},a_{2},...,a_{n}\\}$, where $L_{\neg
a_{i}}:=\\{t\in T_{\Sigma_{n}}^{\omega}\mid$ no node in $t$ is labeled by
$a_{i}\\}$.

######  Proposition 25.

The degree of ambiguity of $L_{\neg a_{1}\vee\dots\vee\neg a_{k}}$ for $k\leq
n$ is $k$.

It is easy to see that $L_{\neg a_{i}}$ are accepted by deterministic PTA.
Therefore, by Lemma 8, we obtain that $L_{\neg a_{1}\vee\dots\vee\neg a_{k}}$
is $k$-ambiguous. In the rest of this section we will show that $L_{\neg
a_{1}\vee\dots\vee\neg a_{k}}$ is not $(k-1)$-ambiguous. It was shown in
[BS13] that $L_{\neg a_{1}\vee\neg a_{2}}$ is ambiguous.

######  Lemma 26.

Let $L_{\exists a_{1}\wedge\dots\wedge\exists a_{m}}:=\\{t\in
T_{\Sigma_{n}}^{\omega}\mid$ for every $i\leq m$ there is a node in $t$
labeled by $a_{i}\\}$, and let $L$ be a tree language such that $t_{c}\notin
L$ and $L_{\exists a_{1}\wedge\dots\wedge\exists a_{m}}\cap
T^{\omega}_{\\{c,a_{1},\dots,a_{m}\\}}\subseteq L$. Then, $L$ is not finitely
ambiguous.

######  Proof 5.1.

Define a function $F:\Sigma^{*}\rightarrow\Sigma$ such that
$F(\sigma_{1}\dots\sigma_{k}):=a_{k-i+1}$ if there is $i$ such that
$\sigma_{i}=a_{1}$, for all $j<i:\sigma_{j}\neq a_{1}$ and $k-i+1\leq m$.
Otherwise, $F(\sigma_{1}\dots\sigma_{k}):=c$.

It is easy to see that $F$ is definable by a Moore machine, and $\forall t\in
T^{\omega}_{\Sigma}:t\in L_{\exists a_{1}}$ iff $\widehat{F}(t)\in L$.
Therefore, by Lemma 15 we conclude that $da(L)\geq da(L_{\exists a_{1}})$.
Since $L_{\exists a_{1}}$ is not finitely ambiguous (by Corollary 19 (3)), we
conclude that $L$ is not finitely ambiguous.

#### Notations

Let $a\in\Sigma$, $t_{1}\in T^{\omega}_{\Sigma}$ and $t_{2}\in
T^{\omega}_{\Sigma}$. We define $Tree(a,t_{1},t_{2})\in T^{\omega}_{\Sigma}$
as a tree $t$ where $t(\epsilon)=a$, $t_{\geq l}=t_{1}$ and $t_{\geq
r}=t_{2}$.

######  Lemma 27.

Let $\mathcal{A}$ be a finitely ambiguous automaton over alphabet $\Sigma_{n}$
such that $L(\mathcal{A})=L_{\neg a_{1}\vee\dots\vee\neg a_{k}}$ for $k\leq
n$. Then $|ACC(\mathcal{A},t_{c})|\geq k$.

######  Proof 5.2.

We will prove by induction on $k$. For $k=1$ the claim holds trivially, since
$t_{c}\in L(\mathcal{A})$ implies that $|ACC(\mathcal{A},t_{c})|\geq 1$.

Assume the claim holds for all $k<m\leq n$ and prove for $k=m$.

Let $\mathcal{A}=(Q,\Sigma,Q_{I},\delta,\mathbb{C})$ be a finitely ambiguous
automaton that accepts $L_{\neg a_{1}\vee\dots\vee\neg a_{m}}$. Define
$R:=\\{(q_{1},q_{2})\in Q\times Q\mid\exists q_{i}\in
Q_{I}:(q_{i},c,q_{1},q_{2})\in\delta)\\}$, and let $R[1]$ and $R[2]$ be the
projections of the first and second coordinate of $R$ on $Q$, respectively.

Define $Q_{\exists a_{m}}:=\\{q\in R[1]\mid L(A_{q})\cap L_{\exists
a_{m}}\neq\emptyset\\}$, and let $Q_{\exists a_{m}\wedge t_{c}}:=\\{q\in
Q_{\exists a_{m}}\mid t_{c}\in L(\mathcal{A}_{q})\\}$ and $Q_{\exists
a_{m}\wedge\neg t_{c}}:=Q_{\exists a_{m}}\setminus Q_{\exists a_{m}\wedge
t_{c}}$.

By definition of $Q_{\exists a_{m}\wedge\neg t_{c}}$ we have $t_{c}\notin
L(\mathcal{A}_{Q_{\exists a_{m}\wedge\neg t_{c}}})$ and therefore
$L(\mathcal{A}_{Q_{\exists a_{m}\wedge\neg t_{c}}})\cap
T^{\omega}_{\\{c,a_{m}\\}}\subseteq
T^{\omega}_{\\{c,a_{m}\\}}\setminus\\{t_{c}\\}$. The language
$T^{\omega}_{\\{c,a_{m}\\}}\setminus\\{t_{c}\\}$ is not finitely ambiguous by
Corollary 19 (2). $L(\mathcal{A}_{Q_{\exists a_{m}\wedge\neg t_{c}}})$ is
finitely ambiguous (by Corollary 12) and since $T^{\omega}_{\\{c,a_{m}\\}}$ is
unambiguous we conclude that $L(\mathcal{A}_{Q_{\exists a_{m}\wedge\neg
t_{c}}})\cap T^{\omega}_{\\{c,a_{m}\\}}$ is finitely ambiguous, by Corollary
9. Therefore, by Lemma 13, there is a tree $t^{\prime}\in
T^{\omega}_{\\{c,a_{m}\\}}\setminus\\{t_{c}\\}=L_{\exists a_{m}}\cap
T^{\omega}_{\\{c,a_{m}\\}}$ such that $t^{\prime}\notin
L(\mathcal{A}_{Q_{\exists a_{m}\wedge\neg t_{c}}})$, and since $L_{\exists
a_{m}}\cap T^{\omega}_{\\{c,a_{m}\\}}\subseteq L(\mathcal{A}_{Q_{\exists
a_{m}}})=L(\mathcal{A}_{Q_{\exists a_{m}\wedge t_{c}}})\cup
L(\mathcal{A}_{Q_{\exists a_{m}\wedge\neg t_{c}}})$ we conclude that
$t^{\prime}\in L(\mathcal{A}_{Q_{\exists a_{m}\wedge t_{c}}})$.

Define $Q^{\prime}:=\\{q\in R[1]\mid t^{\prime}\in L(\mathcal{A}_{q})\\}$ and
$R^{\prime}:=\\{(q_{1},q_{2})\in R\mid q_{1}\in Q^{\prime}\\}$. Since
$t^{\prime}\in L_{\exists a_{m}}\cap T^{\omega}_{\\{c,a_{m}\\}}$, we conclude
that $\\{t\in T^{\omega}_{\Sigma}\mid Tree(c,t^{\prime},t)\in L_{\neg
a_{1}\vee\dots\vee\neg a_{m}}\\}=L_{\neg a_{1}\vee\dots\vee\neg a_{m-1}}$.
Therefore, $L(\mathcal{A}_{R^{\prime}[2]})=L_{\neg a_{1}\vee\dots\vee\neg
a_{m-1}}$, and by induction assumption we now obtain that:
$|ACC(\mathcal{A}_{R^{\prime}[2]},t_{c})|\geq m-1$.

For each computation $\phi\in ACC(\mathcal{A}_{R^{\prime}[2]},t_{c})$ we will
construct a computation $g(\phi)\in ACC(\mathcal{A},t_{c})$, as following. Let
$q_{2}:=\phi(\epsilon)$. By the definition of $R^{\prime}$, there is
$(q_{1},q_{2})\in R^{\prime}$ such that $t^{\prime}\in
L(\mathcal{A}_{q_{1}})$. Since $t^{\prime}\in L(\mathcal{A}_{Q_{\exists
a_{m}\wedge t_{c}}})$ we have $t_{c}\in L(\mathcal{A}_{q_{1}})$, and therefore
there is a computation $\phi_{c}\in ACC(\mathcal{A}_{q_{1}},t_{c})$. Let
$q_{i}\in Q_{I}$ such that $(q_{i},c,q_{1},q_{2})\in\delta$. By defining
$g(\phi):=Tree(q_{i},\phi_{c},\phi)$ we obtain that $g(\phi)\in
ACC(\mathcal{A},t_{c})$, as requested.

Let $\Phi:=\\{g(\phi)\mid\phi\in ACC(\mathcal{A}_{R^{\prime}[2]},t_{c})\\}$.
$g(\phi)_{\geq r}=\phi$ and therefore $g$ is injective, and we conclude that
$|{\Phi}|=|ACC(\mathcal{A}_{R^{\prime}[2]},t_{c})|\geq m-1$.

We now need to find an additional computation $\phi\in ACC(\mathcal{A},t_{c})$
such that $\phi\notin\Phi$, resulting $|ACC(\mathcal{A},t_{c})|\geq m$.

Let $Q_{\exists a_{1}\wedge\dots\wedge\exists a_{m-1}}:=\\{q\in R[2]\mid
L(\mathcal{A}_{q})\cap L_{\exists a_{1}\wedge\dots\wedge\exists
a_{m-1}}\neq\emptyset\\}$ and let $Q_{t_{c}\wedge\exists
a_{1}\wedge\dots\wedge\exists a_{m-1}}:=\\{q\in Q_{\exists
a_{1}\wedge\dots\wedge\exists a_{m-1}}\mid t_{c}\in L(\mathcal{A}_{q})\\}$ and
$Q_{\neg t_{c}\wedge\exists a_{1}\wedge\dots\wedge\exists a_{m-1}}:=Q_{\exists
a_{1}\wedge\dots\wedge\exists a_{m-1}}\setminus Q_{t_{c}\wedge\exists
a_{1}\wedge\dots\wedge\exists a_{m-1}}$.

######  Claim 28.

There is a full-binary tree $t^{\prime\prime}\in L_{\exists
a_{1}\wedge\dots\wedge\exists a_{m-1}}\cap
T^{\omega}_{\\{c,a_{1},\dots,a_{m-1}\\}}$ such that $t^{\prime\prime}\in
L(\mathcal{A}_{Q_{t_{c}\wedge\exists a_{1}\wedge\dots\wedge\exists a_{m-1}}})$
and $t^{\prime\prime}\notin L(\mathcal{A}_{Q_{\neg t_{c}\wedge\exists
a_{1}\wedge\dots\wedge\exists a_{m-1}}})$.

######  Proof 5.3 (Proof).

By the definition of $R[2]$ we have $L_{\exists a_{1}\wedge\dots\wedge\exists
a_{m-1}}\cap T^{\omega}_{\\{c,a_{1},\dots,a_{m-1}\\}}\subseteq
L(\mathcal{A}_{R[2]})$ and therefore by the definition of
$Q_{t_{c}\wedge\exists a_{1}\wedge\dots\wedge\exists a_{m-1}}$ and $Q_{\neg
t_{c}\wedge\exists a_{1}\wedge\dots\wedge\exists a_{m-1}}$, we have
$L_{\exists a_{1}\wedge\dots\wedge\exists a_{m-1}}\cap
T^{\omega}_{\\{c,a_{1},\dots,a_{m-1}\\}}\subseteq
L(\mathcal{A}_{Q_{t_{c}\wedge\exists a_{1}\wedge\dots\wedge\exists
a_{m-1}}})\cup L(\mathcal{A}_{Q_{\neg t_{c}\wedge\exists
a_{1}\wedge\dots\wedge\exists a_{m-1}}})$.

Assume, for the sake of contradiction, that the claim does not hold. Then, we
obtain $L_{\exists a_{1}\wedge\dots\wedge\exists a_{m-1}}\cap
T^{\omega}_{\\{c,a_{1},\dots,a_{m-1}\\}}\subseteq L(\mathcal{A}_{Q_{\neg
t_{c}\wedge\exists a_{1}\wedge\dots\wedge\exists a_{m-1}}})$. We have
$t_{c}\notin L(\mathcal{A}_{Q_{\neg t_{c}\wedge\exists
a_{1}\wedge\dots\wedge\exists a_{m-1}}})$, and therefore by Lemma 26 we
conclude that $L(\mathcal{A}_{Q_{\neg t_{c}\wedge\exists
a_{1}\wedge\dots\wedge\exists a_{m-1}}})$ is not finitely ambiguous – a
contradiction to $\mathcal{A}$ being finitely ambiguous.

Let $t^{\prime\prime}$ be a tree as in Claim 28. We have $t^{\prime\prime}\in
L_{\exists a_{1}\wedge\dots\wedge\exists a_{m-1}}\cap
T^{\omega}_{\\{c,a_{1},\dots,a_{m-1}\\}}$, and therefore
$Tree(c,t_{c},t^{\prime\prime})\in L_{\neg a_{1}\vee\dots\vee\neg
a_{m}}=L(\mathcal{A})$, and there is a computation $\phi\in
ACC(\mathcal{A},Tree(c,t_{c},t^{\prime\prime}))$. Let $q:=\phi(r)$. By
definition of $t^{\prime\prime}$, we have $q\in Q_{t_{c}\wedge\exists
a_{1}\wedge\dots\wedge\exists a_{m-1}}$ and therefore $t_{c}\in
L(\mathcal{A}_{q})$. Let $\phi_{c}\in ACC(\mathcal{A}_{q},t_{c})$, and let
$\phi^{\prime}$ be the computation obtained from $\phi$ by grafting $\phi_{c}$
on $r$. We conclude that $\phi^{\prime}\in ACC(\mathcal{A},t_{c})$.

Assume, for the sake of contradiction, that $\phi^{\prime}\in{\Phi}$, and let
$q_{1}:=\phi^{\prime}(l)$ and $q_{2}:=\phi^{\prime}(r)$. We have
$t^{\prime}\in L(\mathcal{A}_{q_{1}})$ (by definition of $|\Phi|$) and
$t^{\prime\prime}\in L(\mathcal{A}_{q_{2}})$ (by definition of
$\phi^{\prime}$). Therefore, by grafting computations $\phi_{t^{\prime}}\in
ACC(\mathcal{A}_{q_{1}},t^{\prime})$ and $\phi_{t^{\prime\prime}}\in
ACC(\mathcal{A}_{q_{2}},t^{\prime\prime})$ to the left and right children of
the root of $t_{c}$, respectively, we obtain
$Tree(c,t^{\prime},t^{\prime\prime})\in L(\mathcal{A})$. That is a
contradiction, since $t^{\prime}$ contains an $a_{m}$ labeled node, and
$t^{\prime\prime}$ contains $a_{1},\dots,a_{m-1}$ labeled nodes, and therefore
$Tree(c,t^{\prime},t^{\prime\prime})\notin L_{\neg a_{1}\vee\dots\vee\neg
a_{m}}$.

We conclude that $\phi^{\prime}\notin{\Phi}$, and therefore
$|ACC(\mathcal{A},t_{c})|\geq 1+|{\Phi}|=1+(m-1)=m$.

##  6\. Finitely Ambiguous Languages

Let $\Sigma=\\{a_{1},a_{2},c\\}$. We define the following languages over
$\Sigma$:

  * •

For $k,m\in\mathbb{N}$ such that $k<m$, we define $L_{k,m}$ as the set of
trees that are obtained from $t_{c}$ by grafting a tree $t^{\prime}\in L_{\neg
a_{1}\vee\neg a_{2}}$ on node $l^{k}r$, and grafting $t_{a_{1}}$ on node
$l^{m}$.

  * •

For $m\in\mathbb{N}$ we define $L_{m}:=\cup_{k<m}L_{k,m}$.

  * •

$L^{fa}:=\cup_{m\in\mathbb{N}}L_{m}$.

In this section we prove the following proposition:

######  Proposition 29.

The degree of ambiguity of $L^{fa}$ is finite.

The proposition follows from Lemma 30 and Lemma 34 proved below.

######  Lemma 30.

There is a finitely ambiguous automaton that accepts $L^{fa}$

######  Proof 6.1.

On a tree $t\in L_{m}$ the automaton “guesses” a position $i<m$, checks that
$t_{\geq l^{i}r}\in L_{\neg a_{1}\vee\neg a_{2}}$ (using a 2-ambiguous
automaton), checks that $t_{\geq l^{j}r}=t_{c}$ for all $j\neq i\wedge j<m$,
and checks that $t_{\geq l^{m}}=t_{a_{1}}$ (using deterministic automata).
Below, a more detailed proof is given.

First, notice that there are deterministic PTA $\mathcal{A}_{c}$,
$\mathcal{A}_{a_{1}}$, $\mathcal{A}_{\neg a_{1}}$ and $\mathcal{A}_{\neg
a_{2}}$ that accepts languages $\\{t_{c}\\}$, $\\{t_{a_{1}}\\}$, $L_{\neg
a_{1}}$ and $L_{\neg a_{2}}$, respectively.

By Lemma 8, there is a $2$-ambiguous automaton $\mathcal{A}_{\neg
a_{1}\vee\neg a_{2}}$ that accepts the language $L_{\neg a_{1}\vee\neg
a_{2}}:=L_{\neg a_{1}}\cup L_{\neg a_{2}}$.

We will construct an automaton
$\mathcal{B}:=(Q_{\mathcal{B}},\Sigma_{\mathcal{B}},Q_{I_{\mathcal{B}}},\delta_{\mathcal{B}},\mathbb{C}_{\mathcal{B}})$
that accepts $L^{fa}$.

  * •

$Q_{\mathcal{B}}$ is defined as the union of states of $\mathcal{A}_{a_{1}}$,
$\mathcal{A}_{c}$ and $\mathcal{A}_{\neg a_{1}\vee\neg a_{2}}$, along with
additional states $q_{1},q_{2}$.

  * •

$\Sigma_{\mathcal{B}}:=\\{a_{1},a_{2},c\\}$

  * •

$Q_{I_{\mathcal{B}}}:=\\{q_{1}\\}$

  * •

$\delta_{\mathcal{B}}$ will consists of the transitions of
$\mathcal{A}_{a_{1}}$, $\mathcal{A}_{c}$ and $\mathcal{A}_{\neg a_{1}\vee\neg
a_{2}}$, along with additional transitions:

    * –

$(q_{1},c,q_{1},p)\in\delta_{\mathcal{B}}$ for $p$ an initial state in
$\mathcal{A}_{c}$

    * –

$(q_{1},c,q_{2},p)\in\delta_{\mathcal{B}}$ for $p$ an initial state in
$\mathcal{A}_{\neg a_{1}\vee\neg a_{2}}$

    * –

$(q_{2},c,q_{2},p)\in\delta_{\mathcal{B}}$ for $p$ an initial state in
$\mathcal{A}_{c}$

    * –

$(q_{2},a_{1},p,p)\in\delta_{\mathcal{B}}$ for $p$ an initial state in
$\mathcal{A}_{a_{1}}$

  * •

$\mathbb{C}_{\mathcal{B}}(q_{1}):=1$, $\mathbb{C}_{\mathcal{B}}(q_{2}):=1$,
and for other states, the assigned color would be the same as in the automaton
the state has originated from ($\mathcal{A}_{a_{1}}$, $\mathcal{A}_{c}$ or
$\mathcal{A}_{\neg a_{1}\vee\neg a_{2}}$)

It is easy to see that $L(\mathcal{B})=L^{fa}$.

Let $t\in L(\mathcal{B})$. By definition of $L^{fa}$, there is
$m\in\mathbb{N}$ such that $t\in L_{m}$. If $\phi$ is an accepting computation
on $t$, then $\phi$ assigns to the first $m+2$ nodes on the leftmost branch
the sequence $\underbrace{q_{1},\dots,q_{1}}_{\text{$i$
times}}\cdot\underbrace{q_{2},\dots,q_{2}}_{\text{$m-i+1$ times}}\cdot
q_{a_{1}}$ for some $i\in\\{1,\dots,m\\}$, where $q_{a_{1}}$ is the initial
state of $\mathcal{A}_{a_{1}}$ (total $m$ possibilities). $\phi$ assigns to
$l^{j}\cdot r$ the initial state of $\mathcal{A}_{c}$ if $j<i-1$ or $i-1<j<m$;
the initial state of $\mathcal{A}_{\neg a_{1}\vee\neg a_{2}}$ if $j=i-1$; and
the initial state of $\mathcal{A}_{a_{1}}$ if $j\geq m$. Since
$\mathcal{A}_{c}$ and $\mathcal{A}_{a_{1}}$ are deterministic and
$\mathcal{A}_{\neg a_{1}\vee\neg a_{2}}$ is 2-ambiguous, the number of
accepting computations on $t$ is at most $2m$, hence, finite.

######  Lemma 31.

Let $L$ be a tree language such that $L_{m}\subseteq L\subseteq L^{fa}$. Then,
$L$ is not $m-1$ ambiguous.

######  Proof 6.2.

Let $\mathcal{A}$ be an automaton with states $Q$ that accepts $L$, and assume
$\mathcal{A}$ is finitely ambiguous. Define a set $Q^{\prime}\subseteq Q$ by
$Q^{\prime}:=\\{\phi(l^{i}r)\mid i<m\wedge\exists t\in L:\phi\in
ACC(\mathcal{A},t)\\}$ and $Q_{\exists a_{1}}:=\\{q\in Q^{\prime}\mid
L_{\exists a_{1}}\cap L(\mathcal{A}_{q})\neq\emptyset\\}$, and let
$Q_{t_{c}\wedge\exists a_{1}}:=\\{q\in Q_{\exists a_{1}}\mid t_{c}\in
L(\mathcal{A}_{q})\\}$ and $Q_{\neg t_{c}\wedge\exists a_{1}}:=Q_{\exists
a_{1}}\setminus Q_{t_{c}\wedge\exists a_{1}}$.

Relying on the fact that $T^{\omega}_{\\{c,a_{1}\\}}\setminus\\{t_{c}\\}$ is
not finitely ambiguous (by Corollary 19 (2)), we derive the following claim:

######  Claim 32.

There is a tree $t_{\exists
a_{1}}\in\big{(}T^{\omega}_{\\{c,a_{1}\\}}\setminus\\{t_{c}\\}\big{)}\cap\big{(}L(\mathcal{A}_{Q_{t_{c}\wedge\exists
a_{1}}})\setminus L(\mathcal{A}_{Q_{\neg t_{c}\wedge\exists a_{1}}})\big{)}$.
$\blacksquare$

Recall that $t^{m}$ is the tree that is obtained from $t_{c}$ by grafting
$t_{a_{1}}$ on node $l^{m}$. For each $i<m$, define $t^{m}_{i}$ as the tree
that is obtained from $t^{m}$ by grafting $t_{\exists a_{1}}$ on node
$l^{i}r$. It is clear that $t^{m}_{i}\in L(\mathcal{A})$, and therefore there
is an accepting computation $\phi_{i}$ of $\mathcal{A}$ on $t^{m}_{i}$.

$t_{\exists a_{1}}\in L(\mathcal{A}_{Q_{t_{c}\wedge\exists a_{1}}})\setminus
L(\mathcal{A}_{Q_{\neg t_{c}\wedge\exists a_{1}}})$ and since $t_{\exists
a_{1}}\in\mathcal{A}_{\phi_{i}(l^{i}r)}$ we conclude that $\phi_{i}(l^{i}r)\in
Q_{t_{c}\wedge\exists a_{1}}$ and therefore $t_{c}\in
L(\mathcal{A}_{\phi_{i}(l^{i}r)})$. Let $\phi^{c}_{i}\in
ACC(\mathcal{A}_{\phi_{i}(l^{i}r)},t_{c})$, and construct a computation
$\phi_{i}^{\prime}$ from $\phi_{i}$ by grafting $\phi^{c}_{i}$ on $l^{i}r$.
This tree that is obtained from $t^{m}_{i}$ by grafting $t_{c}$ on $l^{i}r$ is
the tree $t^{m}$ and therefore $\phi_{i}^{\prime}\in ACC(\mathcal{A},t^{m})$.

We are going to show that for all $i<j<m$, the computations
$\phi_{i}^{\prime},\phi_{j}^{\prime}\in ACC(\mathcal{A},t^{m})$ are different.
Assume towards a contradiction $\phi_{i}^{\prime}=\phi_{j}^{\prime}$ and let
$\widehat{\phi}:=\phi_{i}^{\prime}$. Define $p_{i}:=\widehat{\phi}(l^{i}r)$,
$p_{j}:=\widehat{\phi}(l^{j}r)$, and let $\phi_{p_{i}}\in
ACC(\mathcal{A}_{p_{i}},t_{\exists a_{1}})$ and $\phi_{p_{j}}\in
ACC(\mathcal{A}_{p_{2}},t_{\exists a_{1}})$. Construct $t^{\prime}$ from
$t^{m}$ by grafting $t_{\exists a_{1}}$ on nodes $l^{i}r$ and $l^{j}r$, and
construct $\phi^{\prime}$ from $\widehat{\phi}$ by grafting $\phi_{p_{i}}$ on
$l^{i}r$ and $\phi_{p_{2}}$ on $l^{j}r$. It follows that $\phi^{\prime}$ is an
accepting computation of $\mathcal{A}$ on $t^{\prime}$. That is a
contradiction, since $t^{\prime}\notin L^{fa}$ (since $t^{\prime}_{\geq
l^{j}r}=t^{\prime}_{\geq l^{i}r}=t_{\exists a_{1}}\neq t_{c}$) and therefore
$t^{\prime}\notin L$ (since $L\subseteq L^{fa}$). We conclude that there are
at least $m$ different accepting computations of $\mathcal{A}$ on $t^{m}$.

######  Remark 33.

The language $L_{m}$ is $2m$ ambiguous but not $m-1$ ambiguous. This implies
that the hierarchy of ambiguous languages is infinite. The point of the more
complex construction in Section 5 is to show that this hierarchy is populated
at every level.

######  Lemma 34.

$L^{fa}$ is not boundedly ambiguous

######  Proof 6.3.

$\forall m\in\mathbb{N}:L_{m}\subseteq L^{fa}$, and therefore from Lemma 31 it
follows that $L^{fa}$ is not $(m-1)$-ambiguous. That is, $L^{fa}$ is not
boundedly ambiguous.

##  7\. Uncountably Ambiguous Languages

In this section we introduce a scheme for obtaining uncountably ambiguous
languages from languages that are not boundedly ambiguous. We then use this
scheme to obtain natural examples of uncountably ambiguous tree languages.

Let $L^{\neg ba}$ be an arbitrary regular tree language over alphabet $\Sigma$
that is not boundedly ambiguous, and let $L_{0}$ be an arbitrary regular tree
language over alphabet $\Sigma$ such that $L_{0}\cap L^{\neg ba}=\emptyset$.
Let $c\in\Sigma$ and define a language $\mathfrak{L}[L_{0},L^{\neg ba}]$ over
alphabet $\Sigma$: $t\in\mathfrak{L}[L_{0},L^{\neg ba}]$ iff the following
conditions hold:

  * •

$\forall v\in l^{*}:t(v)=c$

  * •

There is an infinite set $I\subseteq\mathbb{N}$ such that $\forall i\in
I:t_{\geq l^{i}\cdot r}\in L^{\neg ba}$ and $\forall i\not\in I:t_{\geq
l^{i}\cdot r}\in L_{0}$.

######  Proposition 35.

The degree of ambiguity of $\mathfrak{L}[L_{0},L^{\neg ba}]$ is
$2^{\aleph_{0}}$.

######  Proof 7.1.

Let $\mathcal{A}=(Q,\Sigma,Q_{I},\delta,\mathbb{C})$ be a PTA that accepts
$\mathfrak{L}[L_{0},L^{\neg ba}]$. We will show that
$da(\mathcal{A})=2^{\aleph_{0}}$.

Let $Q^{\prime}:=\\{\phi(u)\mid u\in l^{*}\cdot r$ and $\exists t:\phi\in
ACC(\mathcal{A},t)\\}$, and define $Q_{\mathit{unamb}\wedge\neg
L_{0}}:=\\{q\in Q^{\prime}\mid\mathcal{A}_{q}$ is unambiguous and
$L(\mathcal{A}_{q})\cap L_{0}=\emptyset\\}$.

######  Claim 36.

$L(\mathcal{A}_{Q_{\mathit{unamb}\wedge\neg L_{0}}})\subseteq L^{\neg ba}$.

######  Proof 7.2 (Proof).

Assume, for the sake of contradiction, that there is a tree $t\in
L(\mathcal{A}_{Q_{\mathit{unamb}\wedge\neg L_{0}}})$ such that $t\notin
L^{\neg ba}$. By definition of $Q_{\mathit{unamb}\wedge\neg L_{0}}$ we
conclude that $t\notin L_{0}$.

Let $q\in Q_{\mathit{unamb}\wedge\neg L_{0}}$ such that $t\in
L(\mathcal{A}_{q})$ and let $\phi\in ACC(\mathcal{A}_{q},t)$. Recall that
$q\in Q^{\prime}$ (since $Q_{\mathit{unamb}\wedge\neg L_{0}}\subseteq
Q^{\prime}$) and therefore there is a tree $t^{\prime}\in L(\mathcal{A})$, a
computation $\phi^{\prime}\in ACC(\mathcal{A},t^{\prime})$ and a node $u\in
l^{*}\cdot r$ such that $\phi^{\prime}(u)=q$. By the grafting lemma we
conclude that $\phi^{\prime}[\phi/u]$ is an accepting computation of
$\mathcal{A}$ on $t^{\prime}[t/u]$. Therefore, $t^{\prime}[t/u]\in
L(\mathcal{A})$ for $t\notin L^{\neg ba}\cup L_{0}$ – a contradiction to the
definition of $\mathcal{A}$.

Notice that $L(\mathcal{A}_{Q_{\mathit{unamb}\wedge\neg L_{0}}})$ is boundedly
ambiguous by Corollary 9 (as a finite union of unambiguous languages), and
since $L^{\neg ba}$ is not boundedly ambiguous we conclude that
$da(L(\mathcal{A}_{Q_{\mathit{unamb}\wedge\neg L_{0}}}))\neq da(L^{\neg ba})$.
By Claim 36 we obtain $L(\mathcal{A}_{Q_{\mathit{unamb}\wedge\neg
L_{0}}})\subseteq L^{\neg ba}$, and applying Lemma 13 we conclude that there
is a tree $t_{\neg ba}\in L^{\neg ba}$ such that $t_{\neg ba}\notin
L(\mathcal{A}_{Q_{\mathit{unamb}\wedge\neg L_{0}}})$.

Let $c\in\Sigma$ be as in the definition of $\mathfrak{L}[L_{0},L^{\neg ba}]$,
and let $t_{c}$ be a tree where all nodes are labeled by $c$. Let
$A:=l^{*}\cdot r$ be an antichain, and define $t^{\prime\prime}:=t_{c}[t_{\neg
ba}/A]$. By the definition of $\mathcal{A}$ it is clear that
$t^{\prime\prime}\in L(\mathcal{A})$. Let $\phi^{\prime\prime}\in
ACC(\mathcal{A},t^{\prime\prime})$, and let $B:=\\{u\in A\mid
L(\mathcal{A}_{\phi^{\prime\prime}(u)})\cap L_{0}\neq\emptyset\\}$.

For each $u\in B$ there is a tree $t_{u}\in L_{0}$ and a computation
$\phi_{u}\in ACC(\mathcal{A}_{\phi^{\prime\prime}(u)},t_{u})$. Therefore, by
the grafting lemma, we conclude that the tree $t^{\prime\prime\prime}$ that is
obtained from $t^{\prime\prime}$ by grafting $t_{u}$ on each node $u\in B$ is
in $L(\mathcal{A})$.

Assume, for the sake of contradiction, that $A\setminus B$ is finite. By
definition of $t^{\prime\prime\prime}$, for each $i\in\mathbb{N}$ such that
$u:=l^{i}\cdot r\in B$ we have $t^{\prime\prime\prime}_{\geq l^{i}\cdot
r}=t_{u}\in L_{0}$. Therefore, $|\\{i\in\mathbb{N}\mid
t^{\prime\prime\prime}_{\geq l^{i}\cdot r}\in L^{\neg ba}\\}|=|\\{u\in A\mid
t^{\prime\prime\prime}_{\geq u}\in L^{\neg ba}\\}|=|\\{u\in A\setminus B\mid
t^{\prime\prime\prime}_{\geq u}\in L^{\neg ba}\\}|=|A\setminus B|<\aleph_{0}$,
and by definition of $\mathfrak{L}[L_{0},L^{\neg ba}]$ we conclude that
$t^{\prime\prime\prime}\notin\mathfrak{L}[L_{0},L^{\neg ba}]$ – a
contradiction to the definition of $\mathcal{A}$.

$A\setminus B$ is infinite, and therefore there is a state $q$ and an infinite
set $\widehat{A}\subseteq A\setminus B$ such that $\phi^{\prime\prime}(u)=q$
for all $u\in\widehat{A}$. Recall that $\forall
u\in\widehat{A}:t^{\prime\prime}_{\geq u}=t_{\neg ba}$. Notice that for each
$u\in\widehat{A}$ we have $u\notin B$, and by definition of $B$ we obtain
$L(\mathcal{A}_{\phi^{\prime\prime}(u)})\cap L_{0}=L(\mathcal{A}_{q})\cap
L_{0}=\emptyset$. Since $t_{\neg ba}\notin
L(\mathcal{A}_{Q_{\mathit{unamb}\wedge\neg L_{0}}})$ we conclude that $q\notin
Q_{\mathit{unamb}\wedge\neg L_{0}}$ – hence, $\mathcal{A}_{q}$ is ambiguous.

Let $t_{\mathit{amb}}\in L(\mathcal{A}_{q})$ be a tree having at least two
accepting computations $\phi_{1},\phi_{2}\in
ACC(\mathcal{A}_{q},t_{\mathit{amb}})$. Let
$\widehat{t}:=t^{\prime\prime}[t_{\mathit{amb}}/{\widehat{A}}]$, and
$\widehat{\phi}:=\phi[\phi_{1}/{\widehat{A}}]$. By the grafting lemma we
obtain $\widehat{\phi}\in ACC(\mathcal{A},\widehat{t})$. For each
$A^{\prime}\subseteq\widehat{A}$, define a computation
$\phi_{A^{\prime}}:=\widehat{\phi}[\phi_{2}/{A^{\prime}}]$. Notice that
$\phi_{A^{\prime}}\in ACC(\mathcal{A},\widehat{t})$ (by the grafting lemma)
and that $\forall A_{1},A_{2}\subseteq\widehat{A}:A_{1}\neq
A_{2}\rightarrow\phi_{A_{1}}\neq\phi_{A_{2}}$ (since $\phi_{1}\neq\phi_{2}$).
Therefore, $|ACC(\mathcal{A},\widehat{t})|\geq|\\{A^{\prime}\mid
A^{\prime}\subseteq\widehat{A}\\}|=2^{\aleph_{0}}$, and
$da(\mathcal{A})=2^{\aleph_{0}}$, as requested.

We will now introduce a couple of definitions, and present three natural
examples of infinite tree languages that are not countably ambiguous.

[Characteristic tree] The characteristic tree of
$U_{1},\dots,U_{n}\subseteq\\{l,r\\}^{*}$ is a $\\{0,1\\}^{n}$-labeled tree
$t[U_{1},\dots,U_{n}]$ such that
$t[U_{1},\dots,U_{n}](u):=(b_{1},\dots,b_{n})$ where $b_{i}=1$ iff $u\in
U_{i}$ for each $1\leq i\leq n$.

For a set $U\subseteq\\{l,r\\}^{*}$ we define $U\downarrow$ as the downward
closure of $U$.

A set $X\subseteq\\{l,r\\}^{*}$ is called perfect if $X\neq\emptyset$ and
$\forall u\in X:\exists v_{1},v_{2}\in X$ such that $v_{1}$ and $v_{2}$ are
incomparable and greater than $u$.

######  Proposition 37.

The following regular languages are not countably ambiguous:

  1. (1)

$L_{X\subseteq Y\downarrow}:=\\{t[X,Y]\mid X\subseteq Y\downarrow\\}$ – “for
each node in $X$ there is a greater or equal node in $Y$.”

  2. (2)

$L_{\mathit{no-max}}:=\\{t[X]\mid X$ has no maximal element$\\}$ – “for each
node in $X$ there is a greater node in $X$.”

  3. (3)

$L_{\mathit{perf}}:=\\{t[X]\mid X$ is perfect $\\}$ – “for each node in $X$
there are at least two greater incomparable nodes in $X$.”

In the rest of this section we will prove Proposition 37.

######  Proof 7.3 (Proof of Proposition 37(1)).

Let $L_{\mathit{left}}:=\\{t[X,Y]\mid X=l^{*}$ and $Y\cap l^{*}=\emptyset\\}$.
It is easy to see that $L_{\mathit{left}}$ can be accepted by a deterministic
PTA, and therefore $da(L_{\mathit{left}})=1$.

By Lemma 8 we conclude that $da(L_{X\subseteq Y\downarrow}\cap
L_{\mathit{left}})\leq da(L_{X\subseteq Y\downarrow})\cdot
da(L_{\mathit{left}})=da(L_{X\subseteq Y\downarrow})$. We will show that
$L_{X\subseteq Y\downarrow}\cap L_{\mathit{left}}$ is not countably ambiguous.
By the above inequality, this implies that $L_{X\subseteq Y\downarrow}$ is not
countably ambiguous.

######  Claim 38.

Let $L_{X=\emptyset,Y\neq\emptyset}:=\\{t[X,Y]\mid X=\emptyset$ and
$Y\neq\emptyset\\}$. Then $t^{\prime}\in L_{X\subseteq Y\downarrow}\cap
L_{\mathit{left}}$ iff the following conditions hold:

  1. (1)

$\forall u\in l^{*}:t^{\prime}(u)=(1,0)$

  2. (2)

There is an infinite set $I\subseteq\mathbb{N}$ such that:

    1. (a)

If $i\in I$ then $t^{\prime}_{\geq l^{i}\cdot r}\in
L_{X=\emptyset,Y\neq\emptyset}$

    2. (b)

If $i\notin I$ then $t^{\prime}_{\geq l^{i}\cdot
r}\in\\{t[\emptyset,\emptyset]\\}$

######  Proof 7.4 (Proof).

$\Rightarrow$: Let $t^{\prime}\in L_{X\subseteq Y\downarrow}\cap
L_{\mathit{left}}$. By definition of $L_{\mathit{left}}$ it is clear that the
condition (1) holds, and that for each $i\in\mathbb{N}:t^{\prime}_{\geq
v^{i}\cdot l}\in L_{X=\emptyset,Y\neq\emptyset}$ or $t^{\prime}_{\geq
v^{i}\cdot l}=t[\emptyset,\emptyset]$. Assume, for the sake of contradiction,
that the set $\\{i\in\mathbb{N}\mid t^{\prime}_{\geq v^{i}\cdot l}\in
L_{X=\emptyset,Y\neq\emptyset}\\}$ is finite. Therefore, by the second
condition, there is an index $k\in\mathbb{N}$ such that $\forall i\geq
k:t^{\prime}_{\geq v^{i}\cdot l}=t[\emptyset,\emptyset]$. Let $u:=l^{k}$. By
the definition of $L_{\mathit{left}}$ we have $u\in X$, and for each $v\geq u$
we have either $t^{\prime}(v)=(1,0)$ if $v\in l^{*}$, or $t^{\prime}(v)=(0,0)$
otherwise. Hence, $\forall v\geq u:v\notin Y$, in contradiction to
$t^{\prime}\in L_{X\subseteq Y\downarrow}$.

$\Leftarrow$: Assume that the conditions hold for $t^{\prime}$. It is easy to
see that $t^{\prime}\in L_{\mathit{left}}$. We will show that $t^{\prime}\in
L_{X\subseteq Y\downarrow}$. Assume, for the sake of contradiction, that there
is a node $u\in X$ such that $v\notin Y$ for each node $v\geq u$. Since all
nodes in $X$ are in $l^{*}$ we conclude that there is $i\in\mathbb{N}$ such
that $u=l^{i}$. Notice that the set $I\subseteq\mathbb{N}$ is infinite, and
therefore there is $j>i$ such that $t^{\prime}_{\geq l^{j}\cdot r}\in
L_{X=\emptyset,Y\neq\emptyset}$. Therefore, there is a node $v\geq l^{j}\cdot
r>l^{i}=u$ such that $v\in Y$ – a contradiction.

Observe that the language $L_{X=\emptyset,Y\neq\emptyset}:=\\{t[X,Y]\mid
X=\emptyset$ and $Y\neq\emptyset\\}$ can be considered as a tree language over
alphabet $\\{0\\}\times\\{0,1\\}$, and that
$L_{X=\emptyset,Y\neq\emptyset}=T^{\omega}_{\\{0\\}\times\\{0,1\\}}\setminus\\{t[\emptyset,\emptyset]\\}$.
Therefore, by Corollary 19(2) we conclude that
$L_{X=\emptyset,Y\neq\emptyset}$ is not finitely ambiguous.

Notice that by Claim 38 we obtain $L_{X\subseteq Y\downarrow}\cap
L_{\mathit{left}}=\mathfrak{L}[L_{0},L^{\neg ba}]$, for
$L_{0}=\\{t[\emptyset,\emptyset]\\}$ and $L^{\neg
ba}=L_{X=\emptyset,Y\neq\emptyset}$. Therefore, applying Proposition 35 we
conclude that $L_{X\subseteq Y\downarrow}\cap L_{\mathit{left}}$ is not
countably ambiguous.

To prove Proposition 37(2), we will first prove the following lemma:

######  Lemma 39.

$L_{\mathit{no-max}}$ is not finitely ambiguous.

######  Proof 7.5.

Let $\mathcal{A}=(Q,\Sigma,Q_{I},\delta,\mathbb{C})$ be a PTA that accepts
$L_{\mathit{no-max}}$. Let $Q^{\prime}:=\\{q\in Q\mid\exists q_{i}\in
Q_{I}\exists q^{\prime}\in Q:(q_{i},1,q,q^{\prime})\in\delta$ and
$t[\emptyset]\in L(\mathcal{A}_{q^{\prime}})\\}$.

######  Claim 40.

Define $L_{\neg\emptyset}:=T^{\omega}_{\Sigma}\setminus\\{t[\emptyset]\\}$.
Then:

  1. (1)

$L_{\mathit{no-max}}\setminus\\{t[\emptyset]\\}\subseteq
L(\mathcal{A}_{Q^{\prime}})$

  2. (2)

$L(\mathcal{A}_{Q^{\prime}})\subseteq L_{\neg\emptyset}$

######  Proof 7.6 (Proof).

(1) Let $t^{\prime}\in L_{\mathit{no-max}}\setminus\\{t[\emptyset]\\}$, and
let $t_{\epsilon}:=t[\\{\epsilon\\}]$ (that is, $t_{\epsilon}(\epsilon):=1$,
and $\forall u\neq\epsilon:t_{\epsilon}(u):=0$). Let
$t^{\prime\prime}:=t_{\epsilon}[t^{\prime}/l]$. By the definition of
$L_{\mathit{no-max}}$ we obtain $t^{\prime\prime}\in L_{\mathit{no-max}}$.
Therefore, there is a computation $\phi\in ACC(\mathcal{A},t^{\prime\prime})$
such that $\phi(l)\in Q^{\prime}$ and $t^{\prime}\in
L(\mathcal{A}_{\phi(l)})$, as requested.

(2) Assume, for the sake of contradiction, that $t[\emptyset]\in
L(\mathcal{A}_{Q^{\prime}})$. Then there is a transition
$(q_{i},1,q_{1},q_{2})\in\delta$ from an initial state $q_{i}$ such that
$t[\emptyset]\in L(\mathcal{A}_{q_{1}})$ and $t[\emptyset]\in
L(\mathcal{A}_{q_{2}})$. Therefore, we conclude that
$t_{\epsilon}:=t[\\{\epsilon\\}]$ is accepted by $\mathcal{A}$ – a
contradiction to the definition of $L_{\mathit{no-max}}$.

Let $\Sigma:=\\{0,1\\}$. Define a function $F:\Sigma^{*}\rightarrow\Sigma$
such that

$F(\sigma_{1},\dots,\sigma_{m}):=\begin{cases}1&\exists 1\leq i\leq
m:\sigma_{i}=1\\\ 0&\text{otherwise}\end{cases}$

It is easy to see that $F$ is definable by a Moore machine. We show that $F$
reduces $L_{\neg\emptyset}$ to $L(\mathcal{A}_{Q^{\prime}})$.

Notice that $\forall t^{\prime}\in T^{\omega}_{\Sigma}:t^{\prime}\in
L_{\neg\emptyset}\rightarrow\widehat{F}(t^{\prime})\in L_{\mathit{no-
max}}\setminus\\{t[\emptyset]\\}$. Since $L_{\mathit{no-
max}}\setminus\\{t[\emptyset]\\}\subseteq L(\mathcal{A}_{Q^{\prime}})$ (by
Claim 40(1)) we conclude that $\forall t^{\prime}\in
T^{\omega}_{\Sigma}:t^{\prime}\in
L_{\neg\emptyset}\rightarrow\widehat{F}(t^{\prime})\in
L(\mathcal{A}_{Q^{\prime}})$. Conversely, $\forall t^{\prime}\in
T^{\omega}_{\Sigma}:\widehat{F}(t^{\prime})\in L_{\neg\emptyset}\rightarrow
t^{\prime}\in L_{\neg\emptyset}$, and since
$L(\mathcal{A}_{Q^{\prime}})\subseteq L_{\neg\emptyset}$ (by Claim 40(2)) we
obtain $\forall t^{\prime}\in T^{\omega}_{\Sigma}:\widehat{F}(t^{\prime})\in
L(\mathcal{A}_{Q^{\prime}})\rightarrow t^{\prime}\in L_{\neg\emptyset}$.

Therefore, by Lemma 15, we conclude that $da(L(\mathcal{A}_{Q^{\prime}}))\geq
da(L_{\neg\emptyset})$. Notice that
$L_{\neg\emptyset}=T^{\omega}_{\Sigma}\setminus\\{t[\emptyset]\\}$ and by
Corollary 19(2) we obtain $da(L_{\neg\emptyset})\geq\aleph_{0}$. Hence,
$\mathcal{A}_{Q^{\prime}}$ is not finitely ambiguous, and by Corollary 12 we
conclude that $da(\mathcal{A})\geq\aleph_{0}$.

######  Proof 7.7 (Proof of Proposition 37(2)).

Let $L_{l^{*}\cap X=\emptyset}:=\\{t[X]\mid X\cap l^{*}=\emptyset\\}$. It is
easy to construct a deterministic PTA that accepts $L_{l^{*}\cap
X=\emptyset}$, and therefore $da(L_{l^{*}\cap X=\emptyset})=1$.

By Lemma 8 we conclude that $da(L_{\mathit{no-max}}\cap L_{l^{*}\cap
X=\emptyset})\leq da(L_{\mathit{no-max}})\cdot da(L_{l^{*}\cap
X=\emptyset})=da(L_{\mathit{no-max}})$. We will show that $da(L_{\mathit{no-
max}}\cap L_{l^{*}\cap X=\emptyset})=2^{\aleph_{0}}$, and the lemma will
follow.

Notice that $t^{\prime}\in L_{\mathit{no-max}}\cap L_{l^{*}\cap X=\emptyset}$
iff the following hold:

  * •

$\forall u\in l^{*}:t(u)=0$

  * •

$\forall u\in l^{*}\cdot r:t^{\prime}_{\geq u}\in L_{\mathit{no-max}}$

It is easy to see that $L_{\mathit{no-max}}\cap L_{l^{*}\cap
X=\emptyset}=\mathfrak{L}[L_{0},L^{\neg ba}]$ for $L^{\neg ba}:=L_{\mathit{no-
max}}$ (which is not boundedly ambiguous, by Lemma 39) and $L_{0}:=\emptyset$.
Therefore, by Proposition 35 we conclude that $da(L_{\mathit{no-max}}\cap
L_{l^{*}\cap X=\emptyset})=2^{\aleph_{0}}$, as requested.

######  Proof 7.8 (Proof of Proposition 37(3)).

Let $L_{\mathit{contains-}l^{*}}:=\\{t[X]\mid l^{*}\subseteq X\\}$. It is easy
to see that $L_{\mathit{contains-}l^{*}}$ can be accepted by a deterministic
PTA, and therefore $da(L_{\mathit{contains-}l^{*}})=1$. Look at the language
$L_{\mathit{perf}}\cap L_{\mathit{contains-}l^{*}}$. By Lemma 8 we obtain
$da(L_{\mathit{perf}}\cap L_{\mathit{contains-}l^{*}})\leq
da(L_{\mathit{perf}})\cdot
da(L_{\mathit{contains-}l^{*}})=da(L_{\mathit{perf}})$. We will show that
$L_{\mathit{perf}}\cap L_{\mathit{contains-}l^{*}}$ is not countably
ambiguous. By the above inequality, this implies that
$da(L_{\mathit{perf}})=2^{\aleph_{0}}$.

######  Claim 41.

$L_{\mathit{perf}}$ is not finitely ambiguous.

######  Proof 7.9 (Proof).

Define a function $F:\Sigma^{*}\rightarrow\Sigma$ such that
$F(\sigma_{1},\dots,\sigma_{m}):=\begin{cases}1&\exists 1\leq i\leq
m:\sigma_{i}=1\\\ 0&\text{otherwise.}\end{cases}$. It is easy to see that $F$
is definable by a Moore machine, and that $\forall t^{\prime}\in
T^{\omega}_{\Sigma}:t^{\prime}\in
T^{\omega}_{\Sigma}\setminus\\{t[\emptyset]\\}\leftrightarrow\widehat{F}(t^{\prime})\in
L_{\mathit{perf}}$. Notice that
$T^{\omega}_{\Sigma}\setminus\\{t[\emptyset]\\}$ is not finitely ambiguous (by
Corollary 19(2)), and therefore by Lemma 15 we conclude that
$L_{\mathit{perf}}$ is not finitely ambiguous.

######  Claim 42.

$t^{\prime}\in L_{\mathit{perf}}\cap L_{\mathit{contains-}l^{*}}$ iff the
following conditions hold:

  1. (1)

$\forall u\in l^{*}:t^{\prime}(u)=1$

  2. (2)

There is an infinite set $I\subseteq\mathbb{N}$ such that $\forall i\in
I:t^{\prime}_{\geq l^{i}\cdot r}\in L_{\mathit{perf}}$ and $\forall i\not\in
I:t^{\prime}_{\geq l^{i}\cdot r}\in\\{t[\emptyset]\\}$.

######  Proof 7.10 (Proof).

$\Rightarrow$: Let $t^{\prime}\in L_{\mathit{perf}}\cap
L_{\mathit{contains-}l^{*}}$. By definition of $L_{\mathit{contains-}l^{*}}$
it is clear that condition (1) holds for $t^{\prime}$. Notice that $\forall
i\in\mathbb{N}:t^{\prime}_{\geq l^{i}\cdot r}\in L_{\mathit{perf}}$ or
$t^{\prime}_{\geq l^{i}\cdot r}=t[\emptyset]$. Assume, for the sake of
contradiction, that $\\{i\in\mathbb{N}\mid t^{\prime}_{\geq l^{i}\cdot r}\in
L_{\mathit{perf}}\\}$ is finite. Therefore, there is $k\in\mathbb{N}$ such
that $\forall i\geq k:t^{\prime}_{\geq l^{i}\cdot r}=t[\emptyset]$. Let
$u:=l^{k}$, and notice that $t^{\prime}(u)=1$, and $\forall
v>u:t^{\prime}(v)=1\leftrightarrow v\in l^{*}$. Hence, each pair of
$1$-labeled nodes that are greater than $u$ are comparable – a contradiction
to the definition of $L_{\mathit{perf}}$.

$\Leftarrow$: Let $t^{\prime}$ such that the conditions hold. By the first
condition it is clear that $t^{\prime}\in L_{\mathit{contains-}l^{*}}$. We
will prove that $t^{\prime}\in L_{\mathit{perf}}$, and the claim will follow.
First, notice that $t^{\prime}(\epsilon)=1$, and therefore $t^{\prime}\neq
t[\emptyset]$. Let $u$ be a node such that $t^{\prime}(u)=1$. If $u\in l^{*}$
then by the second condition, there is a node $v\in l^{*}\cdot r$ such that
$v>u$ and $t_{\geq v}\in L_{\mathit{perf}}$. Therefore, there are two nodes
$w_{1},w_{2}>v>u$ such that $w_{1}\perp w_{2}$ and
$t^{\prime}(w_{1})=t^{\prime}(w_{2})=1$. Otherwise ($u\notin l^{*}$), there is
a node $v\in l^{*}\cdot r$, such that $u>v$ and $t_{\geq v}\in
L_{\mathit{perf}}$, and by definition of $L_{\mathit{perf}}$ we conclude that
there are two nodes $w_{1},w_{2}>u$ such that $w_{1}\perp w_{2}$ and
$t^{\prime}(w_{1})=t^{\prime}(w_{2})=1$ – hence, $t^{\prime}\in
L_{\mathit{perf}}$.

It is easy to see that $L_{\mathit{perf}}\cap
L_{\mathit{contains-}l^{*}}=\mathfrak{L}[L_{0},L^{\neg ba}]$ for $L^{\neg
ba}:=L_{\mathit{perf}}$ (which is not boundedly ambiguous, by Claim 41) and
$L_{0}:=\\{t[\emptyset]\\}$. Therefore, by Proposition 35 we conclude that
$L_{\mathit{perf}}\cap L_{\mathit{contains-}l^{*}}=2^{\aleph_{0}}$, as
requested.

Observe that our proof shows that $L_{\mathit{perf}\wedge\min}:=\\{t[X]\mid X$
is perfect and has the $\leq$-minimal element$\\}$ is also uncountably
ambiguous. We conclude with an instructive example of an unambiguous language
which is similar to $L_{\mathit{perf}\wedge\min}$. Let
$X\subseteq\\{l,r\\}^{*}$ be a set of nodes. We say that $u\in X$ is a
$X$-successor of $v$ if $u>v$ and there is no node $w\in X$ such that $v<w<u$.
We call $X$ a full-binary subset-tree if $X$ has a minimal node, and each node
in $X$ has two $X$-successors.

Note that if $X$ is a full-binary subset tree then $X$ is perfect and has the
$\leq$-minimal element. However the language $L_{\mathit{binary}}:=\\{t[X]\mid
X$ is a full-binary subset tree$\\}$ is unambiguous.

##  8\. Countable Languages are Unambiguous

In this section we prove the following Proposition:

######  Proposition 43.

Each regular countable tree language is unambiguous

This section is self-contained and lacks technical connections to the previous
sections. It is instructive to compare the above Proposition with Corollary
19(1) which states that the complement of every countable tree language is not
finitely ambiguous.

To prove Proposition 43 we first recall finite tree automata (Subsection 8.1).
Then, we present Niwiński’s Representation for Countable Languages (Subsection
8.2). Finally, the proof of Proposition 43 is given (Subsection 8.3).

###  8.1. Finite Trees and Finite Tree Automata

#### Finite Trees

A finite tree is a finite set $U\subseteq\\{l,r\\}^{*}$ that is closed under
prefix relation. $U$ is called a finite binary tree if $\forall u\in U:u\cdot
l\in U\leftrightarrow u\cdot r\in U$.

#### Finite $\Sigma$-labeled Binary Trees

Let $\Sigma$ be partitioned into two sets: $\Sigma_{2}$ – labels of internal
nodes, and $\Sigma_{0}$ – labels of leaves. A finite $\Sigma$-labeled binary
tree is a function $t_{U}:U\rightarrow\Sigma$, where $U\subseteq\\{l,r\\}^{*}$
is a finite binary tree, $t_{U}(v)\in\Sigma_{0}$ if $v$ is a leaf, and
$t_{U}(v)\in\Sigma_{2}$ if $v$ has children.

When it is clear from the context, we will use “finite tree” or “labeled
finite tree” for “$\Sigma$-labeled finite binary tree”.

#### Finite Tree Automata (FTA)

An automaton over $\Sigma$-labeled finite trees is a tuple
$\mathcal{B}=(Q,\Sigma,Q_{I},\delta)$, where $Q$ is a finite set of states,
$\Sigma=\Sigma_{0}\cup\Sigma_{2}$ is an alphabet, $Q_{I}$ is a set of initial
states, and $\delta\subseteq(Q\times\Sigma_{0})\cup(Q\times\Sigma_{2}\times
Q\times Q)$ is a set of transitions.

An accepting computation of $\mathcal{B}$ on a finite tree $t_{U}$ is a
function $\phi:U\rightarrow Q$, such that $\phi(\epsilon)\in Q_{I}$, and for
each node $u\in U$, if $u$ is not a leaf then $(\phi(u),t_{U}(u),\phi(u\cdot
l),\phi(u\cdot r))\in\delta$, and otherwise $(\phi(u),t_{U}(u))\in\delta$.

The language of a FTA $\mathcal{B}$ is the set of finite trees $t$ such that
$\mathcal{B}$ has an accepting computation on $t$. A finite tree language is
regular iff it is accepted by a FTA. It is well-known that every regular
finite tree language is unambiguous (i.e., for every finite tree language
there is an unambiguous automaton that accepts it).

###  8.2. Niwiński’s Representation for Countable Languages

Define $T^{fin}_{\Sigma(\\{x_{1},\dots,x_{n}\\})}$ as the set of finite trees
over alphabet $\Sigma\cup\\{x_{1},\dots,x_{n}\\}$ where the internal nodes are
$\Sigma$-labeled, and the leaves are $\\{x_{1},\dots,x_{n}\\}$-labeled.

Let $\tau\in T^{fin}_{\Sigma(\\{x_{1},\dots,x_{n}\\})}$ be a finite tree, and
let $t_{1},\dots,t_{n}\in T^{\omega}_{\Sigma}$ be infinite binary trees over
alphabet $\Sigma$. We define $\tau[t_{1}/x_{1},\dots,t_{n}/x_{n}]$ as the
infinite tree that is obtained from $\tau$ by grafting $t_{i}$ on leaves
labeled by $x_{i}$.

For a set $M\subseteq T^{fin}_{\Sigma(\\{x_{1},\dots,x_{n}\\})}$, we define
$M[t_{1}/x_{1},\dots,t_{n}/x_{n}]:=\underset{\tau\in
M}{\bigcup}\tau[t_{1}/x_{1},\dots,t_{n}/x_{n}]$.

######  Theorem 44 (D. Niwiński [Niw91]).

Let $L$ be a countable regular tree language over alphabet $\Sigma$. Then
there is a finite set of trees $\\{t_{1},\dots,t_{n}\\}$ such that the
following hold:

  1. (1)

For each tree $t\in L$ and a tree branch $\pi$, there is a node $v\in\pi$ and
a number $1\leq i\leq n$ such that $t_{\geq v}=t_{i}$.

  2. (2)

There is a regular finite tree language $M\subseteq
T^{fin}_{\Sigma(\\{x_{1},\dots,x_{n}\\})}$ s.t.
$L=M[t_{1}/x_{1},\dots,t_{n}/x_{n}]$.

The following lemma strengthen item (2) of Theorem 44 by adding another
condition on $M$, implying a unique representation of each tree in $L$:

######  Lemma 45.

Let $L$ be a countable regular tree language over alphabet $\Sigma$, and let
$\\{t_{1},\dots,t_{n}\\}$ be a finite set of trees as in Theorem 44. Then
there is a regular finite trees language $M\subseteq
T^{fin}_{\Sigma(\\{x_{1},\dots,x_{n}\\})}$ such that
$L=M[t_{1}/x_{1},\dots,t_{n}/x_{n}]$, and for each $t\in L$ there is a unique
finite tree $\tau\in M$ such that $t=\tau[t_{1}/x_{1},\dots,t_{n}/x_{n}]$.

######  Proof 8.1.

For each tree $t\in L$, let $g(t)$ be the tree that is obtained from $t$ by
changing the label of each node $v\in\\{l,r\\}^{*}$ where $t_{\geq v}=t_{i}$
to $x_{i}$, and removing all descendants of $\\{x_{1},\dots,x_{n}\\}$-labeled
node.

######  Claim 46.

$g(t)$ is finite for all $t\in L$.

######  Proof 8.2 (Proof).

Assume, for the sake of contradiction, that there is $t\in L$ such that the
set of nodes $U\subseteq\\{l,r\\}^{*}$ of $g(t)$ is infinite. The number of
children of each node in $U$ is bounded by 2, and therefore, by König’s Lemma,
there is a tree branch $\pi$ such that $\forall v\in\pi:v\in U$. Therefore, by
definition of $g(t)$, we conclude that $t_{\geq v}\neq t_{i}$ for each
$v\in\pi$ and $1\leq i\leq n$ – a contradiction to item (1) of Theorem 44.

Notice that for each $t\in L$ we obtain
$g(t)[t_{1}/x_{1},\dots,t_{n}/x_{n}]=t$, and therefore $g$ is injective.
Hence, $L=M[t_{1}/x_{1},\dots,t_{n}/x_{n}]$ where $M:=\\{g(t)\mid t\in L\\}$.
We will show that $M$ is a regular language of finite trees.

It is easy to see that for each $t\in L$ and finite tree $\tau\in
T^{fin}_{\Sigma(\\{x_{1},\dots,x_{n}\\})}$, $\tau=g(t)$ iff the following
conditions hold:

  * •

$t=\tau[t_{1}/x_{1},\dots,t_{n}/x_{n}]$

  * •

$t_{\geq v}\neq t_{i}$ for each node $v$ in $\tau$ that is not a leaf, and for
each $1\leq i\leq n$.

Since both conditions could be formulated in MSO, we conclude that $M$ is MSO-
definable, and therefore regular.

###  8.3. Proof of Proposition 43

Let $L$ be a countable regular tree language over alphabet $\Sigma$. We will
show that $L$ can be accepted by an unambiguous PTA.

By Lemma 45, there is a regular finite tree language $M\subseteq
T^{fin}_{\Sigma(\\{x_{1},\dots,x_{n}\\})}$ and regular infinite trees
$t_{1},\dots,t_{n}$ such that $L=M[t_{1}/x_{1},\dots,t_{n}/x_{n}]$.
Additionally, for each $t\in L$ there is a unique $\tau\in M$ such that
$t=\tau[t_{1}/x_{1},\dots,t_{n}/x_{n}]$.

Each infinite tree $t_{i}:\\{l,r\\}^{*}\rightarrow\Sigma$ is regular, and
therefore, by Fact 16, is definable by a Moore machine
$M_{i}=(\\{l,r\\},\Sigma,Q_{i},q_{I}^{i},\delta^{M}_{i},out^{M}_{i})$. Let
$\mathcal{A}_{i}:=(Q_{i},\Sigma,q_{I}^{i},\delta_{i},F_{i})$ where
$F_{i}:=Q_{i}$, and $(q,a,q_{1},q_{2})\in\delta_{i}$ iff $q_{1}=\delta(q,l)$,
$q_{2}=\delta(q,r)$ and $a=out^{M}_{i}(q)$. It is easy to verify that
$\mathcal{A}_{i}$ is unambiguous, and $L(\mathcal{A}_{i})=\\{t_{i}\\}$. $M$ is
regular and therefore can be accepted by an unambiguous FTA
$\mathcal{B}=(Q_{\mathcal{B}},\Sigma\cup\\{x_{1},\dots,x_{n}\\},q^{\mathcal{B}}_{I},\delta_{\mathcal{B}})$.

We use these automata to construct a PTA
$\mathcal{A}:=(Q,\Sigma,Q_{I},\delta,\mathbb{C})$, by:

  * •

$Q:=\cup_{1\leq i\leq n}Q_{i}\cup Q_{\mathcal{B}}$

  * •

$q_{I}^{i}:=\\{q^{\mathcal{B}}_{I}\\}\cup\\{q_{I}^{i}\mid(q^{\mathcal{B}}_{I},x_{i})\in\delta_{\mathcal{B}}\\}$

  * •

$\delta$ is the union of the following:

    * –

$\\{(q,a,q_{1},q_{2})\in\delta_{\mathcal{B}}\mid a\in\Sigma\\}$ (all
transitions of $\mathcal{B}$ on inner nodes)

    * –

$\cup_{1\leq i\leq n}\delta_{i}$

    * –

$\\{(q,a,q_{I}^{i},q_{I}^{j})\mid\exists(q,a,q_{1},q_{2})\in\delta_{\mathcal{B}}:(q_{1},x_{i})\in\delta_{\mathcal{B}}$
and $(q_{2},x_{j})\in\delta_{\mathcal{B}}\\}$

    * –

$\\{(q,a,q_{1},q_{I}^{j})\mid\exists(q,a,q_{1},q_{2})\in\delta_{\mathcal{B}}:(q_{2},x_{j})\in\delta_{\mathcal{B}}\\}$

    * –

$\\{(q,a,q_{I}^{i},q_{2})\mid\exists(q,a,q_{1},q_{2})\in\delta_{\mathcal{B}}:(q_{1},x_{i})\in\delta_{\mathcal{B}}\\}$

  * •

$\mathbb{C}(q):=\begin{cases}\mathbb{C}_{i}(q)&\exists i:q\in Q_{i}\\\
1&\text{otherwise}\end{cases}$

It is easy to see that $L(\mathcal{A})=M[t_{1}/x_{1},\dots,t_{n}/x_{n}]=L$.

We will show that $\mathcal{A}$ is unambiguous. For each accepting computation
$\phi\in ACC(\mathcal{A},t)$, define a set of nodes
$U_{\phi}:=\\{u\in\\{l,r\\}^{*}\mid\forall v<u:\phi(v)\in Q_{\mathcal{B}}\\}$.
It is easy to see that $U_{\phi}$ is downward closed. Assume towards
contradiction that $U_{\phi}$ is infinite – by König Lemma, $U_{\phi}$
contains an infinite tree branch $\pi$. By definition of $U_{\phi}$ all states
in $\phi(\pi)$ are in $Q_{\mathcal{B}}$, and therefore colored by $1$. That is
a contradiction to $\phi$ being an accepting computation.

Define a labeled finite tree
$t_{\phi}:U_{\phi}\rightarrow\Sigma\cup\\{x_{1},\dots,x_{n}\\}$ by:

$t_{\phi}:=\begin{cases}x_{i}&\exists i:\phi(u)=q_{I}^{i}\\\
t(u)&\text{otherwise}\end{cases}$

By definition of $t_{\phi}$ we obtain
$t=t_{\phi}[t_{1}/x_{1},\dots,t_{n}/x_{n}]$, and by definition of
$\mathcal{B}$ we conclude that $t_{\phi}\in M$.

Assume, for the sake of contradiction, that $\mathcal{A}$ is ambiguous.
Therefore, there is a tree $t\in L$ and two distinct accepting computations
$\phi_{1},\phi_{2}\in ACC(\mathcal{A},t)$. $\mathcal{A}_{i}$ is deterministic
for each $1\leq i\leq n$, and therefore $\phi_{1}\neq\phi_{2}$ iff
$t_{\phi_{1}}\neq t_{\phi_{2}}$. We conclude that
$t_{\phi_{1}}[t_{1}/x_{1},\dots,t_{n}/x_{n}]=t_{\phi_{2}}[t_{1}/x_{1},\dots,t_{n}/x_{n}]$
for $t_{\phi_{1}},t_{\phi_{2}}\in M$ – a contradiction to the uniqueness
property of $M$.

##  9\. Conclusion and Open Questions

We proved that the ambiguity hierarchy is strict for regular languages over
infinite trees.

For each level of the ambiguity hierarchy we provided a language which
occupies this level. It is not difficult to see that all these languages are
definable by MSO-formulas without the second-order quantifiers (formulas of
the first-order fragment of MSO). Concerning the topological complexity,
Olivier Finkel [Fin20] observed that these languages have low topological
complexity: $L_{\neg a_{1}\vee\dots\vee\neg a_{k}}$ are closed languages;
$L^{fa}$ and $L_{\exists a_{1}}$ are countable unions of closed sets, i.e., a
$\Sigma^{0}_{2}$-sets; the uncountably ambiguous language $L_{\mathit{no-
max}}$ is $\Pi^{0}_{2}$. On the other hand, Skrzypczak [Skr18] proved that
unambiguous languages climb up the whole index hierarchy and are topologically
as complex as arbitrary regular tree languages.

A natural question is whether the ambiguity degree is decidable. However, this
is not a trivial matter. In [BS13] some partial solutions for variants of the
problem whether a given language is unambiguous are provided. We proved that
countable regular languages are unambiguous. Since it is decidable whether a
language is countable [Niw91], this provides a decidable sufficient condition
for a langauge to be unambiguous.

A less ambitious task is to develop techniques for computing degrees of
ambiguity and compute the degree of ambiguity of some natural languages. Let
$\Sigma_{1}:=\\{c,a_{1}\\}$ and $L_{\exists^{\infty}a_{1}}:=\\{t\in
T_{\Sigma_{1}}^{\omega}\mid$ there are infinitely many $a_{1}$-labeled nodes
in $t\\}$. $L_{\exists^{\omega}a_{1}}:=\\{t\in T_{\Sigma_{1}}^{\omega}\mid$
there is a branch with infinitely many $a_{1}$-labeled nodes in $t\\}$.
$L_{a_{1}-\infty\mbox{antichain}}:=\\{t\in T_{\Sigma_{1}}^{\omega}\mid$ the
set of $a_{1}$-labeled nodes in $t$ contain an infinite antichain$\\}$. All
these languages are regular. There are (Moore) reductions from $L_{\exists
a_{1}}$ to these languages, hence they are not finitely ambiguous. We believe
that their ambiguity degree is uncountable, but we were unable to prove this.

We provided sufficient conditions for a language to be not finitely ambiguous
and for a language to have uncountable degree of ambiguity. In particular, we
proved that the degree of ambiguity of the complement of a countable regular
language is $\aleph_{0}$ or $2^{\aleph_{0}}$, and provided natural examples of
such languages with countable degree of ambiguity. We proved that the degree
of ambiguity of the complement of a finite regular language is $\aleph_{0}$.
Yet, it is open whether the degree of ambiguity of the complement of countable
regular languages is $\aleph_{0}$.

## Acknowledgments

We would like to thank anonymous referees for their helpful suggestions.

## References

  * [Arn83] André Arnold.  Rational omega-languages are non-ambiguous.  Theor. Comput. Sci., 26:221–223, 09 1983.
  * [BKR10] Vince Bárány, Łukasz Kaiser, and Alex Rabinovich.  Expressing cardinality quantifiers in monadic second-order logic over trees.  Fundamenta Informaticae, 100(1-4):1–17, 2010.
  * [BS13] Marcin Bilkowski and Michal Skrzypczak.  Unambiguity and uniformization problems on infinite trees.  In Simona Ronchi Della Rocca, editor, Computer Science Logic 2013 (CSL 2013), CSL 2013, September 2-5, 2013, Torino, Italy, volume 23 of LIPIcs, pages 81–100. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2013.
  * [CL07] Arnaud Carayol and Christof Löding.  MSO on the infinite binary tree: Choice and order.  In International Workshop on Computer Science Logic, pages 161–176. Springer, 2007.
  * [CLNW10] Arnaud Carayol, Christof Löding, Damian Niwinski, and Igor Walukiewicz.  Choice functions and well-orderings over the infinite binary tree.  Open Mathematics, 8(4):662–682, 2010.
  * [Col15] Thomas Colcombet.  Unambiguity in automata theory.  In International Workshop on Descriptional Complexity of Formal Systems, pages 3–18. Springer, 2015.
  * [EJ91] E Allen Emerson and Charanjit S Jutla.  Tree automata, mu-calculus and determinacy.  In FoCS, volume 91, pages 368–377. Citeseer, 1991.
  * [Fin20] Olivier Finkel.  Personal communication, 12 2020.
  * [GH82] Yuri Gurevich and Leo Harrington.  Trees, automata, and games.  In Proceedings of the fourteenth annual ACM symposium on Theory of computing, pages 60–65, 1982.
  * [GS83] Yuri Gurevich and Saharon Shelah.  Rabin’s uniformization problem 1.  The Journal of Symbolic Logic, 48(4):1105–1119, 1983.
  * [HSS17] Yo-Sub Han, Arto Salomaa, and Kai Salomaa.  Ambiguity, nondeterminism and state complexity of finite automata.  Acta Cybernetica, 23(1):141–157, 2017.
  * [JJŠ16] Jozef Jirásek, Galina Jirásková, and Juraj Šebej.  Operations on unambiguous finite automata.  In International Conference on Developments in Language Theory, pages 243–255. Springer, 2016.
  * [Lei81] Ernst Leiss.  Succinct representation of regular languages by boolean automata.  Theoretical computer science, 13(3):323–330, 1981.
  * [Leu05] Hing Leung.  Descriptional complexity of nfa of different ambiguity.  International Journal of Foundations of Computer Science, 16(05):975–984, 2005.
  * [McN66] Robert McNaughton.  Testing and generating infinite sequences by a finite automaton.  Information and control, 9(5):521–530, 1966.
  * [Niw91] Damian Niwiński.  On the cardinality of sets of infinite trees recognizable by finite automata.  In Andrzej Tarlecki, editor, Mathematical Foundations of Computer Science 1991, pages 367–376, Berlin, Heidelberg, 1991. Springer Berlin Heidelberg.
  * [PP04] Dominique Perrin and Jean-Éric Pin.  Infinite words: automata, semigroups, logic and games, volume 141\.  Academic Press, 2004.
  * [Rab69] Michael O Rabin.  Decidability of second-order theories and automata on infinite trees.  Transactions of the american Mathematical Society, 141:1–35, 1969\.
  * [RT20] Alexander Rabinovich and Doron Tiferet.  Ambiguity Hierarchy of Regular Infinite Tree Languages.  In Javier Esparza and Daniel Kráľ, editors, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020), volume 170 of Leibniz International Proceedings in Informatics (LIPIcs), pages 80:1–80:14, Dagstuhl, Germany, 2020. Schloss Dagstuhl–Leibniz-Zentrum für Informatik.
  * [SHI85] Richard Edwin Stearns and Harry B Hunt III.  On the equivalence and containment problems for unambiguous regular expressions, regular grammars and finite automata.  SIAM Journal on Computing, 14(3):598–611, 1985.
  * [Skr18] Michal Skrzypczak.  Unambiguous languages exhaust the index hierarchy.  In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, volume 107 of LIPIcs, pages 140:1–140:14. Schloss Dagstuhl \- Leibniz-Zentrum für Informatik, 2018.
  * [TB73] Boris Trakhtenbrot and Ya Martynovich Barzdin.  Finite automate: behaviour and synthesis.  1973\.
  * [Tho90] Wolfgang Thomas.  Automata on infinite objects.  In Formal Models and Semantics, pages 133–191. Elsevier, 1990.

##  Appendix A Proof of Claim 21

See 21

######  Proof A.1 (Proof).

$t_{0}$ is regular, and therefore there is a formula $\psi_{t_{0}}(\sigma)$
that defines $t_{0}$ in the unlabeled full-binary tree.

We will use $\psi_{t_{0}}(\sigma)$ to define the following formula
$\mathit{PathfinderWins}_{\mathcal{A},t_{0}}(\phi,STR)$, as the conjunction of
the following conditions:

  1. (1)

$\exists\pi$ such that:

    1. (a)

$\pi$ is a branch

    2. (b)

$\forall u\in\pi:(STR(u,\phi(u\cdot l),\phi(u\cdot r))=l)\leftrightarrow
u\cdot l\in\pi)$ – the Pathfinder moves $d_{0}\dots d_{j}\dots$ are consistent
with $STR$ and are along the branch $\pi$.

  2. (2)

$\exists\sigma:\psi_{t_{0}}(\sigma)$ and at least one of the following holds:

    1. (a)

$\exists v\in\pi$ such that $(\phi(v),\sigma(v),\phi(v\cdot l),\phi(v\cdot
r))\notin\delta$ – the Automaton move at $(v,\phi(v))$ is invalid.

    2. (b)

The maximal color that $\mathbb{C}$ assigns infinitely often to states in
$\phi(\pi)$ is odd.

$\mathit{PathfinderWins}_{\mathcal{A},t_{0}}(\phi,STR)$ holds for a positional
strategy $STR$ of Pathfinder and a computation $\phi$ of $\mathcal{A}$ on a
tree $t^{\prime}$ iff the play $\overline{s}$ of $STR$ against $str_{\phi}$ in
$G_{t_{0},\mathcal{A}}$ is winning for Pathfinder.

######  Proof A.2 (Proof).

By definition of $G_{t_{0},\mathcal{A}}$, Pathfinder wins if either Automaton
makes an invalid move (condition 2a) or the maximal color that is assigned
infinitely often to the positions in $\pi_{\overline{s}}$ is odd. Since all
Pathfinder positions have color $0$, this is equivalent to the maximal color
assigned infinitely often to Automaton positions being odd.

Let $\overline{s}=e_{0},d_{0},e_{1},d_{1},\dots,e_{i},d_{i},\dots$. Notice
that by condition 1, there is a unique branch $\pi$ such that $\pi=v_{0},\dots
v_{i},\dots$ where $v_{i}=d_{0}\dots d_{i-1}$. By Claim 18, we have
$\phi(v_{i})=q_{i}$, where the $i$-th position of Automaton in
$\pi_{\overline{s}}$ is $(v_{i},q_{i})$. Since
$\mathbb{C}_{G}(v_{i},q_{i})=\mathbb{C}(q_{i})$, we conclude that the maximal
color that $\mathbb{C}$ assigns infinitely often to states in $\phi(\pi)$ is
odd iff the maximal color that $\mathbb{C}_{G}$ assigns infinitely often to
positions in $\pi_{\overline{s}}$ is odd. This is assured by condition 2b.

Let $\mathit{WinningStrategy}_{t_{0},\mathcal{A}}(STR):=\forall\phi$ such that
the following holds:

  * •

If there is $t$ such that $\phi$ is an accepting computation of $\mathcal{A}$
on $t$, then:

    * –

$\mathit{PathfinderWins}_{\mathcal{A},t_{0}}(\phi,STR)$ holds

Recalling that the set of all computation of $\mathcal{A}$ is MSO-definable,
we can conclude that $\mathit{WinningStrategy}_{t_{0},\mathcal{A}}(STR)$ is
MSO-definable in the unlabeled full-binary tree.
$\mathit{WinningStrategy}_{t_{0},\mathcal{A}}(STR)$ holds for a positional
strategy $STR$ of Pathfinder iff $STR$ is a positional winning strategy of
Pathfinder.

######  Proof A.3 (Proof).

$\Rightarrow$: By Claim A.1, $STR$ wins in $G_{t_{0},\mathcal{A}}$ against
each positional strategy of Automaton. Assume, for the sake of contradiction,
that is a non-positional strategy $str^{\prime}$ of automaton that wins
against $STR$. Then by positional determinacy of parity games, we conclude
that there is a positional strategy $str^{\prime\prime}$ that wins against
$STR$ – a contradiction.

$\Leftarrow$: Follows immediately from Claim A.1.

We have $t_{0}\notin L(\mathcal{A})$ and therefore by Claim 18(3), Automaton
does not have a positional winning strategy. From positional determinacy of
parity games we conclude that Pathfinder has a positional winning strategy.
Therefore, there is a strategy $STR^{\prime}$ that satisfies
$\mathit{WinningStrategy}_{t_{0},\mathcal{A}}(STR)$ in the unlabeled full-
binary tree.

Therefore, $\mathit{WinningStrategy}_{t_{0},\mathcal{A}}(STR)$ defines a non-
empty tree language over alphabet $Q\times Q\rightarrow\\{l,r\\}$. By Rabin’s
basis Theorem, we conclude that there is a regular tree $\widehat{STR}$ in
this language, and by Claim A.2 we conclude that $\widehat{STR}$ is a
positional winning strategy for Pathfinder in $G_{t_{0},\mathcal{A}}$.

#### Remark (Logic Free Proof of Claim 21)

One can reduce a membership game for a regular tree $t_{0}$ to a game on a
finite graph. By positional determinacy Theorem, Pathfinder will have a
positional winning strategy in the reduced game. From this strategy a regular
winning strategy in $G_{t_{0},\mathcal{A}}$ for Pathfinder is easily
constructed.