{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:46:03Z","timestamp":1725558363178},"publisher-location":"Berlin, Heidelberg","reference-count":33,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540202912"},{"type":"electronic","value":"9783540396246"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-39624-6_19","type":"book-chapter","created":{"date-parts":[[2010,6,28]],"date-time":"2010-06-28T04:01:51Z","timestamp":1277697711000},"page":"234-246","source":"Crossref","is-referenced-by-count":3,"title":["Learning a Subclass of Regular Patterns in Polynomial Time"],"prefix":"10.1007","author":[{"given":"John","family":"Case","sequence":"first","affiliation":[]},{"given":"Sanjay","family":"Jain","sequence":"additional","affiliation":[]},{"given":"R\u00fcdiger","family":"Reischuk","sequence":"additional","affiliation":[]},{"given":"Frank","family":"Stephan","sequence":"additional","affiliation":[]},{"given":"Thomas","family":"Zeugmann","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"19_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, 46\u201362 (1980)","journal-title":"Journal of Computer and System Sciences"},{"key":"19_CR2","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/0304-3975(92)90068-Q","volume":"95","author":"S. Arikawa","year":"1992","unstructured":"Arikawa, S., Shinohara, T., Yamamoto, A.: Learning elementary formal systems. Theoretical Computer Science\u00a095, 97\u2013113 (1992)","journal-title":"Theoretical Computer Science"},{"key":"19_CR3","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1016\/S0304-3975(99)00270-4","volume":"241","author":"T. Shinohara","year":"2000","unstructured":"Shinohara, T., Arimura, H.: Inductive inference of unbounded unions of pattern languages from positive data. Theoretical Computer Science\u00a0241, 191\u2013209 (2000)","journal-title":"Theoretical Computer Science"},{"key":"19_CR4","doi-asserted-by":"crossref","unstructured":"Bratko, I., Muggleton, S.: Applications of inductive logic programming. Communications of the ACM (1995)","DOI":"10.1145\/219717.219771"},{"key":"19_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/BFb0009485","volume-title":"Algorithms and Computation","author":"A. Br\u0101zma","year":"1996","unstructured":"Br\u0101zma, A., Ukkonen, E., Vilo, J.: Discovering unbounded unions of regular pattern languages from positive examples. In: Nagamochi, H., Suri, S., Igarashi, Y., Miyano, S., Asano, T. (eds.) ISAAC 1996. LNCS, vol.\u00a01178, pp. 95\u2013104. Springer, Heidelberg (1996)"},{"key":"19_CR6","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1016\/S0304-3975(00)00274-7","volume":"268","author":"J. Case","year":"2001","unstructured":"Case, J., Jain, S., Kaufmann, S., Sharma, A., Stephan, F.: Predictive learning models for concept drift. Theoretical Computer Science\u00a0268, 323\u2013349 (2001) (Special Issue for ALT 1998)","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"19_CR7","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1006\/inco.1998.2784","volume":"152","author":"J. Case","year":"1999","unstructured":"Case, J., Jain, S., Lange, S., Zeugmann, T.: Incremental concept learning for bounded data mining. Information and Computation\u00a0152(1), 74\u2013110 (1999)","journal-title":"Information and Computation"},{"issue":"1","key":"19_CR8","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/S0304-3975(00)00136-5","volume":"261","author":"T. Erlebach","year":"2001","unstructured":"Erlebach, T., Rossmanith, P., Stadtherr, H., Steger, A., Zeugmann, T.: Learning one-variable pattern languages very efficiently on average, in parallel, and by asking queries. Theoretical Computer Science\u00a0261(1), 119\u2013156 (2001)","journal-title":"Theoretical Computer Science"},{"key":"19_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 & Control\u00a010, 447\u2013474 (1967)","journal-title":"Information & Control"},{"key":"19_CR10","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/B978-0-08-094829-4.50007-6","volume-title":"Proceedings of the Second Annual ACM Workshop on Computational Learning Theory","author":"M. Kearns","year":"1989","unstructured":"Kearns, M., Pitt, L.: A polynomial-time algorithm for learning k-variable pattern languages from examples. In: Rivest, R., Haussler, D., Warmuth, M.K. (eds.) Proceedings of the Second Annual ACM Workshop on Computational Learning Theory, pp. 57\u201371. Morgan Kaufmann Publishers Inc., San Francisco (1989)"},{"key":"19_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"252","DOI":"10.1007\/3-540-59119-2_182","volume-title":"Computational Learning Theory","author":"P. Kilpel\u00e4inen","year":"1995","unstructured":"Kilpel\u00e4inen, P., Mannila, H., Ukkonen, E.: MDL learning of unions of simple pattern languages from positive examples. In: Vit\u00e1nyi, P.M.B. (ed.) EuroCOLT 1995. LNCS, vol.\u00a0904, pp. 252\u2013260. Springer, Heidelberg (1995)"},{"key":"19_CR12","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1007\/BF03037093","volume":"8","author":"S. Lange","year":"1991","unstructured":"Lange, S., Wiehagen, R.: Polynomial time inference of arbitrary pattern languages. New Generation Computing\u00a08, 361\u2013370 (1991)","journal-title":"New Generation Computing"},{"key":"19_CR13","unstructured":"Lavra\u010d, N., D\u017eeroski, S.: Inductive Logic Programming: Techniques and Applications. Ellis Horwood (1994)"},{"key":"19_CR14","first-page":"335","volume-title":"Information Modeling and Knowledge Bases VIII","author":"S. Matsumoto","year":"1997","unstructured":"Matsumoto, S., Shinohara, A.: Learnability of subsequence languages. In: Information Modeling and Knowledge Bases VIII, pp. 335\u2013344. IOS Press, Amsterdam (1997)"},{"key":"19_CR15","volume-title":"Machine Learning","author":"T. Mitchell","year":"1997","unstructured":"Mitchell, T.: Machine Learning. McGraw Hill, New York (1997)"},{"key":"19_CR16","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/BF03037530","volume":"18","author":"S. Miyano","year":"2000","unstructured":"Miyano, S., Shinohara, A., Shinohara, T.: Polynomial-time learning of elementary formal systems. New Generation Computing\u00a018, 217\u2013242 (2000)","journal-title":"New Generation Computing"},{"key":"19_CR17","doi-asserted-by":"publisher","first-page":"669","DOI":"10.1016\/0743-1066(94)90035-3","volume":"19\/20","author":"S. Muggleton","year":"1994","unstructured":"Muggleton, S., De Raedt, L.: Inductive logic programming: Theory and methods. Journal of Logic Programming\u00a019\/20, 669\u2013679 (1994)","journal-title":"Journal of Logic Programming"},{"key":"19_CR18","unstructured":"Nix, R.: Editing by examples. Technical Report 280, Department of Computer Science, Yale University, New Haven, CT, USA (1983)"},{"key":"19_CR19","first-page":"308","volume-title":"Proceedings of 13th International Conference Algorithmic Learning Theory, ALT 2002","author":"D. Reidenbach","year":"2002","unstructured":"Reidenbach, D.: A Negative Result on Inductive Inference of Extended Pattern Languages. In: Cesa-Bianchi, N., Numao, M. (eds.) Proceedings of 13th International Conference Algorithmic Learning Theory, ALT 2002, pp. 308\u2013320. Springer, Heidelberg (2002)"},{"key":"19_CR20","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1145\/279943.279984","volume-title":"Proceedings of the Eleventh Annual Conference on Computational Learning Theory","author":"R. Reischuk","year":"1998","unstructured":"Reischuk, R., Zeugmann, T.: Learning one-variable pattern languages in linear average time. In: Proceedings of the Eleventh Annual Conference on Computational Learning Theory, pp. 198\u2013208. ACM Press, New York (1998)"},{"issue":"1\/2","key":"19_CR21","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1023\/A:1010875913047","volume":"44","author":"P. Rossmanith","year":"2001","unstructured":"Rossmanith, P., Zeugmann, T.: Stochastic Finite Learning of the Pattern Languages. Machine Learning\u00a044(1\/2), 67\u201391 (2001); Special Issue on Automata Induction, Grammar Inference, and Language Acquisition","journal-title":"Machine Learning"},{"key":"19_CR22","first-page":"46","volume":"54","author":"A. Salomaa","year":"1994","unstructured":"Salomaa, A.: Patterns (The Formal Language Theory Column). EATCS Bulletin\u00a054, 46\u201362 (1994)","journal-title":"EATCS Bulletin"},{"key":"19_CR23","first-page":"144","volume":"55","author":"A. Salomaa","year":"1994","unstructured":"Salomaa, A.: Return to patterns (The Formal Language Theory Column). EATCS Bulletin\u00a055, 144\u2013157 (1994)","journal-title":"EATCS Bulletin"},{"key":"19_CR24","first-page":"122","volume-title":"Proceedings, 3rd Annual ACM Workshop on Computational Learning Theory","author":"R. Schapire","year":"1990","unstructured":"Schapire, R.: Pattern languages are not learnable. In: Fulk, M.A., Case, J. (eds.) Proceedings, 3rd Annual ACM Workshop on Computational Learning Theory, pp. 122\u2013129. Morgan Kaufmann Publishers, Inc., San Francisco (1990)"},{"key":"19_CR25","first-page":"2009","volume":"35","author":"S. Shimozono","year":"1994","unstructured":"Shimozono, S., Shinohara, A., Shinohara, T., Miyano, S., Kuhara, S., Arikawa, S.: Knowledge acquisition from amino acid sequences by machine learning system BONSAI. Trans. Information Processing Society of Japan\u00a035, 2009\u20132018 (1994)","journal-title":"Trans. Information Processing Society of Japan"},{"key":"19_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1007\/3-540-11980-9_19","volume-title":"RIMS Symposium on Software Science and Engineering","author":"T. Shinohara","year":"1983","unstructured":"Shinohara, T.: Polynomial time inference of extended regular pattern languages. In: Goto, E., Nakajima, R., Yonezawa, A., Nakata, I., Furukawa, K. (eds.) RIMS 1982. LNCS, vol.\u00a0147, pp. 115\u2013127. Springer, Heidelberg (1983)"},{"key":"19_CR27","doi-asserted-by":"crossref","first-page":"83","DOI":"10.5109\/13347","volume":"20","author":"T. Shinohara","year":"1983","unstructured":"Shinohara, T.: Inferring unions of two pattern languages. Bulletin of Informatics and Cybernetics\u00a020, 83\u201388 (1983)","journal-title":"Bulletin of Informatics and Cybernetics"},{"key":"19_CR28","unstructured":"Shinohara, T., Arikawa, S.: Learning data entry systems: An application of inductive inference of pattern languages. Research Report 102, Research Institute of Fundamental Information Science, Kyushu University (1983)"},{"key":"19_CR29","series-title":"LNAI","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1007\/3-540-60217-8_13","volume-title":"Algorithmic Learning for Knowledge-Based Systems","author":"T. Shinohara","year":"1995","unstructured":"Shinohara, T., Arikawa, S.: Pattern inference. In: Lange, S., Jantke, K.P. (eds.) GOSLER 1994. LNCS (LNAI), vol.\u00a0961, pp. 259\u2013291. Springer, Heidelberg (1995)"},{"key":"19_CR30","doi-asserted-by":"crossref","unstructured":"Smullyan, R.: Theory of Formal Systems, Annals of Mathematical Studies, Princeton, NJ, vol.\u00a0(47) (1961)","DOI":"10.1515\/9781400882007"},{"key":"19_CR31","doi-asserted-by":"publisher","first-page":"1134","DOI":"10.1145\/1968.1972","volume":"27","author":"L.G. Valiant","year":"1984","unstructured":"Valiant, L.G.: A theory of the learnable. Communications of the ACM\u00a027, 1134\u20131142 (1984)","journal-title":"Communications of the ACM"},{"key":"19_CR32","doi-asserted-by":"crossref","first-page":"328","DOI":"10.1016\/B978-0-08-094829-4.50026-X","volume-title":"Proceedings of the Second Annual Workshop on Computational Learning Theory","author":"K. Wright","year":"1989","unstructured":"Wright, K.: Identification of unions of languages drawn from an identifiable class. In: Rivest, R., Haussler, D., Warmuth, M.K. (eds.) Proceedings of the Second Annual Workshop on Computational Learning Theory, pp. 328\u2013333. Morgan Kaufmann Publishers, Inc., San Francisco (1989)"},{"issue":"1\u20132","key":"19_CR33","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1023\/A:1018964207937","volume":"23","author":"T. Zeugmann","year":"1998","unstructured":"Zeugmann, T.: Lange and Wiehagen\u2019s pattern language learning algorithm: An average-case analysis with respect to its total learning time. Annals of Mathematics and Artificial Intelligence\u00a023(1\u20132), 117\u2013145 (1998)","journal-title":"Annals of Mathematics and Artificial Intelligence"}],"container-title":["Lecture Notes in Computer Science","Algorithmic Learning Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-39624-6_19.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T04:42:21Z","timestamp":1605760941000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-39624-6_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540202912","9783540396246"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-39624-6_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2003]]}}}