The Size Impact of Little Iterative Array Resources
Martin Kutrib and Andreas Malcher
We investigate the descriptional complexity of little resources added to deterministic one-dimensional real-time iterative arrays. More precisely, we study the impact of adding sublinearly more time obtaining time complexities strictly in between real time and linear time, adding dimensions, allow the communication cell to perform a few nondeterministic steps, and increase the number of bits that may be communicated to neighboring cells slightly. In all cases it is shown that there are arbitrary savings in the size of the descriptions of the arrays which cannot be bounded by any computable function.
Keywords: Iterative arrays, descriptional complexity, size of description, nonrecursive trade-offs, resources, time, dimensions, nondeterminism, communication bandwidth.