A comparison is made of the computing capabilities of deterministic pushdown store machines and real-time iterative arrays of finite-state machines.The main result is that every deterministic pushdown store computation can be performed by some (multidimensional) iterative array in real-time.The latter are strictly more powerful since they can recognize the set of palindromes in real-time, which deterministic pushdown store machines cannot do even if permitted unlimited computing time.During the development of the main result, variants of pushdown store machines, the tabulator machines and the n-dimensional pushdown store machines, are introduced.By imposing a real-time constraint and letting the number of tabs and the number of dimensions vary, an infinite hierarchy of pushdown store (deterministic context-free) languages is obtained.

A comparison is made of the computing capabilities of pushdown store machines and real-time iterative arrays of finite-state machines with the following results. Every pushdown store computation can be performed by some iterative array in real time. The latter are strictly more powerful, since they can recognize the set of palindromes in real time, which is impossible for pushdown-store machines even without a real-time constraint. Versions of pushdown store machines, the tabulator machines and the n-dimensional pushdown store machines, are introduced during the development. By imposing a real-time constraint and letting the number of tabs and the number of dimensions vary, these form infinite hierarchies whose unions are equivalent to the pushdown store machine.

An n-dimensional iterative array of finite-state machines is formally introduced as a real-time tape acceptor. The computational characteristics of iterative arrays are illuminated by establishing several results concerning the sets of tapes that they recognize. Intercommunication between machines in an array is characterized by specifying a stencil for the array. The computing capability of the array is preserved even if its stencil is reduced to a simple form in which machines communicate only with their nearest neighbors. An increase of computing speed by a constant factor k is defined by encoding k-length blocks of the input tapes, which reduces the lengths of the tapes by 1/k; the time available for computation is correspondingly reduced since the computation must be real time. The computation speed of iterative arrays can be increased by any constant factor k. Two examples of one-dimensional arrays are provided. The first accepts the set of palindromes; the second accepts the set of all tapes of the form ττ (for any tape τ). The latter set of tapes is not a context-free language; therefore, the sets of tapes accepted by iterative arrays are not all contained in the class of context-free languages. Conversely, the class of context-free languages is not contained in the class of sets of tapes accepted by iterative arrays. The sets of tapes accepted by iterative arrays are closed under the operations: union, intersection, and complement; therefore, they form a Boolean algebra. They are not closed under the reflection or concatenation-product operations.