In this paper we consider the extension of Nerode theorem to infinite trees. Unfortunately, we prove that this extension is not possible. We give some characterisations of Recognizable and Rational
-tree sets in terms of
-tree automata. We consider some complexity measures of Recognizable and Rational
-tree sets and prove that these measures define infinite hierarchies.
Keywords Tree automata - Büchi automata - Muller automata - and Rabin automata
Laboratoire d'Informatique Théorique et Programmation. This research was supported by PRC Maths-Info, France.