Frequency prediction of functions
作者： Kaspars Balodis , Ilja Kucevalovs , Rūsiņš Freivalds
DOI: 10.1007/978-3-642-25929-6_7
关键词: Probabilistic analysis of algorithms 、 Algorithm 、 Probabilistic logic 、 Inductive reasoning 、 Randomized algorithm 、 Hierarchy (mathematics) 、 Existential quantification 、 Mathematics 、 Computation 、 Black box
摘要: Prediction of functions is one processes considered in inductive inference. There a "black box" with given total function f it. The result the inference machine F( ) expected to be f(n+1). Deterministic and probabilistic prediction has been widely studied. Frequency computation mechanism used combine features deterministic algorithms. for several types inference, especially, learning via queries. We study frequency show that there exists an interesting hierarchy predictable classes functions.
springer.com
sci-hub.st 参考文章(26)
Robert McNaughton, The Theory of Automata, a Survey Advances in Computers. ,vol. 2, pp. 379- 421 ,(1961) , 10.1016/S0065-2458(08)60144-8
RūsiņŠ Freivalds, Complexity of Probabilistic Versus Deterministic Automata Baltic Computer Science, Selected Papers. pp. 565- 613 ,(1991) , 10.1007/BFB0019368
Farid M. Ablaev, Rūsiņš Freivalds, Why Sometimes Probabilistic Algorithms Can Be More Effective mathematical foundations of computer science. pp. 1- 14 ,(1996) , 10.1007/BFB0016230
RŪsiņš Freivalds, Models of Computation, Riemann Hypothesis, and Classical Mathematics conference on current trends in theory and practice of informatics. pp. 89- 106 ,(1998) , 10.1007/3-540-49477-4_6
Rūsiņš Freivalds, Amount of Nonconstructivity in Finite Automata international conference on implementation and application of automata. pp. 227- 236 ,(2009) , 10.1007/978-3-642-02979-0_26
Rūsiņš Freivalds, Jānis Bārzdiņš, Kārlis Podnieks, Inductive Inference of Recursive Functions: Complexity Bounds Baltic Computer Science, Selected Papers. pp. 111- 155 ,(1991) , 10.1007/BFB0019358
Rūsiņš Freivalds, Inductive Inference of Recursive Functions: Qualitative Theory Baltic Computer Science, Selected Papers. pp. 77- 110 ,(1991) , 10.1007/BFB0019357
Kalvis Apsītis, Rūsinš Freivalds, Mārtinš Krikis, Raimonds Simanovskis, Juris Smotrovs, Unions of Identifiable Classes of Total Recursive Functions AII '92 Proceedings of the International Workshop on Analogical and Inductive Inference. pp. 99- 107 ,(1992) , 10.1007/3-540-56004-1_7
E Mark Gold, Language identification in the limit Information & Computation. ,vol. 10, pp. 447- 474 ,(1967) , 10.1016/S0019-9958(67)91165-5
Rūsiņš Freivalds, Amount of nonconstructivity in deterministic finite automata Theoretical Computer Science. ,vol. 411, pp. 3436- 3443 ,(2010) , 10.1016/J.TCS.2010.05.038