SYNCHRONIZED TREE AUTOMATA

We introduce synchronized tree automata. They are an extension of the usual tree automaton model where computations in independent subtrees of the input have the capability to communicate in a limited way using the synchronization mechanism. The class of tree languages recognized by the nondeterministic synchronized automata is shown to be properly located between the recognizable and the context-free tree languages. We investigate closure properties and decision problems of synchroniz ed tree automata. Equivalence is shown to be undecidable for the nonde terministic synchronized tree automata but decidable for deterministic equality-synchronized automata.