Systolic trellis automata. II. (English) Zbl 0571.68042

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.
Reviewer: G.Wechsung


68Q45 Formal languages and automata
68Q80 Cellular automata (computational aspects)
Full Text: DOI


[1] Berstel J., Transductions and Context-free Languages (1979) · Zbl 0424.68040
[2] Choffrut C., Acta Informatica (1979)
[3] Culik K., Systolic Automata for VLSI (1981)
[4] Culik K., Systolic Trellis Automata: Stability, Decidability and Complexity (1982)
[5] Culik K., Acta Informatica 18 pp 335– (1983) · Zbl 0493.68054
[6] Culik K., RAIRO 18 (1983)
[7] Kung, H. T. 1979. ”Let’s design algorithms for VLSI systems”. Edited by: Seitz, Ch. L. 65–90. Pasadena. Proc. Caltech Conference on Very Large Scale Integration
[8] Kung H. T., The Structure of Parallel Algorithms (1979)
[9] King H. T., Systolic Arrays (for VLSI) pp 256– (1979)
[10] Leiserson C. E., Optimising Synchronous Systems pp 23– (1981)
[11] Mead C. A., Introduction to VLSI Systems (1980)
[12] Ibarra O. H., Theoretical Computer Science (1980)
[13] Ibarra O. H. Kim S. M. Noran S. Trellis automata: characterizations, speed-up, hierarchy, decision problems Submitted for publication
[14] Dyer C. R., Inf. and Control 44 pp 261– (1980) · Zbl 0442.68082
[15] Morita Umeoh K., Information Proc. Letters 14 pp 158– (1982) · Zbl 0488.68041
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.