Classes of systolic \(Y\)-tree automata and a comparison with systolic trellis automata (Q1323376)

Systolic automata have been introduced as abstract models to study systolic systems. The latter are parallel systems composed of a large number of (a few types of) simple processing elements interconnected in a regular pattern. At each time unit, some processing elements are active and transmit simultaneously their results to the ones connected to them. These processors become the new set of active processing elements, and the process is repeated until an output is produced. Systolic automata are (infinite) networks of (a few type of memoryless) finite automata, in which the way to input a word over a given alphabet, the direction of control flow, the transition rules of the processing elements and the output node are specified. Systolic automata whose communication structure is an array, a tree or a trellis have been introduced and results about the power of different input/output modes, the power of various types of homogeneity, etc., have been obtained. Particularly important are the tree-like structures, due to their logarithmic time complexity. In this paper we study Systolic \(Y\)-tree Automata (SYTA), a class of systolic automata where the communication structure is obtained by adding new edges, and therefore new sons, called adoptive sons, to the nodes of the underlying tree according to some regularity condition. We study SYTA in the specific case where the tree is a tree with base, i.e. it has a finite balanced tree as building block. The \(t\)-ary trees, where all nodes have the same number \(t\) of sons, are the most relevant subclass of trees with base. We show that for each natural number \(s\) the set of classes of languages accepted by SYTA whose underlying tree has a base with \(s\) leaves has a maximum, called LsSYTA, and we study when this is reached depending on number and position of the adoptive sons. We also prove that if \(s\) and \(t\) are powers of the same base, then LsSYTA\(=\)LtSYTA. Finally, we give a simulation of SYTA on systolic trellis automata, whose communication structure is a labeled triangularly shaped infinite square grid. This result brings some more light in the understanding of the power of trellis structures. A number of different communication structures become provably representable on them.