{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:46:55Z","timestamp":1759063615179},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"2-3","license":[{"start":{"date-parts":[[1992,7,1]],"date-time":"1992-07-01T00:00:00Z","timestamp":709948800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mach Learn"],"published-print":{"date-parts":[[1992,7]]},"DOI":"10.1007\/bf00992674","type":"journal-article","created":{"date-parts":[[2005,1,14]],"date-time":"2005-01-14T17:44:17Z","timestamp":1105724657000},"page":"107-145","source":"Crossref","is-referenced-by-count":28,"title":["Lower bound methods and separation results for on-line learning models"],"prefix":"10.1007","volume":"9","author":[{"given":"Wolfgang","family":"Maass","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gy\ufffdrgy","family":"Tur\ufffdn","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"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?87.","journal-title":"Information and Control"},{"key":"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. (1987a). Learning regular sets from queries and counterexamples.Information and Computation, 75 87?106.","journal-title":"Information and Computation"},{"key":"CR3","series-title":"Technical Report","volume-title":"Learning k-term DNF formulas using queries and counterexamples","author":"D. Angluin","year":"1987","unstructured":"Angluin, D. (1987b).Learning k-term DNF formulas using queries and counterexamples. (Technical Report YALEU\/DCS\/RR-557). New Haven, CT: Yale University, Department of Computer Science."},{"key":"CR4","first-page":"319","volume":"2","author":"D. Angluin","year":"1988","unstructured":"Angluin, D. (1988). Queries and concept learning.Machine Learning, 2 319?342.","journal-title":"Machine Learning"},{"key":"CR5","first-page":"121","volume":"5","author":"D. Angluin","year":"1990","unstructured":"Angluin, D. (1990). Negative results for equivalence queries.Machine Learning, 5 121?150.","journal-title":"Machine Learning"},{"key":"CR6","first-page":"186","volume-title":"Proceedings of the Thirty-First Annual Symposium on Foundatins of Computer Science","author":"D. Angluin","year":"1990","unstructured":"Angluin, D., Frazier, M. & Pitt, L. (1990). Learning conjunctions of Horn clauses.Proceedings of the Thirty-First Annual Symposium on Foundatins of Computer Science (pp. 186?192). Washington, DC: IEEE Computer Society."},{"key":"CR7","unstructured":"Angluin, D., Hellerstein, L. & 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.)"},{"key":"CR8","first-page":"1224","volume":"13","author":"T.M. Barzdin","year":"1972","unstructured":"Barzdin, T.M. & Freiwalds, R.V. (1972). On the prediction of general recursive functions,Sov. Math. Dokl., 13 1224?1228.","journal-title":"Sov. Math. Dokl."},{"key":"CR9","first-page":"258","volume-title":"Proceedings of the Third Annual Workshop on Computational Learning Theory","author":"E.B. Baum","year":"1990","unstructured":"Baum, E.B. (1990). Polynomial time algorithms for learning neural nets.Proceedings of the Third Annual Workshop on Computational Learning Theory (pp. 258?272). San Mateo, CA: Morgan Kaufmann."},{"key":"CR10","first-page":"61","volume-title":"Proceedings of the Twenty-Eighth Annual Symposium on Foundations of Computer Science","author":"P. Berman","year":"1987","unstructured":"Berman, P. & Roos, R. (1987). Learning one-counter languages in polynomial time.Proceedings of the Twenty-Eighth Annual Symposium on Foundations of Computer Science (pp. 61?67). Washington, DC: IEEE Computer Society."},{"key":"CR11","doi-asserted-by":"crossref","first-page":"929","DOI":"10.1145\/76359.76371","volume":"36","author":"A. Blumer","year":"1989","unstructured":"Blumer, A., Ehrenfeucht, A., Haussler, D., & Warmuth, M.K. (1989). Learnability and the Vapnik-Chervonenkis dimension.Journal of the ACM, 36 929?965.","journal-title":"Journal of the ACM"},{"key":"CR12","first-page":"337","volume-title":"Proceedings of the Fourth Annual Workshop on Computational Learning Theory","author":"W. Bultman","year":"1991","unstructured":"Bultman, W. & Maass, W. (1991). On-line learning of geometrical concepts with membership queries.Proceedings of the Fourth Annual Workshop on Computational Learning Theory (pp. 337?353). San Mateo, CA: Morgan Kaufmann."},{"key":"CR13","volume-title":"Information theory","author":"I. Csisz\u00e1r","year":"1981","unstructured":"Csisz\u00e1r, I. & K\u00f6rner, J. (1981).Information theory. New York: Academic Press."},{"key":"CR14","volume-title":"Probabilistic methods in combinatorics","author":"P. Erd\u00f6s","year":"1974","unstructured":"Erd\u00f6s, P. & Spencer, J. (1974).Probabilistic methods in combinatorics. New York-Budapest: Academic Press-Akad\u00e9miai Kiad\u00f3."},{"key":"CR15","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1137\/0217007","volume":"17","author":"U. Faigle","year":"1988","unstructured":"Faigle, U. & Turan, Gy. (1988). Sorting and recognition problems for ordered sets.SIAM Journal on Computing, 17 100?113.","journal-title":"SIAM Journal on Computing"},{"key":"CR16","unstructured":"Gaizer, T. (1990). The Vapnik-Chervonenkis dimension of finite automata. Unpublished manuscript."},{"key":"CR17","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1109\/SFCS.1989.63454","volume-title":"Proceedings of the Thirtieth Annual Symposium on Foundations of Computer Science","author":"S.A. Goldman","year":"1989","unstructured":"Goldman, S.A., Rivest, R.L. & Schapire, R.E. (1989). Learning binary relations and total orders.Proceedings of the Thirtieth Annual Symposium on Foundations of Computer Science (pp. 46?51), Washington, DC: IEEE Computer Society."},{"key":"CR18","unstructured":"Hetyei, G. (1964),P\u00e9csi Tan\u00e1rk\u00e9pz\u00f6 F\u00f6iskola K\u00f6zlem\u00e9nyei, 151?168."},{"key":"CR19","first-page":"151","volume":"5","author":"H. Ishizaka","year":"1990","unstructured":"Ishizaka, H. (1990). Polynomial time learnability of simple deterministic languages.Machine Learning, 5 151?164.","journal-title":"Machine Learning"},{"key":"CR20","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1007\/BF00565647","volume":"1","author":"J. Kahn","year":"1984","unstructured":"Kahn, J. & Saks, M. (1984). Balancing poset extensions.Order, 1 113?126.","journal-title":"Order"},{"key":"CR21","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1007\/BF02579460","volume":"1","author":"D.J. Kleitman","year":"1981","unstructured":"Kleitman, D.J., Shearer, J.B., & Sturtevant, D. (1981). Intersections ofk-element sets.Combinatorica, 1 381?384.","journal-title":"Combinatorica"},{"key":"CR22","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?318.","journal-title":"Machine Learning"},{"key":"CR23","volume-title":"Combinatorial problems and exercises","author":"L. Lov\u00e1sz","year":"1979","unstructured":"Lov\u00e1sz, L. (1979).Combinatorial problems and exercises. Budapest: Akad\u00e9miai Kiad\u00f3."},{"key":"CR24","first-page":"167","volume-title":"Proceedings of the Fourth Annual Workshop on Computational Learning Theory","author":"W. Maass","year":"1991","unstructured":"Maass, W. (1991). On-line learning with an oblivious environment and the power of randomization.Proceedings of the Fourth Annual Workshop on Computational Learning Theory (pp. 167?175). San Mateo, CA: Morgan Kaufmann."},{"key":"CR25","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1109\/SFCS.1989.63488","volume-title":"Proceedings of the Thirtieth Annual Symposium on Foundations of Computer Science","author":"W. Maass","year":"1989","unstructured":"Maass, W. & Tur\u00e1n, Gy. (1989). On the complexity of learning from counterexamples.Proceedings of the Thirtieth Annual Symposium on Foundations of Computer Science (pp. 262?267). Washington, DC: IEEE Computer Society Press."},{"key":"CR26","first-page":"203","volume-title":"Proceedings of the Thirty-First Annual Symposium on Foundations of Computer Science","author":"W. Maass","year":"1990","unstructured":"Maass, W. & Tur\u00e1n, Gy. (1990a). On the complexity of learning from counterexamples and membership queries.Proceedings of the Thirty-First Annual Symposium on Foundations of Computer Science (pp. 203?210). Washington, DC: IEEE Computer Society Press."},{"key":"CR27","unstructured":"Maass, W. & Tur\u00e1n, Gy. (1990b). Algorithms and lower bounds for on-line learning of geometrical concepts. To appear inMachine Learning."},{"key":"CR28","volume-title":"Computational learning theory and natural learning systems: Constraints and prospects","author":"W. Maass","year":"1990","unstructured":"Maass, W. & Tur\u00e1n, Gy. (1990c). How fast can a threshold gate learn? In S. Hanson, G. Drastal, R. Rivest, (Eds.),Computational learning theory and natural learning systems: Constraints and prospects, Cambridge, MA: MIT Press, to appear."},{"key":"CR29","volume-title":"Perceptrons: an introduction to computational geometry, Expanded edition","author":"M. Minsky","year":"1988","unstructured":"Minsky, M. & Papert, S. (1988).Perceptrons: an introduction to computational geometry, Expanded edition. Cambridge, MA: MIT Press."},{"key":"CR30","volume-title":"Learning machines","author":"N.J. Nilsson","year":"1965","unstructured":"Nilsson, N.J. (1965).Learning machines. New York: McGraw-Hill."},{"key":"CR31","doi-asserted-by":"crossref","first-page":"965","DOI":"10.1145\/48014.63140","volume":"35","author":"L. Pitt","year":"1988","unstructured":"Pitt, L. & Valiant, L.G. (1988). Computational limitations on learning from examples.Journal of the ACM, 35 965?984.","journal-title":"Journal of the ACM"},{"key":"CR32","volume-title":"Principles of neurodynamics","author":"F. Rosenblatt","year":"1962","unstructured":"Rosenblatt, F. (1962).Principles of neurodynamics. New York: Spartan Books."},{"key":"CR33","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/5236.001.0001","volume-title":"Parallel distributed processing: Explorations in the microstructure of cognition","author":"D.E. Rumelhart","year":"1986","unstructured":"Rumelhart, D.E. & McClelland, J.L. (1986).Parallel distributed processing: Explorations in the microstructure of cognition. Cambridge, MA: MIT Press."},{"issue":"A","key":"CR34","first-page":"154","volume":"13","author":"N. Sauer","year":"1972","unstructured":"Sauer, N. (1972). On the density of families of sets.Journal of Combinatorial Theory (A),13 154?147.","journal-title":"Journal of Combinatorial Theory"},{"key":"CR35","doi-asserted-by":"crossref","first-page":"247","DOI":"10.2140\/pjm.1972.41.247","volume":"41","author":"S. Shelah","year":"1972","unstructured":"Shelah, S. (1972). A combinatorial problem; stability and order for models and theories in infinitary languages.Pacific Journal of Mathematics, 41 247?261.","journal-title":"Pacific Journal of Mathematics"},{"key":"CR36","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.Communications of the ACM, 27 1134?1142.","journal-title":"Communications of the ACM"},{"key":"CR37","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1137\/1116025","volume":"16","author":"V.N. Vapnik","year":"1971","unstructured":"Vapnik, V.N. & Chervonenkis, A. Ya. (1971). On the uniform convergence of relative frequencies of events to their probabilities.Theory of Probability and Its Applications, 16 264?280.","journal-title":"Theory of Probability and Its Applications"},{"key":"CR38","first-page":"106","volume-title":"Proceedings of the 1988 Workshop on Computational Learning Theory","author":"J.S. Vitter","year":"1988","unstructured":"Vitter, J.S. & Lin, J.H. (1988). Learning in parallel.Proceedings of the 1988 Workshop on Computational Learning Theory (pp. 106?124). San Mateo, CA: Morgan Kaufmann."}],"container-title":["Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF00992674.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF00992674\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF00992674","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,5]],"date-time":"2020-04-05T09:49:52Z","timestamp":1586080192000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF00992674"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,7]]},"references-count":38,"journal-issue":{"issue":"2-3","published-print":{"date-parts":[[1992,7]]}},"alternative-id":["BF00992674"],"URL":"https:\/\/doi.org\/10.1007\/bf00992674","relation":{},"ISSN":["0885-6125","1573-0565"],"issn-type":[{"value":"0885-6125","type":"print"},{"value":"1573-0565","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992,7]]}}}