Hierarchies and undecidability results for iterative arrays with sparse communication
- PDF / 498,164 Bytes
- 13 Pages / 595.276 x 790.866 pts Page_size
- 98 Downloads / 202 Views
Hierarchies and undecidability results for iterative arrays with sparse communication Andreas Malcher1
© Springer Nature B.V. 2019
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. Keywords Cellular automata · Iterative arrays · Communication bounds · Computational capacity · Decidability questions · Descriptional complexity
1 Introduction Devices of homogeneous, interconnected, parallel acting automata have extensively been investigated from a computational capacity point of view. The specification of such a system includes the type and specification of the single automata (sometimes called cells), their interconnection scheme (which can imply a dimension to the system), a local and/or global transition function, and the input and output modes. Multidimensional devices with nearest neighbor connections whose cells are finite automata are commonly called cellular automata (CA). If the input mode is sequential to a distinguished communication cell, they are called iterative arrays (IA). In connection with formal language recognition IA have been introduced in Cole (1969), where it was shown that the language family accepted by realtime-IA forms a Boolean algebra not closed under concatenation and reversal. In Chang et al. (1987) it is shown that for every context-free grammar a two-dimensional lineartime-IA parser exists. A realtime acceptor for prime numbers has been constructed in
B 1
Andreas Malcher [email protected] Institut für Informatik, Universität Giessen, Arndtstr. 2, 35392 Giessen, Germany
Fischer (1965). A characterization of various types of IA in terms of restricted Turing machines and several results, especially speed-up theorems, are given in Ibarra and Palis (1985), Ibarra and Palis (1988). Several more results concerning formal languages can be found, for example, in Smith (1972), Kutrib (2009). Communication is an essential resource for cellular automata and can be measured in a qualitative way and a quantitative way. In the first case, the number of different messages to be communicated by an IA is bounded by some fixed constant. Iterative arrays with this restricted inter-cell communication have been investigated in Umeo and K
Data Loading...
