Lower Bounds for Las Vegas Automata by Information Theory

Issue		RAIRO-Theor. Inf. 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²

¹ 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 $r\ge n^p$ , 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?

The OpenURL standard is a protocol for transmission of metadata describing the resource that you wish to access. An OpenURL link contains article metadata and directs it to the OpenURL server of your choice. The OpenURL server can provide access to the resource and also offer complementary services (specific search engine, export of references...). The OpenURL link can be generated by different means.

If your librarian has set up your subscription with an OpenURL resolver, OpenURL links appear automatically on the abstract pages.
You can define your own OpenURL resolver with your EDPS Account. In this case your choice will be given priority over that of your library.
You can use an add-on for your browser (Firefox or I.E.) to display OpenURL links on a page (see http://www.openly.com/openurlref/). You should disable this module if you wish to use the OpenURL server that you or your library have defined.