Rectangles and squares recognized by two-dimensional automata

Jarkko Kari and Cristopher Moore

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.

Click here to download.

Cris Moore <>