All computer scientists should be familiar with the theory of one-dimensional strings including the automata that can recognize them and the grammars that generate them. But the two-dimensional version is terra incognita to many, and wildly different. An example in this paper is that two-dimensional deterministic finite automata are significantly less powerful than nondeterministic ones. Further, a two-dimensional finite automaton can use the position of its head to encode a Turing machine! The paper starts with a cogent 50-year history of two-dimensional finite automata. It then defines two-dimensional versions of context-free grammars. It proves that the grammars give a more succinct description of classes of pictures than automata do. No recursive function can capture the relative growth of automata versus grammars that describe the same sets of pictures.

The approach is familiar, but many results are novel. My one criticism is that there is no formal definition of two-dimensional automata. This can be found in the cited references from the 1960s. Unsurprisingly, this subject has few applications but can be used to enrich traditional theory courses and textbooks.