首页 | 本学科首页   官方微博 | 高级检索  
     


On probabilistic analog automata
Authors:Asa Ben-Hur   Alexander Roitershtein  H.T.Hava T. Siegelmann
Affiliation:

a Department of Biochemistry, B400 Beckman Center, Stanford University, CA 94305-5307, USA

b Department of Mathematics, Technion - IIT, Haifa 32000, Israel

c Department of Computer Science, University of Massachusetts at Amherst, 710 N. Pleasant Street, Amherst, MA 01003-9305, USA

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.
Keywords:Probabilistic automata   Probabilistic computation   Noisy computational systems   Regular languages   Definite languages   Markov operators
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号