Lower Bounds for Las Vegas Automata by Information Theory
TUCS-Turku Centre for Computer Science and
Department of Mathematics, University of Turku,
FIN-20014 Turku, Finland; .
Supported by the academy of Finland
under grant 44087.
2 Lehrstuhl für Informatik I, RWTH Aachen, Ahornstraße 55, 52074 Aachen, Germany; .
Accepted: March 2003
We show that the size of a Las Vegas automaton and the size of a complete, minimal deterministic automaton accepting a regular language are polynomially related. More precisely, we show that if a regular language L is accepted by a Las Vegas automaton having r states such that the probability for a definite answer to occur is at least p, then r ≥ np, where n is the number of the states of the minimal deterministic automaton accepting L. Earlier this result has been obtained in  by using a reduction to one-way Las Vegas communication protocols, but here we give a direct proof based on information theory.
Mathematics Subject Classification: 68Q19 / 68Q10 / 94A15
Key words: Las Vegas automata / information theory
© EDP Sciences, 2003