Affiliations: Faculty of Information Science and Technology, University of Osaka
Electro-Communication, Neyagawa-shi, Hatsu-cho, 18-8, Osaka, 572-8530, Japan.
E-mail: umeo@umeolab.osakac.ac.jp
Abstract: 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 × n
(n⩾ 2) square and m × n (m, n ⩾ 2) rectangular arrays in 2n − 1
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(1) steps on two-dimensional rectangular arrays of size
m×n with a general located at an arbitrary position (r, s) in the
array, where m, n ⩾ 2, 1⩽ r ⩽ m and 1 ⩽ s⩽ n. The time complexities for the
first two algorithms developed are one to two steps larger than optimum ones
proposed for O(1)-bit conventional communication model. In the last, it is
shown that there exists a 1-state CA_{1-bit} that can generate in real-time a
context-sensitive integer sequence such that {2^n∣ n = 1, 2, 3, ...}.
Keywords: Cellular automaton, One-bit inter-cell communication model, Early bird problem, Firing squad synchronization problem, Integer sequence generation problem
