{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:33:28Z","timestamp":1725456808110},"publisher-location":"Berlin, Heidelberg","reference-count":46,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540617785"},{"type":"electronic","value":"9783540706786"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/bfb0033340","type":"book-chapter","created":{"date-parts":[[2005,12,1]],"date-time":"2005-12-01T05:45:44Z","timestamp":1133415944000},"page":"22-47","source":"Crossref","is-referenced-by-count":1,"title":["Inductive inference from positive data: from heuristic to characterizing methods"],"prefix":"10.1007","author":[{"given":"Timo","family":"Knuutila","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,17]]},"reference":[{"key":"2_CR1","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1016\/0022-0000(80)90041-0","volume":"21","author":"D. Angluin","year":"1980","unstructured":"D. Angluin. Finding patterns common to a set of strings. Journal of Computer and System Sciences, 21:46\u201362, 1980.","journal-title":"Journal of Computer and System Sciences"},{"key":"2_CR2","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/S0019-9958(80)90285-5","volume":"45","author":"D. Angluin","year":"1980","unstructured":"D. Angluin. Inductive inference of formal languages from positive data. Information and Control, 45:117\u2013135, 1980.","journal-title":"Information and Control"},{"issue":"3","key":"2_CR3","doi-asserted-by":"publisher","first-page":"741","DOI":"10.1145\/322326.322334","volume":"29","author":"D. Angluin","year":"1982","unstructured":"D. Angluin. Inference of reversible languages. Journal of the ACM, 29(3):741\u2013765, July 1982.","journal-title":"Journal of the ACM"},{"key":"2_CR4","volume-title":"The Theory of Parsing, Translation, and Compiling","author":"A. V. Aho","year":"1972","unstructured":"A. V. Aho and J. D. Ullman. The Theory of Parsing, Translation, and Compiling. Prentice-Hall, Englewood Cliffs, N.J., 1972."},{"key":"2_CR5","doi-asserted-by":"crossref","first-page":"592","DOI":"10.1109\/TC.1972.5009015","volume":"C-21","author":"A. W. Biermann","year":"1972","unstructured":"A. W. Biermann and J. A. Feldman. On the synthesis of finite state machines from samples of their behavior. IEEE Transactions on Computers, C-21:592\u2013597, June 1972.","journal-title":"IEEE Transactions on Computers"},{"key":"2_CR6","unstructured":"B. K. Bhargava and K-S. Fu. Transformations and inference of tree grammars for syntactic pattern recognition. In Proceedings of the 1974 IEEE International Conference on Systems, Man, and Cybernetics, Dallas, Texas, 1974."},{"key":"2_CR7","first-page":"293","volume":"SMC-7","author":"J. M. Brayer","year":"1977","unstructured":"J. M. Brayer and K-S. Fu. A note on the k-tail method of tree grammar inference. IEEE Transactions on Systems, Man, and Cybernetics, SMC-7:293\u2013300, April 1977.","journal-title":"IEEE Transactions on Systems, Man, and Cybernetics"},{"issue":"3","key":"2_CR8","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1142\/S0218196792000207","volume":"2","author":"A. Bonopera","year":"1992","unstructured":"A. Bonopera and B. Gaujal. Inference of reversible languages. International Journal of Algebra and Computation, 2(3):327\u2013349, 1992.","journal-title":"International Journal of Algebra and Computation"},{"key":"2_CR9","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-322-92151-2","volume-title":"Automatentheorie","author":"W. Brauer","year":"1984","unstructured":"Wilfried Brauer. Automatentheorie. B. G. Teubner, Stuttgart, 1984."},{"key":"2_CR10","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/0012-365X(82)90281-3","volume":"4","author":"J. A. Brzozowski","year":"1973","unstructured":"J. A. Brzozowski and I. Simon. Characterizations of locally testable events. Discrete Mathematics, 4:243\u2013271, 1973.","journal-title":"Discrete Mathematics"},{"key":"2_CR11","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":"2_CR12","volume-title":"Automata, Languages and Machines, volume A","author":"S. Eilenberg","year":"1974","unstructured":"S. Eilenberg. Automata, Languages and Machines, volume A. Academic Press, New York, 1974."},{"key":"2_CR13","doi-asserted-by":"crossref","unstructured":"S. Eilenberg and M. P. Sch\u00fctzenberger. On pseudovarieties. Adv. Math., pages 413\u2013418, 1976.","DOI":"10.1016\/0001-8708(76)90029-3"},{"issue":"3","key":"2_CR14","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/BF00979871","volume":"13","author":"H. Fukuda","year":"1984","unstructured":"H. Fukuda and K. Kamata. Inference of tree automata from sample set of trees. International Journal of Computer and Information Sciences, 13(3):177\u2013196, 1984.","journal-title":"International Journal of Computer and Information Sciences"},{"issue":"2","key":"2_CR15","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/BF00975630","volume":"5","author":"R. C. Gonzalez","year":"1976","unstructured":"R. C. Gonzalez, J. J. Edwards, and M. G. Thomason. An algorithm for the inference of tree grammars. International Journal of Computer and Information Sciences, 5(2):145\u2013164, 1976.","journal-title":"International Journal of Computer and Information Sciences"},{"key":"2_CR16","doi-asserted-by":"crossref","first-page":"806","DOI":"10.1109\/PGEC.1966.264264","volume":"EC-15","author":"A. Ginzburg","year":"1966","unstructured":"A. Ginzburg. About some properties of definite, reverse-definite and related automata. IEEE Transactions on Electronic Computation, EC-15:806\u2013810, 1966.","journal-title":"IEEE Transactions on Electronic Computation"},{"key":"2_CR17","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. Information and Control, 10:447\u2013474, 1967.","journal-title":"Information and Control"},{"key":"2_CR18","volume-title":"Tree Automata","author":"F. G\u00e9cseg","year":"1984","unstructured":"F. G\u00e9cseg and M. Steinby. Tree Automata. Akad\u00e9miai Kiad\u00f3, Budapest, 1984."},{"key":"2_CR19","volume-title":"Syntactic Pattern Recognition: An Introduction","author":"R. C. Gonzalez","year":"1978","unstructured":"R. C. Gonzalez and M. G. Thomason. Syntactic Pattern Recognition: An Introduction. Addison-Wesley, Reading, MA, 1978."},{"issue":"9","key":"2_CR20","doi-asserted-by":"publisher","first-page":"920","DOI":"10.1109\/34.57687","volume":"PAMI-12","author":"P. Garci\u00e1","year":"1990","unstructured":"P. Garci\u00e1 and E. Vidal. Inference of k-testable languages in the strict sense and application to syntactic pattern recognition. IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-12(9):920\u2013925, September 1990.","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"2_CR21","first-page":"42","volume-title":"Equivalence of models for polynomial learnability","author":"D. Haussler","year":"1988","unstructured":"D. Haussler, M. Kearns, N. Littlestone, and M. K. Warmuth. Equivalence of models for polynomial learnability. In Haussler and Pitt, pages 42\u201355."},{"volume-title":"Proceedings of the 1st Workshop on Computational Learning Theory, 1988","year":"1988","key":"2_CR22","unstructured":"D. Haussler and L. Pitt, editors. Proceedings of the 1st Workshop on Computational Learning Theory, 1988. Morgan Kaufmann, San Mateo, CA, 1988."},{"key":"2_CR23","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1007\/BF03037092","volume":"8","author":"K. P. Jantke","year":"1991","unstructured":"K. P. Jantke. Monotonic and non-monotonic inductive inference. New Generation Computing, 8:349\u2013360, 1991.","journal-title":"New Generation Computing"},{"key":"2_CR24","first-page":"465","volume":"17","author":"K. P. Jantke","year":"1981","unstructured":"K. P. Jantke and H. R. Beick. Combining postulates of naturalness in inductive inference. Elektronische Informationsverarbeitung und Kybernetik, 17:465\u2013484, 1981.","journal-title":"Elektronische Informationsverarbeitung und Kybernetik"},{"volume-title":"Number 744 in Lecture Notes in Artificial Intelligence","year":"1993","key":"2_CR25","unstructured":"K. P. Jantke, S. Kobayashi, E. Tomita, and T. Yokomori, editors. Proceedings of the 4th Workshop on Algorithmic Learning Theory, 1993, Tokyo. Number 744 in Lecture Notes in Artificial Intelligence. Springer-Verlag, New York, 1993."},{"key":"2_CR26","doi-asserted-by":"crossref","unstructured":"K. Kamata. Inference methods for tree automata from sample set of trees. In Proceedings of the 1988 IEEE International Conference on Systems, Man, and Cybernetics, pages 490\u2013493, 1988.","DOI":"10.1109\/ICSMC.1988.754345"},{"key":"2_CR27","first-page":"209","volume-title":"Number 744 in Lecture Notes in Artificial Intelligence","author":"T. Knuutila","year":"1993","unstructured":"T. Knuutila. How to invent characterizable inference methods for regular languages. In Jantke et al., pages 209\u2013222."},{"key":"2_CR28","first-page":"109","volume-title":"Inference of k-testable tree languages","author":"T. Knuutila","year":"1993","unstructured":"T. Knuutila. Inference of k-testable tree languages. In H. Bunke, editor, Proceedings of the International Workshop on Structural and Syntactic Pattern Recognition, Bern, Switzerland, 1992, pages 109\u2013120. World Scientific, Singapore, 1993."},{"key":"2_CR29","volume-title":"PhD thesis","author":"T. Knuutila","year":"1994","unstructured":"T. Knuutila. On the Inductive Inference of Regular String and Tree Languages. PhD thesis, Department of Computer Science, University of Turku, Turku, Finland, 1994."},{"key":"2_CR30","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1016\/0304-3975(94)90033-7","volume":"129","author":"T. Knuutila","year":"1994","unstructured":"T. Knuutila and M. Steinby. Inference of tree languages from a finite samples: an algebraic approach. Theoretical Computer Science, 129:337\u2013367, 1994.","journal-title":"Theoretical Computer Science"},{"key":"2_CR31","first-page":"433","volume-title":"Proceedings of the 21st Annual ACM STOC","author":"M. Kearns","year":"1989","unstructured":"M. Kearns and L. G. Valiant. Cryptographic limitations on learning Boolean formulae and finite automata. In Proceedings of the 21st Annual ACM STOC, pages 433\u2013444. Assoc. Comp. Mach., New York, 1989."},{"issue":"3","key":"2_CR32","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1109\/TPAMI.1981.4767101","volume":"PAMI-3","author":"B. Levine","year":"1981","unstructured":"B. Levine. Derivatives of tree sets with applications to grammatical inference. IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-3(3):285\u2013293, May 1981.","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"2_CR33","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1007\/BF03037093","volume":"8","author":"S. Lange","year":"1991","unstructured":"S. Lange and R. Wiehagen. Polynomial-time inference of arbitrary pattern languages. New Generation Computing, 8:361\u2013370, 1991.","journal-title":"New Generation Computing"},{"key":"2_CR34","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1016\/0020-0190(90)90074-8","volume":"36","author":"E. M\u00e4kinen","year":"1990","unstructured":"E. M\u00e4kinen. The grammatical inference problem for the Szilard languages of linear grammars. Information Processing Letters, 36:203\u2013206, 1990.","journal-title":"Information Processing Letters"},{"key":"2_CR35","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1007\/BF01761708","volume":"8","author":"R. McNaughton","year":"1974","unstructured":"R. McNaughton. Algebraic decision procedures for local testability. Math. Syst. Theor., 8:60\u201376, 1974.","journal-title":"Math. Syst. Theor."},{"key":"2_CR36","volume-title":"Structural Methods in Pattern Recognition","author":"L. Miclet","year":"1986","unstructured":"L. Miclet. Structural Methods in Pattern Recognition, Springer-Verlag, New York, 1986."},{"key":"2_CR37","volume-title":"Inductive Acquisition of Expert Knowledge","author":"S. Muggleton","year":"1990","unstructured":"S. Muggleton. Inductive Acquisition of Expert Knowledge. Addison-Wesley, Reading, MA, 1990."},{"key":"2_CR38","doi-asserted-by":"crossref","unstructured":"J. E. Pin. Varieties of Formal Languages. North Oxford Academic, 1986.","DOI":"10.1007\/978-1-4613-2215-3"},{"key":"2_CR39","doi-asserted-by":"crossref","first-page":"982","DOI":"10.1109\/TSMC.1987.6499309","volume":"SMC-17","author":"V. Radhakrishnan","year":"1987","unstructured":"V. Radhakrishnan and G. Nagaraja. Inference of regular grammars via skeletons. IEEE Transactions on Systems, Man, and Cybernetics, SMC-17:982\u2013992, 1987.","journal-title":"IEEE Transactions on Systems, Man, and Cybernetics"},{"key":"2_CR40","unstructured":"A. Salomaa. Theory of Automata. Pergamon Press, 1969."},{"key":"2_CR41","first-page":"57","volume-title":"Tree Automata and Languages","author":"M. Steinby","year":"1992","unstructured":"M. Steinby. A theory of tree language varieties. In M. Nivat and A. Podelski, editors, Tree Automata and Languages, pages 57\u201381. Elsevier Science Publishers B.V., Amsterdam, 1992."},{"key":"2_CR42","first-page":"125","volume":"E75-D","author":"N. Tanida","year":"1992","unstructured":"N. Tanida and T. Yokomori. Polynomial-time identification of strictly regular languages in the limit. IEICE Transactions on Information and Systems, E75-D:125\u2013132, 1992.","journal-title":"IEICE Transactions on Information and Systems"},{"issue":"11","key":"2_CR43","doi-asserted-by":"publisher","first-page":"1134","DOI":"10.1145\/1968.1972","volume":"27","author":"L. G. Valiant","year":"1984","unstructured":"L. G. Valiant. A theory of the learnable. Communications of the ACM, 27(11):1134\u20131142, 1984.","journal-title":"Communications of the ACM"},{"key":"2_CR44","first-page":"184","volume-title":"number 543 in Lecture Notes in Artificial Intelligence","author":"R. Wiehagen","year":"1991","unstructured":"R. Wiehagen. A thesis in inductive inference. In J. Dix, K. P. Jantke, and P. H. Schmitt, editors, Proceedings of the 2nd International Workshop on Nonmonotonic and Inductive Logic, 1991, Reinhardsbrunn Castle, Germany, number 543 in Lecture Notes in Artificial Intelligence, pages 184\u2013207. Springer-Verlag, New York, 1991."},{"key":"2_CR45","first-page":"113","volume-title":"Learning local languages and its application to protein \u03b1-chain calculation","author":"T. Yokomori","year":"1994","unstructured":"T. Yokomori, N. Ishida, and S. Kobayashi. Learning local languages and its application to protein \u03b1-chain calculation. In Proceedings of the 27th Hawaii International Conference on System Sciences, pages 113\u2013122. IEEE Computer Society Press, Los Alamitos, CA, 1994."},{"key":"2_CR46","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1016\/S0022-0000(72)80020-5","volume":"6","author":"Y. Zalcstein","year":"1972","unstructured":"Y. Zalcstein. Locally testable languages. Journal of Computer and System Sciences, 6:151\u2013167, 1972.","journal-title":"Journal of Computer and System Sciences"}],"container-title":["Lecture Notes in Computer Science","Grammatical Interference: Learning Syntax from Sentences"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0033340","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,6]],"date-time":"2019-02-06T04:52:44Z","timestamp":1549428764000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0033340"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540617785","9783540706786"],"references-count":46,"URL":"https:\/\/doi.org\/10.1007\/bfb0033340","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]}}}