On probabilistic analog automata
| dc.creator | Ben-Hur, A. | |
| dc.creator | Roitershtein, A. | |
| dc.creator | Siegelmann, H. | |
| dc.date | 2003-04-29 | |
| dc.date | 2003-04-30 | |
| dc.date.accessioned | 2026-07-07T03:19:38Z | |
| dc.date.available | 2026-07-07T03:19:38Z | |
| dc.description | 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. | |
| dc.identifier | https://arxiv.org/abs/cs/0304042 | |
| dc.identifier | http://arxiv.org/abs/cs/0304042 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/31540 | |
| dc.subject | Other Computer Science | |
| dc.subject | F.1.1; F.1.2 | |
| dc.title | On probabilistic analog automata | |
| dc.type | text |