Some relations between massively parallel arrays
Relations between various models for massively parallel computers are investigated. These are arrays of finite - state machines - eventually augmented by pushdown storage - operating synchronously. The architectures differ mainly in how the input is supplied and how the single nodes are interconnected. The comparisons are made in terms of their capabilities to time-construct and time-compute functions. That means that given an constant input of length n a distinguished cell has to enter distinguished states after f(1), ..., f(n) respectively f(n) time steps. (C) 1997 Elsevier Science B.V.
computability parallel automata complexity constructibility