×

The size impact of little iterative array resources. (English) Zbl 1280.68130

Summary: 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.

MSC:

68Q80 Cellular automata (computational aspects)
37B15 Dynamical aspects of cellular automata
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite