Two-dimensional iterative arrays: Characterizations and applications (Q1102749)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Two-dimensional iterative arrays: Characterizations and applications |
scientific article |
Statements
Two-dimensional iterative arrays: Characterizations and applications (English)
0 references
1988
0 references
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.
0 references
two-dimensional iterative and cellular arrays
0 references
Turing machines
0 references
number of processors
0 references
speeding up
0 references
sequential machine models
0 references