FacMikIntroduction.tex

% !TEX root = FacMik.tex

\section{Introduction}
In \cite{niwalu} there was given an algorithm which for a \emph{deterministic} parity tree automaton $\A$ decides whether the language $L(\A)$ is Borel. This was further extended to a finer classification in \cite{murlak2} and finally to a full Wadge classification in \cite{murlak}. The algorithms look for a pattern in the graph of the automaton and decide the Borel and Wadge classes upon finding of these special patterns. 

Similar problems for \emph{non-deterministic} parity tree automata seem to be much harder. 
Recently in \cite{bp} was provided an algorithm which decides for a given non-deterministic parity tree automaton $\A$, 
whether $L(\A)$ is a Boolean combination of open sets. For other Borel classes there was no known algorithm. This paper provides a relatively simple extension 
of the result in \cite{bp} to the class of ${\bf \Delta^0_2} = {\bf\Sigma^0_2}\cap{\bf\Pi^0_2}$ sets, that is the sets which are simultaneously presentable as countable unions of closed sets and countable intersections of open sets. This result is presented in Section \ref{sec:the main result} in Theorem \ref{theorem:main}. The proofs in \cite{bp} are based on an analysis of an algebraic structure computable from $\A$ and the main result states that the language $L(\A)$ is a Boolean combination of open sets if and only if a certain finite number of algebraic requirements hold. Since the class ${\bf \Delta^0_2}$ is bigger, in order to characterize this class, the set of algebraic requirements must be relaxed. In this paper we show that indeed this is the case. Our proofs closely follow the proofs from \cite{bp} with some necessary adjustments. In particular the crucial concept of the topological cutting game introduced in \cite{bp} is considered in this paper not only in the finite, but also in the infinite case. 

The approach presented in \cite{bp} and in the present paper in a certain sense is a reminiscent of the approach applied to deterministic automata in \cite{murlak2,murlak,niwalu}. Namely, the algebraic structure computed from a given automaton $\A$ induces a graph with edges reflecting the algebraic properties. In the deterministic case it is possible to decide Borel and Wadge classes analyzing patterns in the graph of the automaton, in the present paper we are looking for patterns in the algebraic graph. 

Finally let us mention results which provide information about the set-theoretical complexity of a language accepted by a non-deterministic automaton $\A$ assuming some additional properties of $\A$:
\begin{itemize}
\item Rabin in \cite{rabin} proved, that if $L$ and its complement are accepted by a non-deterministic Büchi tree automata, then $L$ weakly definable, in particular it is Borel.
\item Recently in \cite{cklvb} it was shown using decidability results about the cost functions, that for a given non-deterministic Büchi tree automaton it is decidable whether the language is weakly definable. 
\item In \cite{fms} the decidability results regarding deterministic automata were lifted to 
a more general context of game automata.
\end{itemize}
This paper consists of four Sections: the Introduction, a preliminary Section 2 introducing automata, set-theoretical and algebraic notations, a Section 3 introducing topological games and linking these games to the Wadge hierarchy and Section 4 containing the main result.