TR99-007 Authors: Juraj Hromkovic, Georg Schnitger

Publication: 15th March 1999 17:29

Downloads: 1118

Keywords:

The investigation of the computational power of randomized

computations is one of the central tasks of current complexity and

algorithm theory. This paper continues in the comparison of the computational

power of LasVegas computations with the computational power of deterministic

and nondeterministic ones. While for one-way finite automata the comparison

of different computational modes was successfully determined one does not

have any nontrivial result relating the powers of determinism, Las Vegas and

nondeterminism for two-way finite automata. The four main results of this

paper are the following ones:

1, If, for a regular language L, there exist small two-way

nondeterministic finite automata for both L and the complement of L,

then there exists a small two-way Las Vegas finite automaton for L.

2, There is a quadratic gap between nondeterminism and LasVegas for

the size of two-way finite automata.

3, There is an almost quadratic gap between Las Vegas and determinism

for the size of two-way finite automata.

4, Two-way Las Vegas finite automata can be much more powerful than

one-way nondeterministic finite automata. A consequence is an

exponential gap between one-way Las Vegas finite

automata and two-way Las Vegas finite automata.