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

Jarkko Kari and Cristopher Moore

00-09-051

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 four-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 four-way NFAs is not closed under complement, and that NFAs are more powerful than DFAs, even for languages over one symbol.