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

Abstract

top
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 ≥ 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.

How to cite

top

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

NotesEmbed ?

top

You must be logged in to post comments.