Real-Time Computation by n-Dimensional Iterative Arrays of Finite-State Machines

Abstract

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.