Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, January 13, 2009, 12:15 pm
Duration: This information is not available in the database
Location: CAB G51
Speaker: Richard Královič
Probabilistic computations can be very powerful with respect to space complexity, e.g. for logarithmic space, zero probability of error is equivalent to nondeterminism. This power, however, depends on the possibility of infinite computations. A natural open question is if this feature is necessary. We answer the question for sweeping finite automata (SFAs), i.e. two-way finite automata that can change the direction of head motion at endmarkers only. We show that zero probability of error SFAs allowing infinite computations can be exponentially more succinct than zero probability of error SFAs forbidding them. More precisely, we show a stronger result providing a family of languages that can be accepted by small zero probability of error SFAs running in exponential time, but (two-sided) bounded error SFAs running in linear time require exponentially more states. Hence, the restriction in time can not be traded for the more powerful bounded-error probabilistic model.
Automatic MiSe System Software Version 1.4803M | admin login