Parallel Learning of Automatic Classes of Languages
作者： Sanjay Jain , Efim Kinber
DOI: 10.1007/978-3-319-11662-4_6
关键词: Limit (mathematics) 、 Theoretical computer science 、 Bipartite graph 、 Computer science 、 Characterization (mathematics) 、 Inductive reasoning 、 Finite-state machine 、 Learnability 、 Parallel learning
摘要: We introduce and explore a model for parallel learning of families languages computable by finite automata. In this model, an algorithmic or automatic learner takes on n different input identifies at least m them correctly. For learning, large enough families, we establish full characterization learnability in terms characteristic samples languages. Based characterization, show that it is the difference − m, number which are potentially not identified, crucial. Similar results obtained also limit. consider automata obtain some partial results. A problems variant remain open.
springer.com
sacredheart.edu参考文章(27)
Daniel N. Osherson, James S. Royer, Sanjay Jain, Arun Sharma, Systems That Learn: An Introduction to Learning Theory ,(1999)
Kaspars Balodis, Ilja Kucevalovs, Rūsiņš Freivalds, Frequency prediction of functions mathematical and engineering methods in computer science. pp. 76- 83 ,(2011) , 10.1007/978-3-642-25929-6_7
Yasuhito Mukouchi, Characterization of Finite Identification AII '92 Proceedings of the International Workshop on Analogical and Inductive Inference. pp. 260- 267 ,(1992) , 10.1007/3-540-56004-1_18
Bakhadyr Khoussainov, Anil Nerode, Automatic Presentations of Structures logical and computational complexity. pp. 367- 392 ,(1994) , 10.1007/3-540-60178-3_93
E Mark Gold, Language identification in the limit Information & Computation. ,vol. 10, pp. 447- 474 ,(1967) , 10.1016/S0019-9958(67)91165-5
Steffen Lange, Thomas Zeugmann, Types of monotonic language learning and their characterization conference on learning theory. pp. 377- 390 ,(1992) , 10.1145/130385.130427
Holger Austinat, Volker Diekert, Ulrich Hertrampf, Holger Petersen, Regular frequency computations Theoretical Computer Science. ,vol. 330, pp. 15- 21 ,(2005) , 10.1016/J.TCS.2004.09.007
Lenore Blum, Manuel Blum, Toward a mathematical theory of inductive inference Information and Control. ,vol. 28, pp. 125- 155 ,(1975) , 10.1016/S0019-9958(75)90261-2
R. Wiehagen, R. Freivalds, E.B. Kinber, On the power of probabilistic strategies in inductive inference Theoretical Computer Science. ,vol. 28, pp. 111- 133 ,(1983) , 10.1016/0304-3975(83)90067-1
E. B. Kinber, Frequency computations in finite automata Cybernetics and Systems Analysis. ,vol. 12, pp. 179- 187 ,(1977) , 10.1007/BF01069884