The increase of computational power due to additions of some horizontal interconnections between neighboring nodes of binary trees is investigated using the concept of systolic automata over so-called 7-trees with one-directional, bottom-to-root, flow of computation.Y-trees are obtained from binary trees by connecting some neighboring pairs of nodes at the same level that are not brothers. We introduce the concept of systolic automata on regularY-trees in column normal form and prove that any systolic automaton on regularY-trees is equivalent to one in the column normal form. We then fully characterize those regularY-trees over which the class of languages recognized by nondeterministic automata is the same as for deterministic automata. An analogous result is obtained for stability. Furthermore, we show that superstable deterministic systolic automata over regularY-trees recognize only regular languages. Finally, several closure properties of and relations between classes of languages accepted by systolic automata over differentY-trees are studied.
Scheda prodotto non validato
Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo
|Titolo:||Power of Interconnections and of Nondeterminism in Regular Y-Tree Systolic Automata.|
|Data di pubblicazione:||1995|
|Appartiene alla tipologia:||01a Articolo in rivista|