Iterative Arrays with Set Storage
Martin Kutrib and Andreas Malcher
Iterative arrays with set storage (SIA) are one-dimensional arrays of interconnected interacting finite automata. The input is supplied sequentially to the distinguished communication cell at the origin. In addition, the communication cell controls a set storage. To this end, it is equipped with a one-way writing tape where strings for the set operations are assembled, and the data storage set where words of arbitrary length can be stored. The computational capacity of (real-time) SIA is investigated. It is shown that such devices are strictly stronger than classical iterative arrays and classical set automata. Moreover, there is a language accepted by a real-time SIA that is neither accepted by a classical set automaton nor by a real-time IA, so the combination of both computing principles is strictly stronger than just the union of the single principles. Some closure properties are studied. Furthermore, in contrast to the situation for classical set automata, it is shown that any constant number of operations on the set cannot increase the computational capacity of classical iterative arrays. Finally, the decidability of the restriction to a finite number of set operations is addressed, where it turns out that the problem is not even semi-decidable.
Keywords: Iterative arrays, set storage, closure properties, decidability, computational capacity, time-bounded computations.