Two-dimensional iterative arrays: Characterizations and applications (Q1102749)

We analyze some properties of two-dimensional iterative and cellular arrays. For example, we show that arrays operating in T(n) time can be sped up to operate in time \(n+(T(n)-n)/k\). Thus, a running time of the form \(n+R(n)\), where R(n) is sublinear (e.g., \(\log n\), \(\log^*n\), etc.), can still be sped up to \(n+R(n)/k\). This type of speed-up is stronger than any previously known speed-up for any type of device. Even for Turing machines, the speed-up is only from T(n) to \(n+T(n)/k.\) Another interesting result is that simultaneous space-reduction and speed-up is possible, i.e., the number of processors of the array can be reduced while simultaneously speeding up its computation. Unlike previous approaches, we carry out our analyses using sequential machine characterizations of the iterative and cellular arrays. Consequently, we are able to prove our results on the much simpler sequential machine models.