Infinite vs. finite size-bounded randomized computations

Randomized computations can be very powerful with respect to space complexity, e.g., for logarithmic space, LasVegas is equivalent to nondeterminism. This power depends on the possibility of infinite computations, however, it is an open question if they are necessary. We answer this question for rotating finite automata (RFAs) and sweeping finite automata (sFAs). We show that LasVegas RMS (SPAS) allowing infinite computations, although only with probability 0, can be exponentially smaller than LasVegas RFAS (SFAS) forbidding them. In particular, we show that even RFAS (SFAS) with linear expected running time may require exponentially more states than RFAS (SFAS) running in exponential time. We also strengthen this result, showing that the restriction on time cannot be traded for the more powerful bounded-error randomization. To prove our results, we introduce a technique for proving lower bounds on size of RFAS (SFAS) that generalizes the notion of generic strings discovered by M. Sipser. (C) 2013 Elsevier Inc. All rights reserved.