On totalistic systolic networks. (English) Zbl 0654.68058

A systolic network is an array of synchronized processors. It is totalistic if the states of its processors are integers and the next state of each processor is determined by the sum of all the states in its neighborhood including its own. Our main result is that every uniform regular network can be simulated by a totalistic systolic network.


68Q80 Cellular automata (computational aspects)
94C15 Applications of graph theory to circuits and networks
68R10 Graph theory (including graph drawing) in computer science
05C15 Coloring of graphs and hypergraphs
Full Text: DOI


[1] Albert, J.; Culik, K., Simple universal cellular automaton and its one-way and totalistic version, Complex systems, 1, 1-16, (1987) · Zbl 0655.68065
[2] Culik, K.; Fris, I., Topological transformations as a tool in the design of systolic networks, Theoret. comput. sci., 37, 183-216, (1985) · Zbl 0584.68068
[3] D. Gordon, On the computational power of totalistic cellular automata, Unpublished manuscript. · Zbl 0627.68049
[4] Kung, H.T., Why systolic architecture?, Computer magazine, 37-46, (1982)
[5] Kung, H.T.; Leiserson, C.E., Systolic arrays (for VLSI), Proc. sparse matrix conf., (1978) · Zbl 0404.68037
[6] Ullman, J.D., Computational aspects of VLSI, (1984), Computer Science Press Rockville, MD · Zbl 0539.68021
[7] Wolfram, S., Computation theory of cellular automata, Comm. math. physics, 96, 15-57, (1984) · Zbl 0587.68050
[8] Wolfram, S., Universality and complexity in cellular automata, Physica, 10 D, 1-35, (1984)
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.