pith. sign in

arxiv: cs/0304042 · v2 · submitted 2003-04-29 · 💻 cs.OH

On probabilistic analog automata

classification 💻 cs.OH
keywords automataprobabilisticanalogcomputationalmaasspowerrabinautomaton
0
0 comments X
read the original abstract

We consider probabilistic automata on a general state space and study their computational power. The model is based on the concept of language recognition by probabilistic automata due to Rabin and models of analog computation in a noisy environment suggested by Maass and Orponen, and Maass and Sontag. Our main result is a generalization of Rabin's reduction theorem that implies that under very mild conditions, the computational power of the automaton is limited to regular languages.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.