Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

Date and Time: Tuesday, January 13, 2009, 12:15 pm

Duration: This information is not available in the database

Location: OAT S15/S16/S17

Speaker: Richard Královič

An Exponential Gap between Linear and Exponential Expected Time in Probabilistic Sweeping Finite Automata

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.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login