Iterative Arrays with Set Storage

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, the witness languages reveal that the combination of both principles is strictly stronger than just the union of the single principles. Some basic 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.