TY - JOUR

T1 - Two-dimensional iterative arrays

T2 - Characterizations and applications

AU - Ibarra, Oscar H.

AU - Palis, Michael A.

N1 - Funding Information: * This research was supported in part by NSF Grants DC&8304756,

PY - 1988/4

Y1 - 1988/4

N2 - We analyse 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.

AB - We analyse 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.

UR - http://www.scopus.com/inward/record.url?scp=0024131922&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0024131922&partnerID=8YFLogxK

U2 - https://doi.org/10.1016/0304-3975(88)90163-6

DO - https://doi.org/10.1016/0304-3975(88)90163-6

M3 - Article

VL - 57

SP - 47

EP - 86

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

IS - 1

ER -