EUDML | A probabilistic approach to automaton-environment systems

Skip to main content (access key 's'), Skip to navigation (access key 'n'), Accessibility information (access key '0')

Displaying similar documents to “A probabilistic approach to automaton-environment systems”

A selection-based formal description of an environment

Ivan Kramosil (1976)

Kybernetika

Similarity:

Mechanized experiment planning in automaton-environment systems

Ivan Kramosil (1977)

Kybernetika

Similarity:

Synthesis of non-initial automata

Ján Černý (1967)

Kybernetika

Similarity:

Lower bounds for Las Vegas automata by information theory

Mika Hirvensalo, Sebastian Seibert (2003)

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

Similarity:

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