Advanced Search

Match of the following rules

Add Sub-clause

Add Another Rule

Contains the following math formula (red border means the formula is incomplete)

Formula preview

Currently displaying 1 – 2 of 2

Order by Relevance | Title | Year of publication

Lower bounds for Las Vegas automata by information theory

Mika Hirvensalo; Sebastian Seibert — 2003

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

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

Lower Bounds for Las Vegas Automata by Information Theory

Mika Hirvensalo; Sebastian Seibert — 2010

RAIRO - Theoretical Informatics and Applications

We show that the size of a automaton and the size of a complete, minimal automaton accepting a regular language are polynomially related. More precisely, we show that if a regular language is accepted by a Las Vegas automaton having states such that the probability for a definite answer to occur is at least , then , where is the number of the states of the minimal deterministic automaton accepting . Earlier this result has been obtained in [2] by using a reduction to , but here we give a direct...

Page 1

Download Results (CSV)