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, ...}.
