We present a pipeline-interval-optimum systolic implementation of priority queues which can handle usual priority queue operations at every cycle.

In this paper we study a classical firing squad synchronization problem on a model of fault-tolerant cellular automata that have possibly some defective cells. Several fault-tolerant time-efficient synchronization algorithms are developed based on a simple freezing-thawing technique. It is shown that, under some constraints on the distribution of defective cells, any cellular array of length n with p defective cell segments can be synchronized in 2n - 2 + p steps.

In the design of systolic algorithms, optimizing the speed of I/O operations and computations is an important problem. In this paper we develop a time-optimum systolic simulation algorithm which converts any two-way cellular algorithm into systolic one, where the former separates the computations from its I/O operations, on the other hand, the latter overlaps them. It is shown that, for any kn linear-time two-way cellular automaton M, there exists a systolic array which can simulate M in (k+2)n+O(1) steps. The parallel steps required for the simulation are optimum.

Mesh-connected computers (MCC's for short) are an important class of physically realizable parallel processors, since many scientific problems can be naturally mapped on them and because their regular structures and simple nearest-neighbour interconnections are particularly suitable for VLSI implementations. In former days iterative arrays and cellular automata were studied and recently special attention has been paid to the study of systolic arrays as a model of parallel computation on VLSI implemented MCC's. These abstract computational models constitute a family of MCC's. In this paper we study the effects of broadcasting bus systems augmented with a mesh-connected computer. First we develop a direct proof technique for the elimination of broadcasting buses. Then, as an application of the technique, we will show that a rich variety of broadcasting bus systems on one- and two-dimensional arrays can be eliminated without any loss of time efficiency. No-time-loss elimination of broadcasting buses on one-dimensional arrays has been shown by a different technique by Ibarra et al., but without our technique, it would be more difficult, but not impossible, to get the same results that we presented newly in this paper.

We show that, for any simple SIMD machine M with time complexity T(n), there exists a systolic array which can simulate M in T(n)+2n+O(1) steps. Our result is an improvement on the previous (2T(n)+3n+O(1))-step systolic simulation theorem.

This paper presents a parallel two-dimensional array matching algorithm which can report all occurrences of a given key subarray of size kk within any text array of size nn in n nk1/l steps on lk2 comparator cells, where l(1ln) is the number of matching units. Our algorithm can be regarded as a two-dimensional generalization of Mukhopadhyay's parallel string matching algorithm.

A simpler and more straightforward proof is given for the recently-proved theorem such that real-time one-way cellular automata languages are closed under reversal.