Two-dimensional formal languages and pattern recognition by cellular automata

A formal study of pattern recognition capabilities of cellular automata is undertaken based on a class of recently introduced grammars for two dimensions, the array grammars, which can be thought of as the two-dimensional generalization of context-sensitive grammars. The class of languages (patterns) generated by array grammars is shown to be precisely the class of languages accepted by cellular automata forming rook-connected finite subsets of the plane. Thus the usual generalization to rectangular array-bounded cellular automata is a special case of this class of machines. The concept of perimeter time is introduced as a natural measure of computing speeds for two-dimensional cellular spaces, and connectedness and convexity are related to this measure. The class of patterns with positive Euler number is shown to be linear-time recognizable by rectangular array-bounded cellular automata, thus solving an open problem of Beyer.