Distinguishability,Simulation and Universality of Moore Tree Automata

Abstract

We extend the notions of distinguishability of states, simulation and universality of string automata to tree automata of Moore type. In particular, we prove that for each finite class of tree automata satisfying certain conditions, there is a unique minimal universal tree automaton. The transfer from strings to trees brings new aspects but also adds difficulties in generalizing classical Moore results.