{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T00:50:13Z","timestamp":1743036613620,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":38,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540428756"},{"type":"electronic","value":"9783540455837"}],"license":[{"start":{"date-parts":[[2001,1,1]],"date-time":"2001-01-01T00:00:00Z","timestamp":978307200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-45583-3_22","type":"book-chapter","created":{"date-parts":[[2007,10,19]],"date-time":"2007-10-19T08:37:04Z","timestamp":1192783024000},"page":"283-298","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Learning Recursive Functions Refutably"],"prefix":"10.1007","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"}]},{"given":"Rolf","family":"Wiehagen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Zeugmann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,10,31]]},"reference":[{"key":"22_CR1","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1145\/356914.356918","volume":"15","author":"D. Angluin","year":"1983","unstructured":"D. Angluin and C. Smith. Inductive inference: Theory and methods. Computing Surveys, 15:237\u2013289, 1983.","journal-title":"Computing Surveys"},{"key":"22_CR2","first-page":"82","volume":"1","author":"J. B\u0101rzdi\u0146\u0161","year":"1974","unstructured":"J. B\u0101rzdi\u0146\u0161. Two theorems on the limiting synthesis of functions. In Theory of Algorithms and Programs, Vol. 1, pp. 82\u201388. Latvian State University, 1974. In Russian.","journal-title":"Theory of Algorithms and Programs"},{"key":"22_CR3","first-page":"101","volume":"210","author":"J. B\u0101rzdi\u0146\u0161","year":"1974","unstructured":"J. B\u0101rzdi\u0146\u0161 and R. Freivalds. Prediction and limiting synthesis of recursively enumerable classes of functions. Latvijas Valsts Univ. Zimatm. Raksti, 210:101\u2013111, 1974.","journal-title":"Latvijas Valsts Univ. Zimatm. Raksti"},{"key":"22_CR4","doi-asserted-by":"crossref","unstructured":"S. Ben-David. Can finite samples detect singularities of real-valued functions? In 24th Annual ACM Symposium on the Theory of Computing, pp. 390\u2013399, 1992.","DOI":"10.1145\/129712.129749"},{"key":"22_CR5","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/S0019-9958(75)90261-2","volume":"28","author":"L. Blum","year":"1975","unstructured":"L. Blum and M. Blum. Toward a mathematical theory of inductive inference. Inform. and Control, 28:125\u2013155, 1975.","journal-title":"Inform. and Control"},{"key":"22_CR6","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1145\/321386.321395","volume":"14","author":"M. Blum","year":"1967","unstructured":"M. Blum. A machine-independent theory of the complexity of recursive functions. Journal of the ACM, 14:322\u2013336, 1967.","journal-title":"Journal of the ACM"},{"key":"22_CR7","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1007\/BF01761704","volume":"8","author":"J. Case","year":"1974","unstructured":"J. Case. Periodicity in generations of automata. Mathematical Systems Theory, 8:15\u201332, 1974.","journal-title":"Mathematical Systems Theory"},{"key":"22_CR8","first-page":"23","volume":"30","author":"J. Case","year":"1994","unstructured":"J. Case, S. Jain, and S. Ngo Manguelle. Refinements of inductive inference by Popperian and reliable machines. Kybernetika, 30:23\u201352, 1994.","journal-title":"Kybernetika"},{"key":"22_CR9","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1007\/BFb0023462","volume-title":"On the classification of computable languages","author":"J. Case","year":"1997","unstructured":"J. Case, E. Kinber, A. Sharma, and F. Stephan. On the classification of computable languages. In Proc. 14th Symposium on Theoretical Aspects of Computer Science, Vol. 1200 of Lecture Notes in Computer Science, pp. 225\u2013236. Springer, 1997."},{"key":"22_CR10","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1016\/0304-3975(83)90061-0","volume":"25","author":"J. Case","year":"1983","unstructured":"J. Case and C. Smith. Comparison of identification criteria for machine inductive inference. Theoretical Computer Science, 25:193\u2013220, 1983.","journal-title":"Theoretical Computer Science"},{"key":"22_CR11","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1007\/BFb0019357","volume-title":"Baltic Computer Science","author":"R. Freivalds","year":"1991","unstructured":"R. Freivalds. Inductive inference of recursive functions: Qualitative theory. In Baltic Computer Science, Vol. 502 of Lecture Notes in Computer Science, pp. 77\u2013110. Springer, 1991."},{"issue":"1","key":"22_CR12","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1006\/inco.1995.1158","volume":"123","author":"R. Freivalds","year":"1995","unstructured":"R. Freivalds, E. Kinber, and C. H. Smith. On the intrinsic complexity of learning. Information and Computation, 123(1):64\u201371, 1995.","journal-title":"Information and Computation"},{"key":"22_CR13","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1016\/S0019-9958(67)91165-5","volume":"10","author":"E. M. Gold","year":"1967","unstructured":"E. M. Gold. Language identification in the limit. Inform. and Control, 10:447\u2013474, 1967.","journal-title":"Inform. and Control"},{"key":"22_CR14","unstructured":"J. Grabowski. Starke Erkennung. In Strukturerkennung diskreter kybernetischer Systeme, Teil I, pp. 168\u2013184. Seminarbericht Nr. 82, Department of Mathematics, Humboldt University of Berlin, 1986."},{"key":"22_CR15","doi-asserted-by":"crossref","unstructured":"G. Grieser. Reflecting inductive inference machines and its improvement by therapy. In Algorithmic Learning Theory: 7th International Workshop (ALT\u2019 96), Vol. 1160 of Lecture Notes in Artificial Intelligence, pp. 325\u2013336. Springer, 1996.","DOI":"10.1007\/3-540-61863-5_56"},{"issue":"3","key":"22_CR16","doi-asserted-by":"publisher","first-page":"356","DOI":"10.1006\/jcss.1998.1591","volume":"57","author":"S. Jain","year":"1998","unstructured":"S. Jain. Learning with refutation. Journal of Computer and System Sciences, 57(3):356\u2013365, 1998.","journal-title":"Journal of Computer and System Sciences"},{"key":"22_CR17","unstructured":"S. Jain, E. Kinber, R. Wiehagen and T. Zeugmann. Refutable inductive inference of recursive functions. Schriftenreihe der Institute f\u00fcr Informatik\/Mathematik, Serie A, SIIM-TR-A-01-06, Medical University at L\u00fcbeck, 2001."},{"key":"22_CR18","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/6610.001.0001","volume-title":"Systems that Learn: An Introduction to Learning Theory","author":"S. Jain","year":"1999","unstructured":"S. Jain, D. Osherson, J. S. Royer, and A. Sharma. Systems that Learn: An Introduction to Learning Theory. MIT Press, Cambridge, Mass., second edition, 1999.","edition":"second edition"},{"key":"22_CR19","doi-asserted-by":"crossref","unstructured":"K. P. Jantke. Reflecting and self-confident inductive inference machines. In Algorithmic Learning Theory: 6th International Workshop (ALT\u2019 95), Vol. 997 of Lecture Notes in Artificial Intelligence, pp. 282\u2013297. Springer, 1995.","DOI":"10.1007\/3-540-60454-5_46"},{"key":"22_CR20","unstructured":"W. Jekeli. Universelle Strategien zur L\u00f6sung induktiver Lernprobleme. MSc Thesis, Dept. of Computer Science, University of Kaiserslautern, 1997."},{"key":"22_CR21","first-page":"91","volume":"21","author":"E. B. Kinber","year":"1985","unstructured":"E. B. Kinber and T. Zeugmann. Inductive inference of almost everywhere correct programs by reliably working strategies. Journal of Information Processing and Cybernetics (EIK), 21:91\u2013100, 1985.","journal-title":"Journal of Information Processing and Cybernetics (EIK)"},{"issue":"2","key":"22_CR22","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1016\/0890-5401(91)90011-P","volume":"92","author":"E. Kinber","year":"1991","unstructured":"E. Kinber and T. Zeugmann. One-sided error probabilistic inductive inference and reliable frequency identification. Information and Computation, 92(2):253\u2013284, 1991.","journal-title":"Information and Computation"},{"key":"22_CR23","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/S0020-0255(80)80006-5","volume":"22","author":"R. Klette","year":"1980","unstructured":"R. Klette and R. Wiehagen. Research in the theory of inductive inference by GDR mathematicians-A survey. Information Sciences, 22:149\u2013169, 1980.","journal-title":"Information Sciences"},{"key":"22_CR24","unstructured":"S. Lange and P. Watson. Machine discovery in the presence of incomplete or ambiguous data. In Algorithmic Learning Theory: 4th International Workshop on Analogical and Inductive Inference (AII\u2019 94) and 5th International Workshop on Algorithmic Learning Theory (ALT\u2019 94), Vol. 872 of Lecture Notes in Artificial Intelligence, pp. 438\u2013452. Springer, 1994."},{"key":"22_CR25","unstructured":"R. Lindner. Algorithmische Erkennung. Dissertation B, University of Jena, 1972."},{"key":"22_CR26","unstructured":"M. Machtey and P. Young. An Introduction to the General Theory of Algorithms. North Holland, New York, 1978."},{"key":"22_CR27","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1016\/0304-3975(76)90087-6","volume":"2","author":"E. Minicozzi","year":"1976","unstructured":"E. Minicozzi. Some natural properties of strong identification in inductive inference. Theoretical Computer Science, 2:345\u2013360, 1976.","journal-title":"Theoretical Computer Science"},{"key":"22_CR28","series-title":"Technical Report","volume-title":"Refutable inference of functions computed by loop programs","author":"T. Miyahara","year":"1995","unstructured":"T. Miyahara. Refutable inference of functions computed by loop programs. Technical Report RIFIS-TR-CS-112, Kyushu University, Fukuoka, 1995."},{"key":"22_CR29","doi-asserted-by":"crossref","unstructured":"Y. Mukouchi and S. Arikawa. Inductive inference machines that can refute hypothesis spaces. In Algorithmic Learning Theory: 4th International Workshop (ALT\u2019 93), Vol. 744 of Lecture Notes in Artificial Intelligence, pp. 123\u2013136. Springer, 1993.","DOI":"10.1007\/3-540-57370-4_42"},{"key":"22_CR30","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0304-3975(95)91135-D","volume":"137","author":"Y. Mukouchi","year":"1995","unstructured":"Y. Mukouchi and S. Arikawa. Towards a mathematical theory of machine discovery from facts. Theoretical Computer Science, 137:53\u201384, 1995.","journal-title":"Theoretical Computer Science"},{"key":"22_CR31","unstructured":"K. R. Popper. The Logic of Scientific Discovery. Harper and Row, 1965."},{"key":"22_CR32","doi-asserted-by":"publisher","first-page":"304","DOI":"10.2307\/2269105","volume":"21","author":"H. Rice","year":"1956","unstructured":"H. Rice. On completely recursively enumerable classes and their key arrays. The Journal of Symbolic Logic, 21:304\u2013308, 1956.","journal-title":"The Journal of Symbolic Logic"},{"key":"22_CR33","unstructured":"H. Rogers. Theory of Recursive Functions and Effective Computability. McGraw-Hill, 1967. Reprinted by MIT Press in 1987."},{"issue":"1","key":"22_CR34","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1142\/S0129054197000033","volume":"8","author":"C. H. Smith","year":"1997","unstructured":"C. H. Smith, R. Wiehagen, and T. Zeugmann. Classifying predicates and languages. International Journal of Foundations of Computer Science, 8(1):15\u201341, 1997.","journal-title":"International Journal of Foundations of Computer Science"},{"key":"22_CR35","unstructured":"F. Stephan. On one-sided versus two-sided classification. Technical Report Forschungsberichte Mathematische Logik 25\/1996, Mathematical Institute, University of Heidelberg, 1996."},{"key":"22_CR36","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"494","DOI":"10.1007\/3-540-08860-1_37","volume-title":"Characterization problems in the theory of inductive inference","author":"R. Wiehagen","year":"1978","unstructured":"R. Wiehagen. Characterization problems in the theory of inductive inference. In Proc. of the 5th International Colloquium on Automata, Languages and Programming, Vol. 62 of Lecture Notes in Computer Science, pp. 494\u2013508. Springer, 1978."},{"key":"22_CR37","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1080\/09528139508953804","volume":"7","author":"R. Wiehagen","year":"1995","unstructured":"R. Wiehagen and C. H. Smith. Generalization versus classification. Journal of Experimental and Theoretical Artificial Intelligence, 7:163\u2013174, 1995.","journal-title":"Journal of Experimental and Theoretical Artificial Intelligence"},{"key":"22_CR38","first-page":"559","volume":"19","author":"T. Zeugmann","year":"1983","unstructured":"T. Zeugmann. A-posteriori characterizations in inductive inference of recursive functions. J. of Inform. Processing and Cybernetics (EIK), 19:559\u2013594, 1983.","journal-title":"J. of Inform. Processing and Cybernetics (EIK)"}],"container-title":["Lecture Notes in Computer Science","Algorithmic Learning Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45583-3_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,25]],"date-time":"2021-08-25T23:02:09Z","timestamp":1629932529000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45583-3_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540428756","9783540455837"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/3-540-45583-3_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2001]]},"assertion":[{"value":"31 October 2001","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}