{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,10,17]],"date-time":"2022-10-17T01:40:30Z","timestamp":1665970830929},"reference-count":28,"publisher":"Institute of Electronics, Information and Communications Engineers (IEICE)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEICE Trans. Inf. & Syst."],"published-print":{"date-parts":[[2020,3,1]]},"DOI":"10.1587\/transinf.2019fcp0009","type":"journal-article","created":{"date-parts":[[2020,2,29]],"date-time":"2020-02-29T22:11:02Z","timestamp":1583014262000},"page":"526-539","source":"Crossref","is-referenced-by-count":0,"title":["An Efficient Learning Algorithm for Regular Pattern Languages Using One Positive Example and a Linear Number of Membership Queries"],"prefix":"10.1587","volume":"E103.D","author":[{"given":"Satoshi","family":"MATSUMOTO","sequence":"first","affiliation":[{"name":"School of Science, Tokai University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tomoyuki","family":"UCHIDA","sequence":"additional","affiliation":[{"name":"Graduate School of Information Sciences, Hiroshima City University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Takayoshi","family":"SHOUDAI","sequence":"additional","affiliation":[{"name":"Faculty of Contemporary Business, Kyushu International University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yusuke","family":"SUZUKI","sequence":"additional","affiliation":[{"name":"Graduate School of Information Sciences, Hiroshima City University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tetsuhiro","family":"MIYAHARA","sequence":"additional","affiliation":[{"name":"Graduate School of Information Sciences, Hiroshima City University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"532","reference":[{"key":"1","doi-asserted-by":"publisher","unstructured":"[1] D. Angluin, \u201cQueries and concept learning,\u201d Machine Learning, vol.2, no.4, pp.319-342, 1988. 10.1007\/bf00116828","DOI":"10.1007\/BF00116828"},{"key":"2","unstructured":"[2] H. Mamitsuka and N. Abe, \u201cEfficient mining from large databases by query learning,\u201d Proc. 7th International Conference on Machine Learning (ICML'00), pp.575-582, 2000."},{"key":"3","doi-asserted-by":"publisher","unstructured":"[3] D. Angluin, \u201cFinding patterns common to a set of strings,\u201d Journal of Computer and System Sciences, vol.21, no.1, pp.46-62, 1980. 10.1016\/0022-0000(80)90041-0","DOI":"10.1016\/0022-0000(80)90041-0"},{"key":"4","unstructured":"[4] A. Marron, \u201cLearning pattern languages from a single initial example and from queries,\u201d Proc. Workshop on Computational Learning Theory (COLT'88), pp.345-358, 1988."},{"key":"5","doi-asserted-by":"crossref","unstructured":"[5] S. Matsumoto and A. Shinohara, \u201cLearning pattern languages using queries,\u201d Proc. European Conf. on Computational Learning Theory (EuroCOLT'97), LNAI, vol.1208, pp.185-197, Springer, Berlin, 1997. 10.1007\/3-540-62685-9_16","DOI":"10.1007\/3-540-62685-9_16"},{"key":"6","doi-asserted-by":"publisher","unstructured":"[6] S. Lange and R. Wiehagen, \u201cPolynomial-time inference of arbitrary pattern languages,\u201d New Generation Computing, vol.8, no.4, pp.361-370, 1991. 10.1007\/bf03037093","DOI":"10.1007\/BF03037093"},{"key":"7","doi-asserted-by":"crossref","unstructured":"[7] D. Angluin, \u201cLearning regular sets from queries and counterexamples,\u201d Information and Computation, vol.75, no.2, pp.87-106, 1987. 10.1016\/0890-5401(87)90052-6","DOI":"10.1016\/0890-5401(87)90052-6"},{"key":"8","doi-asserted-by":"publisher","unstructured":"[8] J. Nessel and S. Lange, \u201cLearning erasing pattern languages with queries,\u201d Theoretical Computer Science, vol.348, no.1, pp.41-57, 2005. 10.1016\/j.tcs.2005.09.001","DOI":"10.1016\/j.tcs.2005.09.001"},{"key":"9","doi-asserted-by":"crossref","unstructured":"[9] H. Sakamoto, K. Hirata, and H. Arimura, \u201cLearning elementary formal systems with queries,\u201d Theoretical Computer Science, vol.298, no.1, pp.21-50, 2003. 10.1016\/s0304-3975(02)00417-6","DOI":"10.1016\/S0304-3975(02)00417-6"},{"key":"10","doi-asserted-by":"crossref","unstructured":"[10] H. Kato, S. Matsumoto, and T. Miyahara, \u201cLearning of elementary formal systems with two clauses using queries,\u201d IEICE Trans. Inf. & Syst., vol.E92-D, no.2, pp.172-180, 2009. 10.1587\/transinf.e92.d.172","DOI":"10.1587\/transinf.E92.D.172"},{"key":"11","doi-asserted-by":"publisher","unstructured":"[11] S. Matsumoto, T. Shoudai, T. Uchida, T. Miyahara, and Y. Suzuki, \u201cLearning of finite unions of tree patterns with internal structured variables from queries,\u201d IEICE Trans. Inf. & Syst., vol.E91-D, no.2, pp.222-230, 2008. 10.1093\/ietisy\/e91-d.2.222","DOI":"10.1093\/ietisy\/e91-d.2.222"},{"key":"12","doi-asserted-by":"publisher","unstructured":"[12] T. Uchida, S. Matsumoto, T. Shoudai, Y. Suzuki, and T. Miyahara, \u201cExact learning of primitive formal system defining labeled ordered tree languages via queries,\u201d IEICE Trans. Inf. & Syst., vol.E101-D, no.3, pp.470-482, 2019. 10.1587\/transinf.2018fcp0011","DOI":"10.1587\/transinf.2018FCP0011"},{"key":"13","doi-asserted-by":"publisher","unstructured":"[13] A. Nakamura, \u201cAn efficient query learning algorithm for ordered binary decision diagrams,\u201d Information and Computation, vol.201, no.2, pp.178-198, 2005. 10.1016\/j.ic.2005.05.003","DOI":"10.1016\/j.ic.2005.05.003"},{"key":"14","unstructured":"[14] H. Mizumoto, S. Todoroki, Diptarama, R. Yoshinaka, and A.Shinohara, \u201cAn efficient query learning algorithm for zero-suppressed binary decision diagrams,\u201d Proc. Machine Learning Research (ALT2017), vol.76, pp.1-12, 2017."},{"key":"15","unstructured":"[15] S. Matsumoto, T. Uchida, T. Shoudai, Y. Suzuki, and T. Miyahara, \u201cExact learning of regular pattern languages from one positive example using a linear number of membership queries,\u201d Proc. 27th International MultiConference of Engineers and Computer Scientists (IMECS2019), pp.204-209, 2019."},{"key":"16","unstructured":"[16] H. Arimura, R. Fujino, T. Shinohara, and S. Arikawa, \u201cProtein motif discovery from positive examples by minimal multiple generalization over regular patterns,\u201d Genome Informatics, vol.5, pp.39-48, 1994."},{"key":"17","unstructured":"[17] S. Shimozono, A. Shinohara, T. Shinohara, S. Miyano, S. Kuhara, and S. Arikawa, \u201cKnowledge acquisition from amino acid sequences by machine learning system BONSAI,\u201d Transactions of Information Processing Society of Japan, vol.35, no.10, pp.2009-2018, 1994."},{"key":"18","unstructured":"[18] T. Shoudai, M. Lappe, S. Miyano, A. Shinohara, T. Okazaki, S. Arikawa, T. Uchida, S. Shimozono, T. Shinohara, and S. Kuhara, \u201cBONSAI Garden: parallel knowledge discovery system for amino acid sequences,\u201d Proc. Third International Conference on Intelligent Systems for Molecular Biology, pp.359-366, 1995."},{"key":"19","unstructured":"[19] National Center for Biotechnology Information, NIH genetic sequence database. https:\/\/www.ncbi.nlm.nih.gov\/genbank\/, Sept. 2019."},{"key":"20","unstructured":"[20] Protein Information Resource (PIR). https:\/\/proteininformationresource.org\/pirwww\/, Sept. 2019."},{"key":"21","doi-asserted-by":"crossref","unstructured":"[21] K. Hattori, H. Yokono, and A. Aizawa, \u201cPhrase pattern generation for text classification,\u201d Proc. 29th Annual Conference of the Japanese Society for Artificial Intelligence, 2E1-4in, 2015 (in Japanese).","DOI":"10.1527\/tjsai.29.416"},{"key":"22","doi-asserted-by":"crossref","unstructured":"[22] B. Settles, \u201cFrom theories to queries: active learning in practice,\u201d Proc. Active Learning and Experimental Design Workshop in conjunction with AISTATS 2010, PMLR, pp.11-18, 2011.","DOI":"10.1007\/978-3-031-01560-1_2"},{"key":"23","doi-asserted-by":"crossref","unstructured":"[23] F. Howar and B. Steffen, \u201cActive automata learning in practice-an annotated bibliography of the years 2011 to 2016,\u201d Proc. Machine Learning for Dynamic Software Analysis: Potentials and Limits-International Dagstuhl Seminar 16172, LNCS 11026, pp.123-148, Springer, 2018. 10.1007\/978-3-319-96562-8_5","DOI":"10.1007\/978-3-319-96562-8_5"},{"key":"24","unstructured":"[24] International Community interested in Grammatical Inference, https:\/\/grammarlearning.org\/Active_Learning, Sept. 2019."},{"key":"25","unstructured":"[25] R.A. Servedio and S.J. Gortler, \u201cQuantum versus classical learnability,\u201d Proc. 16th Annual IEEE Conference on Computational Complexity (CoCo2001), pp.138-148, 2001. 10.1109\/ccc.2001.933881"},{"key":"26","unstructured":"[26] Quantum Algorithm Zoo, https:\/\/quantumalgorithmzoo.org, Sept. 2019."},{"key":"27","doi-asserted-by":"crossref","unstructured":"[27] S. Aaronson, D. Grier, and L. Schaeffer, \u201cA quantum query complexity trichotomy for regular languages,\u201d Electronic Colloquium on Computational Complexity (ECCC), 26:61, 2019.","DOI":"10.1109\/FOCS.2019.00061"},{"key":"28","doi-asserted-by":"publisher","unstructured":"[28] Y. Suzuki, T. Shoudai, T. Uchida, and T. Miyahara, \u201cOrdered term tree languages which are polynomial time inductively inferable from positive data,\u201d Theoretical Computer Science, vol.350, no.1, pp.63-90, 2006. 10.1016\/j.tcs.2005.10.022","DOI":"10.1016\/j.tcs.2005.10.022"}],"container-title":["IEICE Transactions on Information and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transinf\/E103.D\/3\/E103.D_2019FCP0009\/_pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,17]],"date-time":"2022-10-17T01:13:27Z","timestamp":1665969207000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transinf\/E103.D\/3\/E103.D_2019FCP0009\/_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,3,1]]},"references-count":28,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020]]}},"URL":"https:\/\/doi.org\/10.1587\/transinf.2019fcp0009","relation":{},"ISSN":["0916-8532","1745-1361"],"issn-type":[{"value":"0916-8532","type":"print"},{"value":"1745-1361","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,3,1]]}}}