## Classes of Systolic Y-Tree Automata and a Comparison with
Systolic trellis Automata

**D Sangiorgi et al**
*Abstract:* 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 more specific
case where the tree is t-ary or a tree with base. We show that for
each *s* \geq 0 the set of classes of languages accepted by
SYTA whose underlying tree is a tree with base with s leaves has a
maximum, called *LsSYTA*. We study when
*LsSYTA* is reached depending on number and position of
the adoptive sons. We prove that if s and t are powers of the same
base, then *LsSYTA=LtSYTA*. We give also a simulation
of SYTA on regular and modular systolic trellis automata,
strengthening a previous result on simulation of systolic tree
automata on systolic trellis automata.

*LFCS report ECS-LFCS-91-166*

Previous |

Index |

Next