On the descriptional complexity of iterative arrays

The descriptional complexity of iterative arrays (IAs) is studied. Iterative arrays are a parallel computational model with a sequential processing of the input. It is shown that IAs when compared to deterministic finite automata or pushdown automata may provide savings in size which are not bounded by any recursive function, so-called non-recursive trade-offs. Additional non-recursive trade-offs are proven to exist between IAs working in linear time and IAs working in real time. Furthermore, the descriptional complexity of IAs is compared with cellular automata (CAs) and non-recursive trade-offs are proven between two restricted classes. Finally, it is shown that many decidability questions for IAs are undecidable and not semidecidable.