{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:36:20Z","timestamp":1759638980768},"reference-count":33,"publisher":"Elsevier BV","issue":"3","license":[{"start":{"date-parts":[[2003,11,1]],"date-time":"2003-11-01T00:00:00Z","timestamp":1067644800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":3546,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Computer and System Sciences"],"published-print":{"date-parts":[[2003,11]]},"DOI":"10.1016\/s0022-0000(03)00067-9","type":"journal-article","created":{"date-parts":[[2003,6,21]],"date-time":"2003-06-21T00:11:16Z","timestamp":1056154276000},"page":"546-607","source":"Crossref","is-referenced-by-count":2,"title":["Intrinsic complexity of learning geometrical concepts from positive data"],"prefix":"10.1016","volume":"67","author":[{"given":"Sanjay","family":"Jain","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Efim","family":"Kinber","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0022-0000(03)00067-9_BIBBF72","first-page":"1224","article-title":"On the prediction of general recursive functions","volume":"13","author":"B\u0101rzdi\u0146\u0161","year":"1972","journal-title":"Soviet Math. Dokl."},{"key":"10.1016\/S0022-0000(03)00067-9_BIBBLU67","doi-asserted-by":"crossref","first-page":"322","DOI":"10.1145\/321386.321395","article-title":"A machine-independent theory of the complexity of recursive functions","volume":"14","author":"Blum","year":"1967","journal-title":"J. ACM"},{"issue":"4","key":"10.1016\/S0022-0000(03)00067-9_BIBBEHW89","doi-asserted-by":"crossref","first-page":"929","DOI":"10.1145\/76359.76371","article-title":"Learnability and the Vapnik\u2013Chervonenkis dimension","volume":"36","author":"Blumer","year":"1989","journal-title":"J. ACM"},{"key":"10.1016\/S0022-0000(03)00067-9_BIBBGGM98","doi-asserted-by":"crossref","first-page":"674","DOI":"10.1137\/S0097539794274246","article-title":"Exact learning of discretized geometric concepts","volume":"28","author":"Bshouty","year":"1998","journal-title":"SIAM J. Comput."},{"issue":"1","key":"10.1016\/S0022-0000(03)00067-9_BIBBGM98","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1006\/inco.1998.2737","article-title":"Noise-tolerant parallel learning of geometric concepts","volume":"147","author":"Bshouty","year":"1998","journal-title":"Inform. Comput."},{"issue":"6","key":"10.1016\/S0022-0000(03)00067-9_BIBCAS99","doi-asserted-by":"crossref","first-page":"1941","DOI":"10.1137\/S0097539793249694","article-title":"The power of vacillation in language learning","volume":"28","author":"Case","year":"1999","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0022-0000(03)00067-9_BIBCL82","series-title":"Proceedings of the Ninth International Colloquium on Automata, Languages and Programming","first-page":"107","article-title":"Machine inductive inference and language identification","volume":"Vol. 140","author":"Case","year":"1982"},{"key":"10.1016\/S0022-0000(03)00067-9_BIBCS83","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1016\/0304-3975(83)90061-0","article-title":"Comparison of identification criteria for machine inductive inference","volume":"25","author":"Case","year":"1983","journal-title":"Theoret. Comput. Sci."},{"issue":"1","key":"10.1016\/S0022-0000(03)00067-9_BIBCA99","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1006\/jcss.1999.1621","article-title":"The learnability of unions of two rectangles in the two-dimensional discretized space","volume":"59","author":"Chen","year":"1999","journal-title":"J. Comput. System Sci."},{"issue":"2\/3","key":"10.1016\/S0022-0000(03)00067-9_BIBCM94","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1023\/A:1022671717849","article-title":"On-line learning of rectangles and unions of rectangles","volume":"17","author":"Chen","year":"1994","journal-title":"Mach. Learning"},{"key":"10.1016\/S0022-0000(03)00067-9_BIBDS86","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/S0019-9958(86)80042-0","article-title":"On the complexity of inductive inference","volume":"69","author":"Daley","year":"1986","journal-title":"Inform. Control"},{"key":"10.1016\/S0022-0000(03)00067-9_BIBDG95","doi-asserted-by":"crossref","unstructured":"D. Dobkin, D. Gunopulos, Concept learning with geometric hypothesis, in: Proceedings of the Eighth Annual Conference on Computational Learning Theory, Santa Cruz, CA, ACM, New York, 1995, pp. 329\u2013336.","DOI":"10.1145\/225298.225338"},{"key":"10.1016\/S0022-0000(03)00067-9_BIBFEL72","doi-asserted-by":"crossref","first-page":"244","DOI":"10.1016\/S0019-9958(72)90424-X","article-title":"Some decidability results on grammatical inference and complexity","volume":"20","author":"Feldman","year":"1972","journal-title":"Inform. Control"},{"key":"10.1016\/S0022-0000(03)00067-9_BIBFIS95","doi-asserted-by":"crossref","unstructured":"P. Fischer, More or less efficient agnostic learning of convex polygons, in: Proceedings of the Eighth Annual Conference on Computational Learning Theory, Santa Cruz, CA, ACM, New York, 1995, pp. 337\u2013344.","DOI":"10.1145\/225298.225339"},{"issue":"1","key":"10.1016\/S0022-0000(03)00067-9_BIBFKS95","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1006\/inco.1995.1158","article-title":"On the intrinsic complexity of learning","volume":"123","author":"Freivalds","year":"1995","journal-title":"Inform. Comput."},{"key":"10.1016\/S0022-0000(03)00067-9_BIBGOL67","doi-asserted-by":"crossref","first-page":"447","DOI":"10.1016\/S0019-9958(67)91165-5","article-title":"Language identification in the limit","volume":"10","author":"Gold","year":"1967","journal-title":"Inform. Control"},{"key":"10.1016\/S0022-0000(03)00067-9_BIBGG94","doi-asserted-by":"crossref","unstructured":"P. Goldberg, S. Goldman, Learning one-dimensional geometric patterns under one-sided random misclassification noise, in: Proceedings of the Seventh Annual Conference on Computational Learning Theory, ACM, New York, 1994, pp. 246\u2013255.","DOI":"10.1145\/180139.181131"},{"key":"10.1016\/S0022-0000(03)00067-9_BIBGGDM94","doi-asserted-by":"crossref","unstructured":"P. Goldberg, S. Goldman, H. David Mathias, Learning unions of boxes with membership and equivalence queries, in: Proceedings of the Seventh Annual Conference on Computational Learning Theory, ACM, New York, 1994, pp. 198\u2013207.","DOI":"10.1145\/180139.181102"},{"key":"10.1016\/S0022-0000(03)00067-9_BIBGGS96","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1007\/BF00115300","article-title":"Pac learning of one-dimensional patterns","volume":"25","author":"Goldberg","year":"1996","journal-title":"Mach. Learning"},{"key":"10.1016\/S0022-0000(03)00067-9_BIBGKS01","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1006\/jcss.2000.1723","article-title":"Agnostic learning of geometric patterns","volume":"62","author":"Goldman","year":"2001","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0022-0000(03)00067-9_BIBGS99","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1023\/A:1007681724516","article-title":"A theoretical and empirical study of a noise-tolerant algorithm to learn geometric patterns","volume":"37","author":"Goldman","year":"1999","journal-title":"Mach. Learning"},{"key":"10.1016\/S0022-0000(03)00067-9_BIBHEG94","doi-asserted-by":"crossref","unstructured":"T. Hegedus, Geometrical concept learning and convex polytopes, in: Proceedings of the Seventh Annual Conference on Computational Learning Theory, ACM, New York, 1994, pp. 228\u2013236.","DOI":"10.1145\/180139.181124"},{"key":"10.1016\/S0022-0000(03)00067-9_BIBHU79","series-title":"Introduction to Automata Theory, Languages, and Computation","author":"Hopcroft","year":"1979"},{"key":"10.1016\/S0022-0000(03)00067-9_BIBJKW99","unstructured":"S. Jain, E. Kinber, R. Wiehagen, Language learning: degrees of intrinsic complexity and their characterizations, Technical Report LSA-99-02E, Centre for Learning Systems and Applications, Department of Computer Science, University of Kaiserslautern, Germany, 1999."},{"key":"10.1016\/S0022-0000(03)00067-9_BIBJKW00","series-title":"Proceedings of the Thirteenth Annual Conference on Computational Learning Theory","first-page":"47","article-title":"Language learning from texts: Degrees of intrinsic complexity and their characterizations","author":"Jain","year":"2000"},{"key":"10.1016\/S0022-0000(03)00067-9_BIBJS96","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1006\/jcss.1996.0030","article-title":"The intrinsic complexity of language identification","volume":"52","author":"Jain","year":"1996","journal-title":"J. Comput System Sci."},{"key":"10.1016\/S0022-0000(03)00067-9_BIBJS97","doi-asserted-by":"crossref","first-page":"1187","DOI":"10.2307\/2275636","article-title":"The structure of intrinsic complexity of learning","volume":"62","author":"Jain","year":"1997","journal-title":"J. Symbolic Logic"},{"key":"10.1016\/S0022-0000(03)00067-9_BIBKS95","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1006\/inco.1995.1170","article-title":"Language learning from texts","volume":"123","author":"Kinber","year":"1995","journal-title":"Inform. Comput."},{"issue":"2","key":"10.1016\/S0022-0000(03)00067-9_BIBLZ93","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1142\/S0129054193000110","article-title":"Learning recursive languages with a bounded number of mind changes","volume":"4","author":"Lange","year":"1993","journal-title":"Inter. J. Found. Comput. Sci."},{"key":"10.1016\/S0022-0000(03)00067-9_BIBMY78","series-title":"An Introduction to the General Theory of Algorithms","author":"Machtey","year":"1978"},{"key":"10.1016\/S0022-0000(03)00067-9_BIBOW82","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/S0019-9958(82)80025-9","article-title":"Criteria of language learning","volume":"52","author":"Osherson","year":"1982","journal-title":"Inform. Control"},{"key":"10.1016\/S0022-0000(03)00067-9_BIBROG67","unstructured":"H. Rogers, Theory of Recursive Functions and Effective Computability, McGraw-Hill, New York, 1967, Reprinted, MIT, Cambridge, MA, 1987."},{"key":"10.1016\/S0022-0000(03)00067-9_BIBWIE86","first-page":"305","article-title":"On the complexity of program synthesis from examples","volume":"22","author":"Wiehagen","year":"1986","journal-title":"J. Inform. Process. Cybernetics (EIK)"}],"container-title":["Journal of Computer and System Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0022000003000679?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0022000003000679?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,3,20]],"date-time":"2019-03-20T06:20:30Z","timestamp":1553062830000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0022000003000679"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,11]]},"references-count":33,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2003,11]]}},"alternative-id":["S0022000003000679"],"URL":"https:\/\/doi.org\/10.1016\/s0022-0000(03)00067-9","relation":{},"ISSN":["0022-0000"],"issn-type":[{"value":"0022-0000","type":"print"}],"subject":[],"published":{"date-parts":[[2003,11]]}}}