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.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.