{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T04:19:13Z","timestamp":1742617153102,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":52,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540544586"},{"type":"electronic","value":"9783540383918"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1991]]},"DOI":"10.1007\/3-540-54458-5_53","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T22:51:13Z","timestamp":1330210273000},"page":"89-103","source":"Crossref","is-referenced-by-count":2,"title":["A survey of some aspects of computational learning theory"],"prefix":"10.1007","author":[{"given":"Gy\u00f6rgy","family":"Tur\u00e1n","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,9]]},"reference":[{"key":"10_CR1","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1016\/S0019-9958(81)90090-5","volume":"51","author":"D. Angluin","year":"1981","unstructured":"Angluin, D. (1981). A note on the number of queries needed to identify regular languages. Information and Control, 51, 76\u201387.","journal-title":"Information and Control"},{"key":"10_CR2","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/0890-5401(87)90052-6","volume":"75","author":"D. Angluin","year":"1987","unstructured":"Angluin, D. (1987). Learning regular sets from queries and counterexamples. Information and Computation, 75, 87\u2013106.","journal-title":"Information and Computation"},{"key":"10_CR3","first-page":"319","volume":"2","author":"D. Angluin","year":"1988","unstructured":"Angluin, D. (1988). Queries and concept learning, Machine Learning, 2, 319\u2013342.","journal-title":"Machine Learning"},{"key":"10_CR4","first-page":"121","volume":"5","author":"D. Angluin","year":"1990","unstructured":"Angluin, D. (1990). Negative results for equivalence queries. Machine Learning, 5, 121\u2013150.","journal-title":"Machine Learning"},{"key":"10_CR5","doi-asserted-by":"crossref","unstructured":"Angluin, D., Frazier, M. and Pitt, L. (1990). Learning conjunctions of Horn clauses. 31. FOCS, 186\u2013192.","DOI":"10.1109\/FSCS.1990.89537"},{"key":"10_CR6","unstructured":"Angluin, D., Hellerstein, L. and Karpinski, M. (1989). Learning read-once formulas with queries. (Technical Report UCB\/CSD 89\/527). University of California at Berkeley, Computer Science Division. (also, Technical Report TR-89-050, International Computer Science Institute, Berkeley, California.) To appear, JACM."},{"key":"10_CR7","doi-asserted-by":"crossref","unstructured":"Angluin, D. and Kharitonov, M. (1991). When won't membership queries help. 23. STOC, 444\u2013454.","DOI":"10.1145\/103418.103420"},{"key":"10_CR8","doi-asserted-by":"crossref","unstructured":"Anthony, M., Biggs, N. and Shawe-Taylor, J. (1990). The learnability of formal concepts. 3. COLT, 232\u2013246.","DOI":"10.1016\/B978-1-55860-146-8.50022-9"},{"key":"10_CR9","unstructured":"Beals, R. (1990). Unpublished manuscript."},{"key":"10_CR10","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1016\/0020-0190(87)90114-1","volume":"24","author":"A. Blumer","year":"1987","unstructured":"Blumer, A., Ehrenfeucht, A., Haussler, D. and Warmuth, M.K. (1987). Occam's razor. Information Processing Letters, 24, 377\u2013380.","journal-title":"Information Processing Letters"},{"key":"10_CR11","doi-asserted-by":"crossref","first-page":"939","DOI":"10.1145\/76359.76371","volume":"36","author":"A. Blumer","year":"1989","unstructured":"Blumer, A., Ehrenfeucht, A., Haussler, D., and Warmuth, M.K. (1989). Learnability and the Vapnik-Chervonenkis dimension. JACM, 36, 939\u2013965.","journal-title":"JACM"},{"key":"10_CR12","doi-asserted-by":"crossref","unstructured":"Board, R. and Pitt, L. (1990). On the necessity of Occam algorithms. 22. STOC, 54\u201363.","DOI":"10.1145\/100216.100223"},{"key":"10_CR13","unstructured":"Chen, Z.X. (1991). Unpublished manuscript."},{"key":"10_CR14","unstructured":"Ehrenfeucht, A., Haussler, D., Kearns, M. and Valiant, L.G. (1988). A general lower bound on the number of examples needed for learning. COLT 1988, 139\u2013154."},{"key":"10_CR15","unstructured":"Faigle, U. and Kern, W. (1990). On learnability of monotone DNF functions under uniform distribution. University of Twente, Faculty of Applied Mathematics, Memo. No. 863."},{"key":"10_CR16","doi-asserted-by":"crossref","unstructured":"Floyd, S. (1989). Space-bounded learning and the Vapnik-Chervonenkis dimension. 2. COLT, 349\u2013364.","DOI":"10.1016\/B978-0-08-094829-4.50028-3"},{"key":"10_CR17","doi-asserted-by":"crossref","unstructured":"Freund, Y. (1990). Boosting a weak learning algorithm by majority. 3. COLT, 202\u2013216.","DOI":"10.1016\/B978-1-55860-146-8.50019-9"},{"key":"10_CR18","unstructured":"Fulk, M.A. and Chase, J., editors. (1990). Proceedings of the Third Annual Conference on Computational Learning Theory. Morgan Kauffman."},{"key":"10_CR19","doi-asserted-by":"crossref","first-page":"447","DOI":"10.1016\/S0019-9958(67)91165-5","volume":"10","author":"E.M. Gold","year":"1967","unstructured":"Gold, E.M. (1967). Language identification in the limit. Information and Control, 10, 447\u2013474.","journal-title":"Information and Control"},{"key":"10_CR20","doi-asserted-by":"crossref","first-page":"792","DOI":"10.1145\/6490.6503","volume":"33","author":"O. Goldreich","year":"1986","unstructured":"Goldreich, O., Goldwasser, S. and Micali, S. (1986). How to construct random functions. JACM, 33, 792\u2013807.","journal-title":"JACM"},{"key":"10_CR21","doi-asserted-by":"crossref","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L. and Schrijver, A. (1988). Geometric Algorithms and Combinatorial Optimization. Springer, Algorithms and Combinatorics Vol. 2.","DOI":"10.1007\/978-3-642-97881-4"},{"key":"10_CR22","unstructured":"Haussler, D. (1989). Generalizing the PAC model for neural net and other learning applications. (Technical Report UCSC-CRL-89-30). University of California at Santa Cruz, Computer Research Laboratory. To appear, Information and Computation."},{"key":"10_CR23","unstructured":"Haussler, D. (1990). Probably approximately correct learning. Eight National AI Conference, AAAI'90, 1101\u20131108."},{"key":"10_CR24","unstructured":"Haussler, D., Kearns, M., Littlestone, N. and Warmuth, M.K. (1988). Equivalence of models for polynomial learnability. COLT 1988, 42\u201355. To appear, Information and Computation."},{"key":"10_CR25","unstructured":"Haussler, D., Littlestone, N. and Warmuth, M.K. (1988). Predicting {0,1}-functions on randomly drawn points. 29. FOCS, 100\u2013109."},{"key":"10_CR26","unstructured":"Haussler, D. and Pitt, L., editors. (1988). Proceedings of the 1988 Workshop on Computational Learning Theory. Morgan Kauffman."},{"key":"10_CR27","doi-asserted-by":"crossref","unstructured":"Kearns, M.J. and Schapire, R.E. (1990). Efficient distribution-free learning of probabilistic concepts. 31. FOCS, 382\u2013391.","DOI":"10.1109\/FSCS.1990.89557"},{"key":"10_CR28","unstructured":"Kearns, M. and Valiant, L.G. (1989). Cryptographic limitations on learning Boolean formulae and finite automata. 21. STOC, 433\u2013444."},{"key":"10_CR29","first-page":"1093","volume":"244","author":"L.G. Khachian","year":"1979","unstructured":"Khachian, L.G. (1979). A polynomial algorithm in linear programming. Doklady Akademii Nauk SSSR, 244, 1093\u20131096. English translation: Soviet Mathematics Doklady, 20, 191\u2013194.","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"10_CR30","doi-asserted-by":"crossref","unstructured":"Linial, N., Mansour, Y. and Nisan, N. (1989). Constant depth circuits, Fourier transform and learnability. 30. FOCS, 574\u2013579.","DOI":"10.1109\/SFCS.1989.63537"},{"key":"10_CR31","first-page":"285","volume":"2","author":"N. Littlestone","year":"1988","unstructured":"Littlestone, N. (1988). Learning quickly when irrelevant attributes abound: a new linear-threshold algorithm. Machine Learning, 2, 285\u2013318.","journal-title":"Machine Learning"},{"key":"10_CR32","doi-asserted-by":"crossref","unstructured":"Maass, W. and Tur\u00e1n, Gy. (1989). On the complexity of learning from counterexamples. 30. FOCS, 262\u2013267.","DOI":"10.1109\/SFCS.1989.63488"},{"key":"10_CR33","doi-asserted-by":"crossref","unstructured":"Maass, W. and Tur\u00e1n, Gy. (1990 a). On the complexity of learning from counterexamples and membership queries. 31. FOCS, 203\u2013210.","DOI":"10.1016\/B978-1-55860-146-8.50037-0"},{"key":"10_CR34","unstructured":"Maass, W. and Tur\u00e1n, Gy. (1990 b). Lower bounds and separation results for on-line learning models. To appear, Machine Learning."},{"key":"10_CR35","unstructured":"Maass, W. and Tur\u00e1n, Gy. (1990 c). Algorithms and lower bounds for on-line learning of geometrical concepts. Unpublished manuscript."},{"key":"10_CR36","unstructured":"Maass, W. and Tur\u00e1n, Gy. (1990 d). How fast can a threshold gate learn? To appear in: Hanson, S., Drastal, G. and Rivest, R., Editors, Computational Learning Theory and Natural Learning Systems: Constraints and Prospects, MIT Press."},{"key":"10_CR37","doi-asserted-by":"crossref","unstructured":"Maimonides, M. (1963). The Guide of the Perplexed. Translated by Shlomo Pines. University of Chicago Press.","DOI":"10.7208\/chicago\/9780226842608.001.0001"},{"key":"10_CR38","unstructured":"Minsky, M. and Papert, S. (1988). Perceptrons: an introduction to computational geometry, Expanded edition. MIT Press."},{"key":"10_CR39","unstructured":"Natarajan, B.K. (1987). Learning functions from examples. Technical Report CMU-R1-TR-87-19. Carnegie-Mellon University."},{"key":"10_CR40","unstructured":"Nilsson, N.J. (1965). Learning machines. McGraw-Hill."},{"key":"10_CR41","doi-asserted-by":"crossref","unstructured":"Naor, M. and Yung, M. (1990). Public-key cryptosystems provably secure against chosen ciphertext attacks. 22. STOC, 427\u2013437.","DOI":"10.1145\/100216.100273"},{"key":"10_CR42","doi-asserted-by":"crossref","first-page":"965","DOI":"10.1145\/48014.63140","volume":"35","author":"L. Pitt","year":"1988","unstructured":"Pitt, L. and Valiant, L.G. (1988). Computational limitations on learning from examples. JACM, 35, 965\u2013984.","journal-title":"JACM"},{"key":"10_CR43","doi-asserted-by":"crossref","unstructured":"Pitt, L. and Warmuth, M.K. (1989). The minimum consistent DFA problem cannot be approximated within any polynomial. 21. STOC, 421\u2013432. To apear, JACM.","DOI":"10.1109\/SCT.1989.41829"},{"key":"10_CR44","unstructured":"Rivest, R., Haussler, D. and Warmuth, M.K., editors. (1989). Proceedings of the Second Annual Conference on Computational Learnign Theory. Morgan Kauffman."},{"key":"10_CR45","unstructured":"Rosenblatt, F. (1962). Principles of neurodynamics. Spartan Books."},{"key":"10_CR46","doi-asserted-by":"crossref","unstructured":"Rumelhart, D.E. and McClelland, J.L. (1986). Parallel distributed processing: explorations in the microstructure of cognition. MIT Press.","DOI":"10.7551\/mitpress\/5236.001.0001"},{"key":"10_CR47","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1016\/0097-3165(72)90019-2","volume":"13","author":"N. Sauer","year":"1972","unstructured":"Sauer, N. (1972). On the density of families of sets. Journal of Combinatorial Theory (A), 13, 145\u2013147.","journal-title":"Journal of Combinatorial Theory (A)"},{"key":"10_CR48","first-page":"197","volume":"5","author":"R.E. Schapire","year":"1990","unstructured":"Schapire, R.E. (1990). The strength of weak learnability. Machine Learning, 5, 197\u2013227.","journal-title":"Machine Learning"},{"key":"10_CR49","unstructured":"Sloan, R.H. (1988). Types of noise in data for concept learning. COLT 1988, 91\u201396."},{"key":"10_CR50","doi-asserted-by":"crossref","unstructured":"Vaidya, P.M. (1989). A new algorithm for minimizing convex functions over convex sets. 30. FOCS, 338\u2013343.","DOI":"10.1109\/SFCS.1989.63500"},{"key":"10_CR51","doi-asserted-by":"crossref","first-page":"1134","DOI":"10.1145\/1968.1972","volume":"27","author":"L.G. Valiant","year":"1984","unstructured":"Valiant, L.G. (1984). A theory of the learnable. CACM, 27, 1134\u20131142.","journal-title":"CACM"},{"key":"10_CR52","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1137\/1116025","volume":"16","author":"V.N. Vapnik","year":"1971","unstructured":"Vapnik, V.N. and Chervonenkis, A.Ya. (1971). On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and Its Applications, 16, 264\u2013280.","journal-title":"Theory of Probability and Its Applications"}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-54458-5_53.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T21:19:48Z","timestamp":1742591988000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-54458-5_53"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991]]},"ISBN":["9783540544586","9783540383918"],"references-count":52,"URL":"https:\/\/doi.org\/10.1007\/3-540-54458-5_53","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1991]]}}}