Symposium on Theoretical Aspects of Computer Science (STACS) 2001.

We resolve several long-standing open questions regarding the power of various types of finite-state automata to recognize ``picture languages,'' i.e. sets of two-dimensional arrays of symbols. We show that the languages recognized by 4-way alternating finite-state automata (AFAs) are incomparable to the so-called tiling recognizable languages. Specifically, we show that the set of acyclic directed graphs is AFA-recognizable but not tiling recognizable, while the set of non-acyclic directed graphs is tiling recognizable but not AFA-recognizable. More generally, the complement of an AFA-recognizable language is tiling recognizable, and therefore the AFA-recognizable languages are not closed under complement. We also show that the set of languages recognized by 4-way NFAs is not closed under complement, and that NFAs are more powerful than DFAs, even for languages over one symbol.

Cris Moore <moore@santafe.edu>