In Theory Is Forever, Essays Dedicated to Arto Salomaa on the Occasion of His 70th Birthday. J.Karhumaki, H.Maurer, G.Paun, G.Rozenberg (Eds.), LNCS 3113, 134-144.
We consider sets of rectangles and squares recognized by deterministic and non-deterministic two-dimensional finite-state automata. We show that sets of squares recognized by DFAs from the inside can be as sparse as any recursively enumerable set. We also show that NFAs can only recognize sets of rectangles from the outside that correspond to simple regular languages.