Issue Theoret. Informatics Appl. Volume 37, Number 1, January-March 2003 Page(s) 39 - 49 DOI 10.1051/ita:2003007

Theoret. Informatics Appl. 37, 39-49 (2003)
DOI: 10.1051/ita:2003007

Lower Bounds for Las Vegas Automata by Information Theory

Mika Hirvensalo¹ and Sebastian Seibert<sup>2

1</sup>  TUCS-Turku Centre for Computer Science and Department of Mathematics, University of Turku, FIN-20014 Turku, Finland; mikhirve@cs.utu.fi. Supported by the academy of Finland under grant 44087.
²  Lehrstuhl für Informatik I, RWTH Aachen, Ahornstraße 55, 52074 Aachen, Germany; seibert@I1.Informatik.RWTH-Aachen.DE.

(Received December, 2001. Accepted March, 2003.)

Abstract
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 , where n is the number of the states of the minimal deterministic automaton accepting L. Earlier this result has been obtained in [2] 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

What is OpenURL?