Languages of pictures (2D matrices with entries from a finite alphabet) have been studied since Blum and Hewitt [1]; Rosenfeld [2]; and Siromoney, Siromoney, and Krithivasan [3]. A nondeterministic notion of recognizability by tessellation or tiling was introduced by Inoue and Nakamura [4] and studied by Giammarresi and Restivo [5]. A deterministic one-pass version, proceeding from the top left of the picture toward the bottom right, has been studied by Anselmo, Giammarresi, and Madonia [6].

The authors wish to have a less restrictive model: their deterministic ordered restarting automata (DORA) can move up, down, and right on the picture (this three-way idea was developed by Inoue and Takanami [7]). Further, they order the working alphabet of the automaton, allow replacement of a picture symbol by a lesser one in the ordering, and restart from the initial state at the top left position. Thus, only a bounded number of passes is possible over the picture; for words, this idea was shown by Hennie [8] to only accept regular languages.

The authors define three variants (two-way, extended two-way, and three-way) of automata; the membership problems of the corresponding languages are in polynomial time. The differences in the variants show up when considering languages that check whether particular rows and columns are copies or reversals of each other, or are palindromes themselves. A discussion on why having these languages is important for a picture automaton model is needed. The authors do not compare these classes to other intermediate models considered in [6].