Two-dimensional iterative arrays: Characterizations and applications

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.

Recommendations

Cites work

Cited in

(16)

This page was built for publication: Two-dimensional iterative arrays: Characterizations and applications

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