State-efficient one-bit communication solutions for some classical cellular automata problems
We present several state-efficient implementations on 1-bit inter-cell communication cellular automata for some classical cellular automata problems. The 1-bit inter-cell communication cellular automaton model (CA(1)-bit) studied in this paper is a subclass of cellular automata (CA) whose inter-cell communication at one step is restricted to 1-bit. We study an early bird problem, a firing squad synchronization problem and an integer sequence generation problem, all of which are known as the classical, fundamental problems in cellular automata. Firstly, it is shown that there exists a 37-state CA,(1)-bit that solves the early bird problem in twice real-time. Then, we give a two-dimensional CA(1)-bit which can synchronize any n x n (n > 2) square and m x n. (m, n > 2) rectangular arrays in 2n - I and m + n + max(m, n) steps, respectively. In addition, we propose a generalized linear-time synchronization algorithm that operates in m + n + max(r + s m + n - r - s + 2) + O(l) steps on two-dimensional rectangular arrays of size m, x n with a general located at an arbitrary position (r, s) in the array, where m., n > 2, 1 < r < m and I < s < n. The time complexities for the first two algorithms developed are one to two steps larger than optimum ones proposed for O(l)-bit conventional communication model. In the last, it is shown that there exists a 1-state CAI-bit that can generate in real-time a context- sensitive integer sequence such that 2(n)| n = 1, 2, 3,... }.
cellular automaton early bird problem firing squad synchronization problem integer sequence generation problem one-bit inter-cell communication model