POWER OF INTERCONNECTIONS AND OF NONDETERMINISM IN REGULAR Y-TREE SYSTOLIC AUTOMATA

The increase of computational power due to additions of some horizonta l interconnections between neighboring nodes of binary trees is invest igated using the concept of systolic automata over so-called Y-trees w ith one-directional, bottom-to-root, flow of computation. Y-trees are obtained from binary trees by connecting some neighboring pairs of nod es at the same level that are not brothers. We introduce the concept o f systolic automata on regular Y-trees in column normal form and prove that any systolic automaton on regular Y-trees is equivalent to one i n the column normal form. We then fully characterize those regular Y-t rees over which the class of languages recognized by nondeterministic automata is the same as for deterministic automata. An analogous resul t is obtained for stability. Furthermore, we show that superstable det erministic systolic automata over regular Y-trees recognize only regul ar languages. Finally, several closure properties of and relations bet ween classes of languages accepted by systolic automata over different Y-trees are studied.