Two-dimensional formal languages and pattern recognition by cellular automata
Alvy Ray Smith · Annual Symposium on Switching & Automata Theory · 1971
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.
Cited by 92 works. doi:10.1109/swat.1971.29
Authors
References
- Pattern Detection and Recognition
- Computer Interpretation of English Text and Picture Patterns
- Recognition of convex blobs
- Array Automata and Array Grammars
- An optimum solution to the firing squad synchronization problem
- Cellular automata complexity trade-offs
- Tessellation Automata
- The syntax of a triangle and some other figures
- RECOGNITION OF TOPOLOGICAL INVARIANTS BY ITERATIVE ARRAYS
- Cellular automata and formal languages