  A three-way (resp., two-way) two-dimensional automaton has a read-only input
head that moves in three (resp., two) directions on a finite array of cells
labelled by symbols of the input alphabet. Restricting the input head movement
of a two-dimensional automaton results in a model that is weaker in terms of
recognition power.
  In this paper, we introduce the notion of "degrees of restriction" for
two-dimensional automata, and we develop sets of extended two-dimensional
automaton models that allow for some bounded number of restricted moves. We
establish recognition hierarchies for both deterministic and nondeterministic
extended three-way two-dimensional automata, and we find similar hierarchies
for both deterministic and nondeterministic extended two-way two-dimensional
automata. We also prove incomparability results between nondeterministic and
deterministic extended three-way two-dimensional automata. Lastly, we consider
closure properties for some operations on languages recognized by extended
three-way two-dimensional automata.
