Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR00-027 | 11th April 2000 00:00

A Separation of Determinism, Las Vegas and Nondeterminism for Picture Recognition

RSS-Feed




TR00-027
Authors: Pavol Duris, Juraj Hromkovic, Katsushi Inoue
Publication: 23rd May 2000 16:09
Downloads: 1035
Keywords: 


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.



ISSN 1433-8092 | Imprint