{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T02:47:28Z","timestamp":1764557248805},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642299513"},{"type":"electronic","value":"9783642299520"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-29952-0_41","type":"book-chapter","created":{"date-parts":[[2012,5,3]],"date-time":"2012-05-03T06:14:09Z","timestamp":1336025649000},"page":"423-434","source":"Crossref","is-referenced-by-count":1,"title":["On the Amount of Nonconstructivity in Learning Formal Languages from Positive Data"],"prefix":"10.1007","author":[{"given":"Sanjay","family":"Jain","sequence":"first","affiliation":[]},{"given":"Frank","family":"Stephan","sequence":"additional","affiliation":[]},{"given":"Thomas","family":"Zeugmann","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1","key":"41_CR1","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1016\/0022-0000(80)90041-0","volume":"21","author":"D. Angluin","year":"1980","unstructured":"Angluin, D.: Finding patterns common to a set of strings. Journal of Computer and System Sciences\u00a021(1), 46\u201362 (1980)","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"41_CR2","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/S0019-9958(80)90285-5","volume":"45","author":"D. Angluin","year":"1980","unstructured":"Angluin, D.: Inductive inference of formal languages from positive data. Information and Control\u00a045(2), 117\u2013135 (1980)","journal-title":"Information and Control"},{"key":"#cr-split#-41_CR3.1","unstructured":"Barzdin, J.: Inductive inference of automata, functions and programs. In: Proc. of the 20th International Congress of Mathematicians, Vancouver, Canada, pp. 455-460 (1974)"},{"key":"#cr-split#-41_CR3.2","unstructured":"republished in Amer. Math. Soc. Transl. 109 (2), 107- 112 (1977)"},{"key":"41_CR4","first-page":"1251","volume":"9","author":"J.M. B\u0101rzdi\u0146\u0161","year":"1968","unstructured":"B\u0101rzdi\u0146\u0161, J.M.: Complexity of programs to determine whether natural numbers not greater than n belong to a recursively enumerable set. Soviet Mathematics Doklady\u00a09, 1251\u20131254 (1968)","journal-title":"Soviet Mathematics Doklady"},{"issue":"3","key":"41_CR5","doi-asserted-by":"publisher","first-page":"320","DOI":"10.1016\/j.ic.2010.11.006","volume":"209","author":"O. Beyersdorff","year":"2011","unstructured":"Beyersdorff, O., K\u00f6bler, J., M\u00fcller, S.: Proof systems that take advice. Information and Computation\u00a0209(3), 320\u2013332 (2011)","journal-title":"Information and Computation"},{"issue":"4","key":"41_CR6","doi-asserted-by":"publisher","first-page":"1353","DOI":"10.2178\/jsl\/1203350791","volume":"72","author":"S. Cook","year":"2007","unstructured":"Cook, S., Kraji\u010dek, J.: Consequences of the provability of NP\u2009\u2286\u2009P\/poly. The Journal of Symbolic Logic\u00a072(4), 1353\u20131371 (2007)","journal-title":"The Journal of Symbolic Logic"},{"key":"41_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1007\/3-540-60246-1_121","volume-title":"Mathematical Foundations of Computer Science 1995","author":"C. Damm","year":"1995","unstructured":"Damm, C., Holzer, M.: Automata that Take Advice. In: H\u00e1jek, P., Wiedermann, J. (eds.) MFCS 1995. LNCS, vol.\u00a0969, pp. 149\u2013158. Springer, Heidelberg (1995)"},{"issue":"4","key":"41_CR8","doi-asserted-by":"publisher","first-page":"292","DOI":"10.1090\/S0002-9904-1947-08785-1","volume":"53","author":"P. Erd\u0151s","year":"1947","unstructured":"Erd\u0151s, P.: Some remarks on the theory of graphs. Bulletin of the American Mathematical Society\u00a053(4), 292\u2013294 (1947)","journal-title":"Bulletin of the American Mathematical Society"},{"key":"41_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1007\/978-3-642-02979-0_26","volume-title":"Implementation and Application of Automata","author":"R. Freivalds","year":"2009","unstructured":"Freivalds, R.: Amount of Nonconstructivity in Finite Automata. In: Maneth, S. (ed.) CIAA 2009. LNCS, vol.\u00a05642, pp. 227\u2013236. Springer, Heidelberg (2009)"},{"issue":"38-39","key":"41_CR10","doi-asserted-by":"publisher","first-page":"3436","DOI":"10.1016\/j.tcs.2010.05.038","volume":"411","author":"R. Freivalds","year":"2010","unstructured":"Freivalds, R.: Amount of nonconstructivity in deterministic finite automata. Theoretical Computer Science\u00a0411(38-39), 3436\u20133443 (2010)","journal-title":"Theoretical Computer Science"},{"key":"41_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"332","DOI":"10.1007\/978-3-642-20877-5_33","volume-title":"Theory and Applications of Models of Computation","author":"R. Freivalds","year":"2011","unstructured":"Freivalds, R., Zeugmann, T.: On the Amount of Nonconstructivity in Learning Recursive Functions. In: Ogihara, M., Tarui, J. (eds.) TAMC 2011. LNCS, vol.\u00a06648, pp. 332\u2013343. Springer, Heidelberg (2011)"},{"key":"41_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1007\/3-540-62064-8_12","volume-title":"Perspectives of System Informatics","author":"R. Freivalds","year":"1996","unstructured":"Freivalds, R., Zeugmann, T.: Co\u2013Learning of Recursive Languages from Positive Data. In: Bj\u00f8rner, D., Broy, M., Pottosin, I.V. (eds.) PSI 1996. LNCS, vol.\u00a01181, pp. 122\u2013133. Springer, Heidelberg (1996)"},{"issue":"5","key":"41_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":"Gold, E.M.: Language identification in the limit. Inform. Control\u00a010(5), 447\u2013474 (1967)","journal-title":"Inform. Control"},{"issue":"1-2","key":"41_CR14","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/S0304-3975(99)00269-8","volume":"241","author":"S. Jain","year":"2000","unstructured":"Jain, S., Kinber, E., Lange, S., Wiehagen, R., Zeugmann, T.: Learning languages and functions by erasing. Theoretical Computer Science\u00a0241(1-2), 143\u2013189 (2000)","journal-title":"Theoretical Computer Science"},{"key":"41_CR15","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.S., Sharma, A.: Systems that Learn: An Introduction to Learning Theory, 2nd edn. MIT Press, Cambridge (1999)","edition":"2"},{"key":"41_CR16","doi-asserted-by":"crossref","unstructured":"Jain, S., Stephan, F., Zeugmann, T.: On the amount of nonconstructivity in learning formal languages from text. Tech. Rep. TCS-TR-A-12-55, Division of Computer Science, Hokkaido University (2012)","DOI":"10.1007\/978-3-642-29952-0_41"},{"issue":"4","key":"41_CR17","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/BF03037092","volume":"8","author":"K.P. Jantke","year":"1991","unstructured":"Jantke, K.P.: Monotonic and non-monotonic inductive inference. New Generation Computing\u00a08(4), 349\u2013360 (1991)","journal-title":"New Generation Computing"},{"key":"41_CR18","first-page":"191","volume":"28","author":"R.M. Karp","year":"1982","unstructured":"Karp, R.M., Lipton, R.J.: Turing machines that take advice. L\u2019 Enseignement Math\u00e9matique\u00a028, 191\u2013209 (1982)","journal-title":"L\u2019 Enseignement Math\u00e9matique"},{"key":"41_CR19","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1145\/130385.130427","volume-title":"Proc. 5th Annual ACM Workshop on Computational Learning Theory","author":"S. Lange","year":"1992","unstructured":"Lange, S., Zeugmann, T.: Types of monotonic language learning and their characterization. In: Haussler, D. (ed.) Proc. 5th Annual ACM Workshop on Computational Learning Theory, pp. 377\u2013390. ACM Press, New York (1992)"},{"key":"41_CR20","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1145\/168304.168320","volume-title":"Proceedings of the Sixth Annual ACM Conference on Computational Learning Theory","author":"S. Lange","year":"1993","unstructured":"Lange, S., Zeugmann, T.: Language learning in dependence on the space of hypotheses. In: Pitt, L. (ed.) Proceedings of the Sixth Annual ACM Conference on Computational Learning Theory, pp. 127\u2013136. ACM Press, New York (1993)"},{"issue":"1-3","key":"41_CR21","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1016\/j.tcs.2008.02.030","volume":"397","author":"S. Lange","year":"2008","unstructured":"Lange, S., Zeugmann, T., Zilles, S.: Learning indexed families of recursive languages from positive data: A survey. Theoretical Computer Science\u00a0397(1-3), 194\u2013232 (2008)","journal-title":"Theoretical Computer Science"},{"key":"41_CR22","unstructured":"Rogers Jr., H.: Theory of Recursive Functions and Effective Computability. McGraw-Hill (1967); reprinted, MIT Press 1987"},{"key":"41_CR23","series-title":"LNAI","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1007\/3-540-60217-8_12","volume-title":"Algorithmic Learning for Knowledge-Based Systems","author":"T. Zeugmann","year":"1995","unstructured":"Zeugmann, T., Lange, S.: A Guided Tour Across the Boundaries of Learning Recursive Languages. In: Lange, S., Jantke, K.P. (eds.) GOSLER 1994. LNCS (LNAI), vol.\u00a0961, pp. 190\u2013258. Springer, Heidelberg (1995)"},{"key":"41_CR24","unstructured":"Zeugmann, T., Minato, S., Okubo, Y.: Theory of Computation. Corona Publishing Co, Ltd. (2009)"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-29952-0_41.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T11:23:00Z","timestamp":1620127380000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-29952-0_41"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642299513","9783642299520"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-29952-0_41","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}