The investigation of the computational power of randomized computations
is one of the central tasks of current complexity and algorithm theory.
In this paper for the first time a "strong" separation between the power
of determinism, Las Vegas randomization, and nondeterminism for a compu-
ting model is proved. The computing model considered here are finite au-
tomata with two-dimensional input tapes (i.e., finite automata recognizing
picture languages). Moreover, a hierarchy on the degree of nondeterminism
of two-dimensional finite automata is proved.