Systolic trellis automatat†

From MaRDI portal
Publication:3687723





In the first part the notion of a systolic trellis automaton (sta) is introduced, and several of its modifications are considered. Informally, an sta is given by a triangularly shaped hexagonally structured network where each node is occupied by a processor (indeed by a combinational circuit). The data flow goes rhythmically in the direction from the bottom level (where the input is fed in a parallel way) to the top processor. So full pipelining is possible. sta are used as language acceptors. It is shown that homogeneous sta (each node is occupied by the same type of processor) are strictly less powerful than unrestricted ones. In the second part different design techniques for sta are presented and illustrated by interesting examples. Furthermore, several general results are proved: sta are more powerful than systolic tree automata (introduced in the article reviewed below), the class of homogeneous sta languages is closed under Boolean operations, and it contains all linear languages not having the empty word as an element.




Cited in
(37)








This page was built for publication: Systolic trellis automatat†

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3687723)