{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T08:19:29Z","timestamp":1760170769660},"publisher-location":"Berlin, Heidelberg","reference-count":8,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540573708"},{"type":"electronic","value":"9783540480969"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1993]]},"DOI":"10.1007\/3-540-57370-4_54","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T12:55:54Z","timestamp":1330260954000},"page":"279-287","source":"Crossref","is-referenced-by-count":4,"title":["Complexity of computing Vapnik-Chervonenkis dimension"],"prefix":"10.1007","author":[{"given":"Ayumi","family":"Shinohara","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,2]]},"reference":[{"key":"22_CR1","doi-asserted-by":"crossref","unstructured":"S. Ben-David, N. Cesa-Bianchi, and P.M. Long. Characterizations of learnability for classes of {0,..., n}-valued functions. In Proc. 5th Annual Workshop on Computational Learning Theory, pages 333\u2013340, 1992.","DOI":"10.1145\/130385.130423"},{"issue":"4","key":"22_CR2","doi-asserted-by":"crossref","first-page":"929","DOI":"10.1145\/76359.76371","volume":"36","author":"A. Blumer","year":"1989","unstructured":"A. Blumer, A. Ehrenfeucht, D. Haussler, and M.K. Warmuth. Learnability and the Vapnik-Chervonenkis dimension. JACM, 36(4):929\u2013965, 1989.","journal-title":"JACM"},{"key":"22_CR3","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1016\/0890-5401(91)90058-A","volume":"90","author":"N. Linial","year":"1991","unstructured":"N. Linial, Y. Mansour, and R.L. Rivest. Results on learnability and the Vapnik-Chervonenkis dimension. Information and Computation, 90:33\u201349, 1991.","journal-title":"Information and Computation"},{"key":"22_CR4","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1016\/0304-3975(88)90131-4","volume":"61","author":"N. Megiddo","year":"1988","unstructured":"N. Megiddo and U. Vishkin. On finding a minimum dominating set in a tournament. Theoretical Computer Science, 61:307\u2013316, 1988.","journal-title":"Theoretical Computer Science"},{"key":"22_CR5","unstructured":"B.K. Natarajan. Machine Learning \u2014 A Theoretical Approach. Morgan Kaufmann Publishers, 1991."},{"key":"22_CR6","first-page":"348","volume":"667","author":"S.H. Nienhuys-Cheng","year":"1993","unstructured":"S.H. Nienhuys-Cheng and M. Polman. Complexity dimensions and learnability. In Proc. European Conference on Machine Learning, (Lecture Notes in Artificial Intelligence 667), pages 348\u2013353, 1993.","journal-title":"Lecture Notes in Artificial Intelligence"},{"key":"22_CR7","doi-asserted-by":"crossref","unstructured":"K. Romanik. Approximate testing and learnability. In Proc. 5th Annual Workshop on Computational Learning Theory, pages 327\u2013332, 1992.","DOI":"10.1145\/130385.130422"},{"issue":"11","key":"22_CR8","doi-asserted-by":"crossref","first-page":"1134","DOI":"10.1145\/1968.1972","volume":"27","author":"L.G. Valiant","year":"1984","unstructured":"L.G. Valiant. A theory of the learnable. CACM, 27(11):1134\u20131142, 1984.","journal-title":"CACM"}],"container-title":["Lecture Notes in Computer Science","Algorithmic Learning Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-57370-4_54.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T01:04:41Z","timestamp":1619571881000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57370-4_54"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540573708","9783540480969"],"references-count":8,"URL":"https:\/\/doi.org\/10.1007\/3-540-57370-4_54","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1993]]}}}