Realtime reversible iterative arrays Iterative arrays are onedimensional arrays of interconnected interacting finite automata. The cell at the origin is equipped with a oneway readonly input tape. We investigate iterative arrays as acceptors for formal languages. In particular, we consider realtime devices which are reversible on the core of computation, i.e., from initial configuration to the configuration given by the time complexity. This property is called realtime reversibility. It is shown that realtime reversible iterative arrays can simulate restricted variants of stacks and queues. It turns out that realtime reversible iterative arrays are strictly weaker than realtime reversible cellular automata. On the other hand, a nonsemilinear language is accepted. We show that realtime reversibility itself is not even semidecidable, which extends the undecidability for cellular automata and contrasts with the general case, where reversibility is decidable for onedimensional devices. Moreover, we prove the nonsemidecidability of several other properties. Several closure properties are also derived.

Dynamics and Complexity of Computrons We investigate chaoticity and complexity of a binary general network automata of finite size with external input which we call a computron. As a generalization of cellular automata, computrons can have nonuniform cell rules, nonregular cell connectivity and an external input. We show that any finitestate machine can be represented as a computron and develop two novel settheoretic concepts: (i) diversity space as a metric space that captures similarity of configurations on a given graph and (ii) basin complexity as a measure of complexity of partitions of the diversity space. We use these concepts to quantify chaoticity of computronsxe2x80x99 dynamics and the complexity of their basins of attraction. The theory is then extended into probabilistic machines where we define fuzzy basin partitioning of recurrent classes and introduce the concept of ergodic decomposition. A case study on 1D cyclic computron is provided with both deterministic and probabilistic versions.