Tree automata with constraints on infinite trees
Fix a finite alphabet . Denote by the set of -labellings of the complete infinite binary tree, i.e. maps . Let be an (equivalence) relation of such trees. A (binary) tree automaton with -constraints consists of a finite state set , an initial state , and a transition relation . A run of a tree automaton on a tree labelling is a choice of states and transitions for each vertex such that and , where if the left and right subtree of are in -relation and otherwise. A tree automaton accepts a labelling if there is a run for it. This can be extended to different more intricate acceptance conditions (Büchi condition along paths, parity conditions, \ldots{}). The set of labellings accepted by an automaton is called its language. The following questions might depend to some extent on the nature of the relation and should be understood as "for your favourite/interesting ". Question: Is emptiness/universality decidable for these automata? Question: What are the closure properties for these language classes?
