Linear-time recognition of connectivity of binary images on 1-bit inter-cell communication cellular automaton (Q5940983)

We introduce a new class of two-dimensional Cellular Automata (CAs) whose inter-cell communication is restricted to 1-bit and propose a linear-time connectivity recognition algorithm for two-dimensional binary images. Precisely, it is shown that a set of two-dimensional connected binary images of size \(m\times\)n can be recognized in \(2(m+n)+O(1)\) steps by a two-dimensional CA with 1-bit inter-cell communication.