# Lower bounds for Las Vegas automata by information theory

Mika Hirvensalo; Sebastian Seibert

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2003)

- 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 - Informatique Théorique et Applications 37.1 (2003): 39-49. <http://eudml.org/doc/245009>.

@article{Hirvensalo2003,

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

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

journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},

keywords = {Las Vegas automata; information theory},

language = {eng},

number = {1},

pages = {39-49},

publisher = {EDP-Sciences},

title = {Lower bounds for Las Vegas automata by information theory},

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

volume = {37},

year = {2003},

}

TY - JOUR

AU - Hirvensalo, Mika

AU - Seibert, Sebastian

TI - Lower bounds for Las Vegas automata by information theory

JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

PY - 2003

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\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.

LA - eng

KW - Las Vegas automata; information theory

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

ER -

## References

top- [1] T.M. Cover and J.A. Thomas, Elements of Information Theory. John Wiley & Sons, Inc. (1991). Zbl0762.94001MR1122806
- [2] P. Ďuris, J. Hromkovič, 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. MR1473768
- [3] J. Hromkovič, personal communication.
- [4] 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.68058MR2115303
- [5] C.H. Papadimitriou, Computational Complexity. Addison-Wesley (1994). Zbl0833.68049MR1251285
- [6] S. Yu, Regular Languages, edited by G. Rozenberg and A. Salomaa. Springer, Handb. Formal Languages I (1997).

## NotesEmbed ?

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