SIMULATION OF SYSTOLIC TREE AUTOMATA ON TRELLIS AUTOMATA
Emanuela Fachini, Jozef Gruska, Andrea Maggiolo–Schettini, Davide Sangiorgi · International Journal of Foundations of Computer Science · 1990
The relation between two basic types of systolic automata—tree automata and trellis automata—is investigated. First it is shown that for every natural t>1 there is a simple nonhomogeneous (actually regular and also modular) trellis [Formula: see text] such that any t-ary systolic tree automaton can be simulated in a universal and quite straighforward way on a trellis automaton over [Formula: see text]. This implies that the family of languages accepted by systolic tree automata, which is incomparable with the family of languages accepted by homogeneous systolic trellis automata, is actually contained in the family of languages accepted by trellis automata that are both regular and modular.