Decidable Properties of Tree Languages

The first part of the thesis concerns problems related to the question: "when can a regular tree language be defined in first-order logic?" Characterizations in terms of automata of first-order logic and the related chain logic are presented. A decidable property of tree automata called confusion is introduced; it is conjectured that a regular tree language can be defined in chain logic if and only if its minimal automaton does not contain confusion. Furthermore, polynomial time algorithms are presented that decide if a given regular tree language can be defined in any one of the temporal branching logics TL[EX], TL[EF] and TL[EX, EF]. In the second part..