{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,12,22]],"date-time":"2023-12-22T03:35:50Z","timestamp":1703216150294},"reference-count":69,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":3663,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[2004,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Freivalds defined an acceptable programming system independent criterion for learning programs for functions in which the final programs were required to be both correct and \u201cnearly\u201d minimal size. i.e.. within a computable function of being purely minimal size. Kinber showed that this parsimony requirement on final programs limits learning power. However, in scientific inference, parsimony is considered highly desirable. A<jats:italic>lim-computable function<\/jats:italic>is (by definition) one calculable by a total procedure allowed to change its mind finitely many times about its output. Investigated is the possibility of assuaging somewhat the limitation on learning power resulting from requiring parsimonious final programs by use of criteria which require the final, correct programs to be \u201cnot-so-nearly\u201d minimal size, e.g., to be within a lim-computable function of actual minimal size. It is shown that some parsimony in the final program is thereby retained, yet learning power strictly increases. Considered, then, are lim-computable functions as above but for which<jats:italic>notations for<\/jats:italic>constructive ordinals are used to bound the number of mind changes allowed regarding the output. This is a variant of an idea introduced by Freivalds and Smith. For this ordinal notation complexity bounded version of lim-computability, the power of the resultant learning criteria form finely graded, infinitely ramifying, infinite hierarchies intermediate between the computable and the lim-computable cases. Some of these hierarchies, for the natural notations determining them, are shown to be optimally tight.<\/jats:p>","DOI":"10.2178\/jsl\/1080938842","type":"journal-article","created":{"date-parts":[[2005,3,2]],"date-time":"2005-03-02T21:31:12Z","timestamp":1109799072000},"page":"287-327","source":"Crossref","is-referenced-by-count":11,"title":["Parsimony hierarchies for inductive inference"],"prefix":"10.1017","volume":"69","author":[{"given":"Andris","family":"Ambainis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"John","family":"Case","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sanjay","family":"Jain","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mandayam","family":"Suraj","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200008173_ref055","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-18253-5"},{"key":"S0022481200008173_ref062","doi-asserted-by":"publisher","DOI":"10.1145\/267460.267485"},{"key":"S0022481200008173_ref057","first-page":"46","article-title":"Patterns (The Formal Language Theory Column)","volume":"54","author":"Salomaa","year":"1994","journal-title":"The Bulletin for the European Association for Theoretical Computer Science"},{"key":"S0022481200008173_ref052","first-page":"49","volume":"30","author":"Putnam","year":"1965","journal-title":"Trial and error predicates and the solution to a problem of Mostowski"},{"key":"S0022481200008173_ref064","doi-asserted-by":"crossref","first-page":"83","DOI":"10.5109\/13347","article-title":"Inferring unions of two pattern languages","volume":"20","author":"Shinohara","year":"1983","journal-title":"Bulletin of Informatics and Cybernetics"},{"key":"S0022481200008173_ref058","first-page":"144","article-title":"Return to patterns (The Formal Language Theory Column)","volume":"55","author":"Salomaa","year":"1994","journal-title":"The Bulletin for the European Association for Theoretical Computer Science"},{"key":"S0022481200008173_ref067","doi-asserted-by":"crossref","DOI":"10.1515\/9781400882007","volume-title":"Theory of formal systems","author":"Smullyan","year":"1961"},{"key":"S0022481200008173_ref056","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-12013-2"},{"key":"S0022481200008173_ref068","doi-asserted-by":"publisher","DOI":"10.2307\/420992"},{"key":"S0022481200008173_ref046","volume-title":"An introduction to the general theory of algorithms","author":"Machtey","year":"1978"},{"key":"S0022481200008173_ref040","first-page":"221","volume-title":"Theory of algorithms and programs","volume":"1","author":"Kinber","year":"1974"},{"key":"S0022481200008173_ref044","volume-title":"Set theory","author":"Kuratowski","year":"1967"},{"key":"S0022481200008173_ref048","first-page":"669","article-title":"Inductive logic programming: Theory and methods","volume":"19","author":"Muggleton","year":"1994","journal-title":"Journal of Logic Programming"},{"key":"S0022481200008173_ref050","volume-title":"Classical recursion theory","volume":"II","author":"Odifreddi","year":"1999"},{"key":"S0022481200008173_ref033","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(67)91165-5"},{"key":"S0022481200008173_ref015","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00274-7"},{"key":"S0022481200008173_ref003","doi-asserted-by":"crossref","first-page":"1","DOI":"10.3233\/FI-1999-40101","article-title":"Inductive inference with procrastination: Back to definitions","volume":"40","author":"Ambainis","year":"1999","journal-title":"Fundamenta Informaticae"},{"key":"S0022481200008173_ref010","doi-asserted-by":"publisher","DOI":"10.1145\/321386.321395"},{"key":"S0022481200008173_ref026","first-page":"219","volume-title":"Proceedings of the 4th Symposium on Mathematical Foundations of Computer Science","volume":"32","author":"Freivalds","year":"1975"},{"key":"S0022481200008173_ref014","doi-asserted-by":"publisher","DOI":"10.1080\/09528139408953778"},{"key":"S0022481200008173_ref013","doi-asserted-by":"publisher","DOI":"10.1007\/BF01761704"},{"key":"S0022481200008173_ref009","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(75)90261-2"},{"key":"S0022481200008173_ref012","first-page":"95","volume-title":"Proceedings of the Seventh International Symposium on Algorithms and Computation (ISAAC'96)","volume":"1178","author":"Brazma","year":"1996"},{"key":"S0022481200008173_ref049","volume-title":"Technical Report 280","author":"Nix","year":"1983"},{"key":"S0022481200008173_ref035","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1996.2614"},{"key":"S0022481200008173_ref025","doi-asserted-by":"publisher","DOI":"10.1007\/BF02219847"},{"key":"S0022481200008173_ref002","first-page":"99","volume-title":"EuroCOLT'95","volume":"904","author":"Ambainis","year":"1995"},{"key":"S0022481200008173_ref036","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-49097-3_16"},{"key":"S0022481200008173_ref018","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1007\/3-540-60217-8_5","volume-title":"Algorithmic learning for knowledge-based systems","volume":"961","author":"Case","year":"1995"},{"key":"S0022481200008173_ref006","first-page":"26","volume-title":"Algorithmic learning theory, Proceedings of the 4th International Workshop on Analogical and Inductive Inference (AII'94) and the 5th International Workshop on Algorithmic Learning Theory (ALT'94), October 10\u201315, 1994","volume":"872","author":"Aps\u012btis","year":"1994"},{"key":"S0022481200008173_ref032","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1007\/BF01534453","article-title":"Recursion theoretic models of learning: some results and intuitions","volume":"15","author":"Gasarch","year":"1995","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"key":"S0022481200008173_ref023","first-page":"47","article-title":"A hierarchy of sets, I","volume":"7","author":"Ershov","year":"1968","journal-title":"Algebra i Logika"},{"key":"S0022481200008173_ref034","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/6610.001.0001","volume-title":"Systems that learn: An introduction to learning theory","author":"Jain","year":"1999"},{"key":"S0022481200008173_ref020","unstructured":"Case J. and Suraj M. , Characterizing Ershov hierarchies by algorithmic O-count down, Working paper, 2003."},{"key":"S0022481200008173_ref019","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(83)90061-0"},{"key":"S0022481200008173_ref007","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90068-Q"},{"key":"S0022481200008173_ref028","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1993.1068"},{"key":"S0022481200008173_ref001","first-page":"1","volume-title":"Theory of models. (Proceedings of the 1963 International Symposium)","author":"Addison","year":"1965"},{"key":"S0022481200008173_ref031","doi-asserted-by":"publisher","DOI":"10.1002\/1521-3870(200105)47:2<161::AID-MALQ161>3.0.CO;2-E"},{"key":"S0022481200008173_ref011","doi-asserted-by":"publisher","DOI":"10.1145\/219717.219771"},{"key":"S0022481200008173_ref021","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(82)80086-7"},{"key":"S0022481200008173_ref016","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1998.2784"},{"key":"S0022481200008173_ref038","volume-title":"Mathematical Reviews","author":"Jockusch","year":"1982"},{"key":"S0022481200008173_ref066","volume-title":"Cardinal and ordinal numbers","author":"Sierpinski","year":"1965"},{"key":"S0022481200008173_ref059","doi-asserted-by":"publisher","DOI":"10.1007\/s001530050112"},{"key":"S0022481200008173_ref008","unstructured":"Behounek L. , Ordinal calculator, 1997, Web document at: http:\/\/www.ff.cuni.cz\/~behounek\/ordinalc.htm."},{"key":"S0022481200008173_ref030","unstructured":"Fulk M. , A study of inductive inference machines, Ph.D. thesis , SUNY at Buffalo, 1985."},{"key":"S0022481200008173_ref022","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0090937"},{"key":"S0022481200008173_ref045","volume-title":"Inductive logic programming: Techniques and applications","author":"Lavra\u010d","year":"1994"},{"key":"S0022481200008173_ref065","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-60217-8_13"},{"key":"S0022481200008173_ref029","first-page":"179","article-title":"Inductive inference with additional information","volume":"15","author":"Freivalds","year":"1979","journal-title":"Electronische Informationverarbeitung und Kybernetik"},{"key":"S0022481200008173_ref017","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1996.0064"},{"key":"S0022481200008173_ref051","volume-title":"Probability and confirmation","author":"Putnam","year":"1963"},{"key":"S0022481200008173_ref063","first-page":"2009","article-title":"Knowledge acquisition from amino acid sequences by machine learning system BONSAI","volume":"35","author":"Shimozono","year":"1994","journal-title":"Transactions of the Information Processing Society of Japan"},{"key":"S0022481200008173_ref024","first-page":"15","article-title":"A hierarchy of sets, II","volume":"7","author":"Ershov","year":"1968","journal-title":"Algebra i Logika"},{"key":"S0022481200008173_ref039","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-59119-2_182"},{"key":"S0022481200008173_ref043","doi-asserted-by":"publisher","DOI":"10.2307\/2372632"},{"key":"S0022481200008173_ref054","volume-title":"Theory of recursive functions and effective computability","author":"Rogers","year":"1967"},{"key":"S0022481200008173_ref053","first-page":"331","volume":"23","author":"Rogers","year":"1958","journal-title":"G\u00f6del numberings of partial recursive functions"},{"key":"S0022481200008173_ref027","first-page":"3","volume-title":"Proceedings of the Third Annual Workshop on Computational Learning Theory","author":"Freivalds","year":"1990"},{"key":"S0022481200008173_ref037","doi-asserted-by":"publisher","DOI":"10.1006\/inco.2000.3001"},{"key":"S0022481200008173_ref005","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90041-0"},{"key":"S0022481200008173_ref060","first-page":"146","article-title":"On a hierarchy of limiting computations","volume":"25","author":"Selivanov","year":"1984","journal-title":"Sibirskii Mathematicheskii Zhurnal"},{"key":"S0022481200008173_ref041","first-page":"150","volume":"3","author":"Kleene","year":"1938","journal-title":"On notation for ordinal numbers"},{"key":"S0022481200008173_ref069","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-08-094829-4.50026-X"},{"key":"S0022481200008173_ref042","doi-asserted-by":"publisher","DOI":"10.2307\/2371894"},{"key":"S0022481200008173_ref061","first-page":"342","volume":"36","author":"Shapiro","year":"1971","journal-title":"Review of \u201cLimiting recursion\u201d by E. M. Gold and \u201cTrial and error predicates and the solution to a problem of Mostowski\u201d by H. Putnam"},{"key":"S0022481200008173_ref004","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00005-5"},{"key":"S0022481200008173_ref047","volume-title":"Machine learning","author":"Mitchell","year":"1997"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200008173","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,6]],"date-time":"2021-07-06T06:16:47Z","timestamp":1625552207000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200008173\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,3]]},"references-count":69,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2004,3]]}},"alternative-id":["S0022481200008173"],"URL":"https:\/\/doi.org\/10.2178\/jsl\/1080938842","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,3]]}}}