DECIDABILITY OF EQUIVALENCE FOR DETERMINISTIC SYNCHRONIZED TREE AUTOMATA

Synchronized tree automata allow limited communication between computa tions in independent subtrees of the input. This enables them to verif y, for instance, the equality of two unary subtrees of unlimited size. The class of tree languages recognized by synchronized tree automata is strictly included in the context-free tree languages, As our main r esult we show that equivalence of tree languages recognized by determi nistic synchronized tree automata can be effectively decided. This con trasts the earlier undecidability result for the equivalence problem f or nondeterministic synchronized tree automata. For our decidability p roof we introduce globally deterministic synchronized tree automata. W e establish the various inclusion relations between the deterministic, globally deterministic and nondeterministic synchronized tree automat a.