Languages accepted by systolic \(Y\)-tree automata: Structural characterizations (Q1323359): Difference between revisions

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 are given again in terms of the shape of the underlying \(Y\)-tree for the closure under right concatenation with regular sets and for the decidability of the problems of emptiness, finiteness, equivalence and co-emptiness. A sufficient condition is given for the decidability of the stability problem, in the deterministic case, while some undecidability results are proved in the nondeterministic case.