We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Hierarchies and undecidability results for iterative arrays with sparse communication.
- Authors
Malcher, Andreas
- Abstract
Iterative arrays with restricted internal inter-cell communication are investigated. A quantitative measure for the communication is defined by counting the number of uses of the links between cells and it is differentiated between the sum of all communications of an accepting computation and the maximum number of communications per cell occurring in accepting computations. The computational complexity of both classes of devices is investigated and put into relation. In addition, a strict hierarchy depending on the maximum number of communications per cell is established. Furthermore, it is shown that almost all commonly studied decidability questions are not semidecidable for iterative arrays with restricted communication. Finally, non-recursive trade-offs are proved among the iterative arrays providing the strict hierarchy depending on the maximum number of communications per cell.
- Subjects
HIERARCHIES; CELL communication; COMPUTATIONAL complexity; CELLULAR automata
- Publication
Natural Computing, 2020, Vol 19, Issue 4, p797
- ISSN
1567-7818
- Publication type
Article
- DOI
10.1007/s11047-019-09773-3