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 grid graphs with crossover is AFA-recognizable but not tiling recognizable, while its complement is tiling recognizable but not AFA-recognizable. Since we also show that the complement of an AFA-recognizable language is tiling recognizable, it follows that the AFA-recognizable languages are not closed under complementation. In addition, we show that the set of languages recognized by 4-way NFAs is not closed under complementation, and that NFAs are more powerful than DFAs, even for languages over one symbol.
展开▼
