# Lower Bounds for Las Vegas Automata by Information Theory

Mika Hirvensalo; Sebastian Seibert

RAIRO - Theoretical Informatics and Applications (2010)

- Volume: 37, Issue: 1, page 39-49
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topHirvensalo, Mika, and Seibert, Sebastian. "Lower Bounds for Las Vegas Automata by Information Theory." RAIRO - Theoretical Informatics and Applications 37.1 (2010): 39-49. <http://eudml.org/doc/92712>.

@article{Hirvensalo2010,

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 ≥ np, 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.
},

author = {Hirvensalo, Mika, Seibert, Sebastian},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {Las Vegas automata; information theory},

language = {eng},

month = {3},

number = {1},

pages = {39-49},

publisher = {EDP Sciences},

title = {Lower Bounds for Las Vegas Automata by Information Theory},

url = {http://eudml.org/doc/92712},

volume = {37},

year = {2010},

}

TY - JOUR

AU - Hirvensalo, Mika

AU - Seibert, Sebastian

TI - Lower Bounds for Las Vegas Automata by Information Theory

JO - RAIRO - Theoretical Informatics and Applications

DA - 2010/3//

PB - EDP Sciences

VL - 37

IS - 1

SP - 39

EP - 49

AB -
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 [2] by using a reduction to one-way Las Vegas communication
protocols, but here we give a direct proof based on information theory.

LA - eng

KW - Las Vegas automata; information theory

UR - http://eudml.org/doc/92712

ER -

## References

top- T.M. Cover and J.A. Thomas, Elements of Information Theory. John Wiley & Sons, Inc. (1991). Zbl0762.94001
- P. Duris, J. Hromkovic, J.D.P. Rolim and G. Schnitger, Las Vegas Versus Determinism for One-way Communication Complexity, Finite Automata, and Polynomial-time Computations. Springer, Lecture Notes in Comput. Sci. 1200 (1997) 117-128.
- J. Hromkovic, personal communication.
- H. Klauck, On quantum and probabilistic communication: Las Vegas and one-way protocols, in Proc. of the ACM Symposium on Theory of Computing (2000) 644-651. Zbl1296.68058
- C.H. Papadimitriou, Computational Complexity. Addison-Wesley (1994).
- S. Yu, Regular Languages, edited by G. Rozenberg and A. Salomaa. Springer, Handb. Formal Languages I (1997).

## Citations in EuDML Documents

top## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.