| Issue |
RAIRO-Theor. Inf. Appl.
Volume 37, Number 1, January/March 2003
|
|
|---|---|---|
| Page(s) | 39 - 49 | |
| DOI | https://doi.org/10.1051/ita:2003007 | |
| Published online | 15 November 2003 | |
Lower Bounds for Las Vegas Automata by Information Theory
1
TUCS-Turku Centre for Computer Science and
Department of Mathematics, University of Turku,
FIN-20014 Turku, Finland; .
Supported by the academy of Finland
under grant 44087.
2
Lehrstuhl für Informatik I, RWTH Aachen, Ahornstraße
55, 52074 Aachen, Germany; .
Received:
December
2001
Accepted:
March
2003
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.
Mathematics Subject Classification: 68Q19 / 68Q10 / 94A15
Key words: Las Vegas automata / information theory
© EDP Sciences, 2003
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.