Iterative arrays with finite inter-cell communication
- PDF / 541,459 Bytes
- 13 Pages / 595.276 x 790.866 pts Page_size
- 69 Downloads / 193 Views
(0123456789().,-volV)(0123456789(). ,- volV)
Iterative arrays with finite inter-cell communication Martin Kutrib1
•
Andreas Malcher1
Accepted: 21 September 2020 Ó The Author(s) 2020
Abstract Iterative arrays whose internal inter-cell communication is quantitatively restricted are investigated. The quantity of communication is measured by counting the number of uses of the links between cells. In particular, iterative arrays are studied where the maximum number of communications per cell occurring in accepting computations is drastically bounded by a constant number. Additionally, the iterative arrays have to work in realtime. We study the computational capacity of such devices. For example, a result is that a strict and dense hierarchy with respect to the constant number of communications exists. Due to their very restricted communication, the question arises whether the usually studied decidability problems such as, for example, emptiness, finiteness, inclusion, or equivalence become decidable for such devices. However, it can be shown that all such decidability questions remain undecidable even if only four communications per cell are allowed. Finally, the undecidability results are shown to hold as well for one-way and two-way cellular automata having at most four communications per cell. Keywords Cellular automata Iterative arrays Communication bounds Computational capacity Decidability questions
1 Introduction Devices of homogeneous, interconnected, parallel acting automata have widely been investigated from a computational capacity point of view. Multi-dimensional devices with nearest neighbor connections whose cells are finite automata are commonly called cellular automata (CA). The cells work synchronously at discrete time steps. If the input mode is sequential to a distinguished communication cell, such devices are called iterative arrays (IA). In connection with formal language recognition onedimensional iterative arrays have been introduced in Cole (1969), where it was shown that the language family accepted by realtime IAs 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 iterative array parser exists. A
& Martin Kutrib [email protected] Andreas Malcher [email protected] 1
Institut fu¨r Informatik, Universita¨t Giessen, Arndtstr. 2, 35392 Giessen, Germany
realtime IA acceptor for prime numbers has been constructed in Fischer (1965). A characterization of various types of IAs in terms of restricted Turing machines and several results, especially speed-up theorems, are given in Ibarra and Palis (1985), (1988). Several more results concerning formal languages can be found, for example, in the survey (Kutrib 2009). It is obvious that inter-cell communication is an essential resource for iterative arrays that can be measured qualitatively as well as quantitatively. In the first case, the number of different messages to be communicated b
Data Loading...
