We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Iterative Arrays with Set Storage.
- Authors
KUTRIB, MARTIN; MALCHER, ANDREAS
- Abstract
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.
- Subjects
ARRAY processors; MACHINE theory; BACK up systems; REAL-time computing; ROBOTS
- Publication
Journal of Cellular Automata, 2016, Vol 12, Issue 1/2, p7
- ISSN
1557-5969
- Publication type
Article