Name
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 (Inform. Control 3 (1963) 230) and models of analog computation in a noisy environment suggested by Maass and Orponen (Neural Comput. 10 (1998) 1071), and Maass and Sontag (Neural Comput. 11 (1999) 771). Our main result is a generalization of Rabin's reduction theorem that implies that under very mild conditions, the computational power of such automata is limited to regular languages. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1016/j.tcs.2004.03.003 | Theoretical Computer Science |
Keywords | DocType | Volume |
language recognition,definite languages.,probabilistic automata,neural comput,computational power,regular languages,reduction theorem,noisy computational systems,main result,general state space,noisy environment,mild condition,probabilistic computation,markov operators,probabilistic analog automaton,definite languages,probabilistic automaton,noisy computational sys- tems,analog computation,regular language,state space | Journal | 320 |
Issue | ISSN | Citations |
2-3 | Theoretical Computer Science | 2 |
PageRank | References | Authors |
0.37 | 7 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Asa Ben-Hur | 1 | 1405 | 110.73 |
| Alexander Roitershtein | 2 | 2 | 2.07 |
| Hava T. Siegelmann | 3 | 980 | 145.09 |