New Results on Alternating and Non-Deterministic Two-Dimensional Finite-State Automata

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.