Abstract:
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.