CLASSES OF SYSTOLIC Y-TREE AUTOMATA AND A COMPARISON WITH SYSTOLIC TRELLIS AUTOMATA

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 greater-than-or-equal-to 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.