Two-dimensional iterative arrays: Characterizations and applications

Oscar H. Ibarra, Michael A. Palis

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Pages (from-to)47-86
Number of pages40
JournalTheoretical Computer Science
Volume57
Issue number1
DOIs
StatePublished - Apr 1988
Externally publishedYes

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Two-dimensional iterative arrays: Characterizations and applications'. Together they form a unique fingerprint.

Cite this