{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T18:16:11Z","timestamp":1725560171515},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540407201"},{"type":"electronic","value":"9783540451679"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-45167-9_50","type":"book-chapter","created":{"date-parts":[[2010,7,22]],"date-time":"2010-07-22T23:10:53Z","timestamp":1279840253000},"page":"684-698","source":"Crossref","is-referenced-by-count":0,"title":["Generality\u2019s Price"],"prefix":"10.1007","author":[{"given":"John","family":"Case","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Keh-Jiann","family":"Chen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sanjay","family":"Jain","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wolfgang","family":"Merkle","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"James S.","family":"Royer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"50_CR1","unstructured":"Barzdin, J.A.: Two theorems on the limiting synthesis of functions. In: Theory of Algorithms and Programs, Latvian State University, Riga, U.S.S.R, vol.\u00a0210, pp. 82\u201388 (1974)"},{"key":"50_CR2","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/S0019-9958(75)90261-2","volume":"28","author":"L. Blum","year":"1975","unstructured":"Blum, L., Blum, M.: Toward a mathematical theory of inductive inference. Information and Control\u00a028, 125\u2013155 (1975)","journal-title":"Information and Control"},{"key":"50_CR3","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1145\/321386.321395","volume":"14","author":"M. Blum","year":"1967","unstructured":"Blum, M.: A machine independent theory of the complexity of recursive functions. Journal of the ACM\u00a014, 322\u2013336 (1967)","journal-title":"Journal of the ACM"},{"key":"50_CR4","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1016\/S0304-3975(00)00028-1","volume":"259","author":"J. Case","year":"2001","unstructured":"Case, J., Chen, K., Jain, S.: Costs of general purpose learning. Theoretical Computer Science\u00a0259, 455\u2013473 (2001)","journal-title":"Theoretical Computer Science"},{"key":"50_CR5","unstructured":"Chen, K.: Tradeoffs in machine inductive inference, Ph.D. thesis, SUNY at Buffalo (1981)"},{"key":"50_CR6","volume-title":"Introduction to algorithms","author":"T. Cormen","year":"2001","unstructured":"Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to algorithms, 2nd edn. MIT Press, Cambridge (2001)","edition":"2"},{"key":"50_CR7","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0022-0000(81)90021-0","volume":"22","author":"P. Chew","year":"1981","unstructured":"Chew, P., Machtey, M.: A note on structure and looking back applied to the relative complexity of computable functions. Journal of Computer and System Sciences\u00a022, 53\u201359 (1981)","journal-title":"Journal of Computer and System Sciences"},{"key":"50_CR8","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1016\/0304-3975(83)90061-0","volume":"25","author":"J. Case","year":"1983","unstructured":"Case, J., Smith, C.: Comparison of identification criteria for machine inductive inference. Theoretical Computer Science\u00a025, 193\u2013220 (1983)","journal-title":"Theoretical Computer Science"},{"key":"50_CR9","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1016\/S0019-9958(67)91165-5","volume":"10","author":"E.M. Gold","year":"1967","unstructured":"Gold, E.M.: Language identification in the limit. Information and Control\u00a010, 447\u2013474 (1967)","journal-title":"Information and Control"},{"key":"50_CR10","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1090\/S0002-9947-1965-0170805-7","volume":"117","author":"J. Hartmanis","year":"1965","unstructured":"Hartmanis, J., Stearns, R.: On the computational complexity of algorithms. Transactions of the American Mathematical Society\u00a0117, 285\u2013306 (1965)","journal-title":"Transactions of the American Mathematical Society"},{"key":"50_CR11","volume-title":"Introduction to automata theory languages and computation","author":"J. Hopcroft","year":"1979","unstructured":"Hopcroft, J., Ullman, J.: Introduction to automata theory languages and computation. Addison-Wesley Publishing Company, Reading (1979)"},{"key":"50_CR12","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/2003.001.0001","volume-title":"Computability and complexity from a programming perspective","author":"N. Jones","year":"1997","unstructured":"Jones, N.: Computability and complexity from a programming perspective. MIT Press, Cambridge (1997)"},{"key":"50_CR13","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":"Jain, S., Osherson, D., Royer, J., Sharma, A.: Systems that learn: An introduction to learning theory, 2nd edn. MIT Press, Cambridge (1999)","edition":"2"},{"key":"50_CR14","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1145\/321864.321877","volume":"22","author":"R. Ladner","year":"1975","unstructured":"Ladner, R.: On the structure of polynomial time reducibility. Journal of the ACM\u00a022, 155\u2013171 (1975)","journal-title":"Journal of the ACM"},{"key":"50_CR15","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/0304-3975(81)90069-4","volume":"15","author":"L. Landweber","year":"1981","unstructured":"Landweber, L., Lipton, R., Robertson, E.: On the structure of sets in NP and other complexity classes. Theoretical Computer Science\u00a015, 181\u2013200 (1981)","journal-title":"Theoretical Computer Science"},{"key":"50_CR16","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-2606-0","volume-title":"An introduction to Kolmogorov complexity and its applications","author":"M. Li","year":"1997","unstructured":"Li, M., Vit\u00e1nyi, P.: An introduction to Kolmogorov complexity and its applications, 2nd edn. Springer, Heidelberg (1997)","edition":"2"},{"key":"50_CR17","volume-title":"Introduction to mathematical logic","author":"E. Mendelson","year":"1997","unstructured":"Mendelson, E.: Introduction to mathematical logic, 4th edn. Chapman & Hall, London (1997)","edition":"4"},{"key":"50_CR18","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0249-3","volume-title":"Subrecursive programming systems: Complexity & succinctness","author":"J. Royer","year":"1994","unstructured":"Royer, J., Case, J.: Subrecursive programming systems: Complexity & succinctness. Birkh\u00e4user, Basel (1994)"},{"key":"50_CR19","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1016\/0022-0000(88)90036-0","volume":"36","author":"K. Regan","year":"1988","unstructured":"Regan, K.: The topology of provability in complexity theory. Journal of Computer and System Sciences\u00a036, 384\u2013432 (1988)","journal-title":"Journal of Computer and System Sciences"},{"key":"#cr-split#-50_CR20.1","unstructured":"Rogers, H.: Theory of recursive functions and effective computability. Mc- Graw Hill, New York (1967);"},{"key":"#cr-split#-50_CR20.2","unstructured":"Reprinted MIT Press, Cambridge (1987)"},{"key":"50_CR21","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0304-3975(82)90114-1","volume":"18","author":"U. Schoning","year":"1982","unstructured":"Schoning, U.: A uniform approach to obtain diagonal sets in complexity classes. Theoretical Computer Science\u00a018, 95\u2013103 (1982)","journal-title":"Theoretical Computer Science"},{"key":"50_CR22","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/0304-3975(85)90217-8","volume":"38","author":"D. Schmidt","year":"1985","unstructured":"Schmidt, D.: The recursion-theoretic structure of complexity classes. Theoretical Computer Science\u00a038, 143\u2013156 (1985)","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Learning Theory and Kernel Machines"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-45167-9_50","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,6,7]],"date-time":"2020-06-07T11:03:18Z","timestamp":1591527798000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-45167-9_50"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540407201","9783540451679"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-45167-9_50","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2003]]}}}