  A two-dimensional finite automaton has a read-only input head that moves in
four directions on a finite array of cells labelled by symbols of the input
alphabet. A three-way two-dimensional automaton is prohibited from making
upward moves, while a two-way two-dimensional automaton can only move downward
and rightward.
  We show that the language emptiness problem for unary three-way
nondeterministic two-dimensional automata is NP-complete, and is in P for
general-alphabet two-way nondeterministic two-dimensional automata. We show
that the language equivalence problem for two-way deterministic two-dimensional
automata is decidable, while both the equivalence and universality problems for
two-way nondeterministic two-dimensional automata are undecidable. The
deterministic case is the first known positive decidability result for the
equivalence problem on two-dimensional automata over a general alphabet. We
show that there exists a unary three-way deterministic two-dimensional
automaton with a nonregular column projection, and we show that the row
projection of a unary three-way nondeterministic two-dimensional automaton is
always regular.
