Linear-time recognition of connectivity of binary images on l-bit inter-cell communication cellular automaton

摘要

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