Languages accepted by systolic \(Y\)-tree automata: Structural characterizations
type: Item
instance of: scholarly article
title: Languages accepted by systolic \(Y\)-tree automata: Structural characterizations
zbMATH Open document ID: 0790.68087
DOI: 10.1007/BF01191895
published in: Acta Informatica
publication date: 1994-07-04T00:00:00Z
review text: Systolic automata have been introduced as formal models to study systolic systems. They consist of (infinite) networks of (a few types of memoryless) finite automata, in which the way to input a word over a given alphabet, the direction of the flow of control, the transition rules for the processing elements and the output nodes are specified. Systolic automata whose communication structure are one-dimensional arrays, trees or trellises have been introduced and results about the power of the different interconnection topologies, the power of different input/output modes and the power of various types of homogeneity, have been obtained. Tree-like communication structures allow logarithmic time computation, hence systolic tree automata are very basic models of parallel processing. To increase the computational power while keeping logarithmic time complexity, new types of systolic automata have been defined in which the connection graph, called \(Y\)-tree, is obtained from a given infinite leafless labeled tree by assigning in a proper regular way new sons, called adoptive sons, to some nodes: a node may have as adoptive sons some nodes occurring to the left of its leftmost son and to the right of its rightmost son and in the same level as its sons. In this paper closure properties and decision problems for classes of languages accepted by deterministic and nondeterministic systolic automata over binary \(Y\)-trees are studied, i.e. \(Y\)-trees whose nodes have exactly two non-adoptive sons. Non-closure results under basic language operations are stated by means of new nonacceptability criteria for these classes of automata. Necessary and sufficient conditions are given in terms of the shape of the underlying \(Y\)-tree, for the closure under \(\lambda\)-free regular substitution, concatenation, inverse homomorphism and for the closure under right concatenation with and quotient by finite sets. Moreover, in the nondeterministic case necessary and sufficient conditions …
Mathematics Subject Classification ID: 68Q80
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 03D35
zbMATH DE Number: 567320
zbMATH Keywords: deterministic systolic automata
zbMATH Keywords: systolic systems
zbMATH Keywords: nondeterministic systolic automata
zbMATH Keywords: \(Y\)-trees
zbMATH Keywords: concatenation
zbMATH Keywords: regular sets
zbMATH Keywords: decidability
zbMATH Keywords: undecidability results
author: Emanuela Fachini
author: Angelo Monti
author: Margherita Napoli
author: Mimmo Parente
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: Power of interconnections and of nondeterminism in regularY-tree systolic automata
cites work: Q4430305
cites work: C-tree systolic automata
cites work: Non acceptability criteria and closure properties for the class of languages accepted by binary systolic tree automata
cites work: Q4206409
cites work: Q3361899
cites work: Q3677178
cites work: Synthesis, structure and power of systolic computations
cites work: Q3862379
cites work: SYSTOLIC TREE WITH BASE AUTOMATA
description: scientific article; zbMATH DE number 567320