Classes of systolic \(Y\)-tree automata and a comparison with systolic trellis automata
type: Item
instance of: scholarly article
title: Classes of systolic \(Y\)-tree automata and a comparison with systolic trellis automata
zbMATH Open document ID: 0790.68086
DOI: 10.1007/BF01185564
published in: Acta Informatica
publication date: 1994-05-10T00:00:00Z
review text: 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 trel…
Mathematics Subject Classification ID: 68Q80
zbMATH DE Number: 567331
zbMATH Keywords: systolic systems
zbMATH Keywords: parallel systems
zbMATH Keywords: \(Y\)-tree Automata
zbMATH Keywords: systolic trellis automata
author: Emanuela Fachini
author: Andrea Maggiolo-Schettini
author: Davide Sangiorgi
MaRDI profile type: Publication
cites work: Systolic automata for VLSI on balanced trees
cites work: On a family of L languages resulting from systolic tree automata
cites work: Systolic trellis automatata †
cites work: Systolic trellis automata: Stability, decidability and complexity
cites work: Q3687724
cites work: Q3832052
cites work: SIMULATION OF SYSTOLIC TREE AUTOMATA ON TRELLIS AUTOMATA
cites work: Power of interconnections and of nondeterminism in regularY-tree systolic automata
cites work: Q4206409
cites work: Q3361899
cites work: C-tree systolic automata
cites work: Q3677178
cites work: Synthesis, structure and power of systolic computations
full work available at URL: https://doi.org/10.1007/bf01185564
OpenAlex ID: W1967603862
description: scientific article; zbMATH DE number 567331