{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,6,4]],"date-time":"2023-06-04T04:04:45Z","timestamp":1685851485963},"reference-count":23,"publisher":"Institute of Electronics, Information and Communications Engineers (IEICE)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEICE Trans. Fundamentals"],"published-print":{"date-parts":[[2023,6,1]]},"DOI":"10.1587\/transfun.2022eap1052","type":"journal-article","created":{"date-parts":[[2022,12,13]],"date-time":"2022-12-13T22:09:53Z","timestamp":1670969393000},"page":"896-906","source":"Crossref","is-referenced-by-count":0,"title":["Parameterized Formal Graph Systems and Their Polynomial-Time PAC Learnability"],"prefix":"10.1587","volume":"E106.A","author":[{"given":"Takayoshi","family":"SHOUDAI","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, Fukuoka Institute of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Satoshi","family":"MATSUMOTO","sequence":"additional","affiliation":[{"name":"Department of Mathematical Sciences, Tokai 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":"Tomoyuki","family":"UCHIDA","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":"crossref","unstructured":"[1] 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":"2","doi-asserted-by":"crossref","unstructured":"[2] S. Arikawa, T. Shinohara, and A. Yamamoto, \u201cLearning elementary formal systems,\u201d Theoretical Computer Science, vol.95, pp.97-113, 1992. 10.1016\/0304-3975(92)90068-q","DOI":"10.1016\/0304-3975(92)90068-Q"},{"key":"3","doi-asserted-by":"crossref","unstructured":"[3] A. Blumer, A. Ehrenfeucht, D. Haussler, and M. Warmuth, \u201cLearnability and the Vapnik-Chervonenkis Dimension,\u201d J. ACM, vol.36, no.4, pp.929-965, 1989. 10.1145\/76359.76371","DOI":"10.1145\/76359.76371"},{"key":"4","doi-asserted-by":"publisher","unstructured":"[4] H.L. Bodlaender, \u201cA linear-time algorithm for finding tree-decompositions of small treewidth,\u201d SIAM J. Comput., vol.25, pp.1305-1317, 1990. 10.1137\/s0097539793251219","DOI":"10.1137\/S0097539793251219"},{"key":"5","unstructured":"[5] D. Chiang, J. Andreas, D. Bauer, K.M. Hermann, B. Jones, and K. Knight, \u201cParsing graphs with hyperedge replacement grammars,\u201d Proc. 51st Meeting of the ACL, Marie-Catherine de Marneffe, 2013."},{"key":"6","doi-asserted-by":"crossref","unstructured":"[6] R. Diestel, Graph Theory, 5th ed., Graduate Texts in Mathematics, vol.173, Springer, 2017.","DOI":"10.1007\/978-3-662-53622-3_7"},{"key":"7","doi-asserted-by":"publisher","unstructured":"[7] M. Grohe, D. Neuen, and P. Schweitzer, \u201cA faster isomorphism test for graphs of small degree,\u201d SIAM J. Comput., pp.FOCS18-1-FOCS18-36, 2020. 10.1137\/19m1245293","DOI":"10.1137\/19M1245293"},{"key":"8","doi-asserted-by":"crossref","unstructured":"[8] S. Hara and T. Shoudai, \u201cPolynomial time MAT learning of C-deterministic regular formal graph systems,\u201d Proc. 3rd International Conference on Advanced Applied Informatics, pp.204-211, 2014. 10.1109\/iiai-aai.2014.51","DOI":"10.1109\/IIAI-AAI.2014.51"},{"key":"9","doi-asserted-by":"publisher","unstructured":"[9] D. Haussler, M. Kearns, N. Littlestone, and M.K. Warmuth, \u201cEquivalence of models for polynomial learnability,\u201d Information and Computation, vol.95, no.2, pp.129-161, 1991. 10.1016\/0890-5401(91)90042-z","DOI":"10.1016\/0890-5401(91)90042-Z"},{"key":"10","doi-asserted-by":"publisher","unstructured":"[10] T. Horv\u00e1th, J. Ramon, and S. Wrobel, \u201cFrequent subgraph mining in outerplanar graphs,\u201d Data Min. Knowl. Disc., vol.21, pp.472-508, 2010. 10.1007\/s10618-009-0162-1","DOI":"10.1007\/s10618-009-0162-1"},{"key":"11","doi-asserted-by":"crossref","unstructured":"[11] J.W. Lloyd, Foundations of Logic Programming, 2nd extended ed., Springer, 1987. 10.1007\/978-3-642-83189-8","DOI":"10.1007\/978-3-642-83189-8"},{"key":"12","doi-asserted-by":"publisher","unstructured":"[12] S. Miyano, A. Shinohara, and T. Shinohara, \u201cPolynomial-time learning of elementary formal systems,\u201d New Gener. Comput., vol.18, pp.217-242, 2000. 10.1007\/bf03037530","DOI":"10.1007\/BF03037530"},{"key":"13","unstructured":"[13] M. Mohri, et al., Foundation of Machine Learning, 2nd ed., MIT Press, 2018."},{"key":"14","doi-asserted-by":"publisher","unstructured":"[14] B. Natarajan, \u201cOn learning sets and functions,\u201d Mach. Learn., vol.4, no.1, pp.67-97, 1989. 10.1007\/bf00114804","DOI":"10.1007\/BF00114804"},{"key":"15","unstructured":"[15] B. Natarajan, Machine Learning \u2014 A Theoretical Approach, Morgan Kaufmann Publishers, 1991."},{"key":"16","doi-asserted-by":"crossref","unstructured":"[16] 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":"17","doi-asserted-by":"crossref","unstructured":"[17] S. Shalev-Shwartz and S. Ben-David, Understanding Machine Learning: From Theory to Algorithms, Cambridge University Press, 2014. 10.1017\/cbo9781107298019","DOI":"10.1017\/CBO9781107298019"},{"key":"18","doi-asserted-by":"publisher","unstructured":"[18] C. Shibata and R. Yoshinaka, \u201cPAC learning of some subclasses of context-free grammars with basic distributional properties from positive data,\u201d Proc. 24th International Conference on Algorithmic Learning Theory, Springer, Lecture Notes in Artificial Intelligence, vol.8139, pp.143-157, 2013. 10.1007\/978-3-642-40935-6_11","DOI":"10.1007\/978-3-642-40935-6_11"},{"key":"19","unstructured":"[19] T. Uchida, T. Shoudai, and S. Miyano, \u201cParallel algorithms for refutation tree problem on formal graph systems,\u201d IEICE Trans. Inf. & Syst., vol.78, no.2, pp.99-112, 1995."},{"key":"20","doi-asserted-by":"publisher","unstructured":"[20] L. Valiant, \u201cA theory of the learnable,\u201d Commun. ACM, vol.27, no.11, pp.1134-1142, 1984. 10.1145\/1968.1972","DOI":"10.1145\/1968.1972"},{"key":"21","doi-asserted-by":"crossref","unstructured":"[21] H. Yamasaki and T. Shoudai, \u201cMining of frequent externally extensible outerplanar graph patterns,\u201d Proc. 7th International Conference on Machine Learning and Applications, pp.871-876, 2008. 10.1109\/icmla.2008.98","DOI":"10.1109\/ICMLA.2008.98"},{"key":"22","doi-asserted-by":"publisher","unstructured":"[22] H. Yamasaki, Y. Sasaki, T. Shoudai, T. Uchida, and Y. Suzuki, \u201cLearning block-preserving graph patterns and its application to data mining,\u201d Mach. Learn., vol.76, no.1, pp.137-173, 2009. 10.1007\/s10994-009-5115-9","DOI":"10.1007\/s10994-009-5115-9"},{"key":"23","unstructured":"[23] X. Yan and J. Han, \u201cgSpan: Graph-based substructure pattern mining,\u201d Proc. 2002 IEEE International Conference on Data Mining, pp.721-724, 2002. 10.1109\/icdm.2002.1184038"}],"container-title":["IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transfun\/E106.A\/6\/E106.A_2022EAP1052\/_pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,3]],"date-time":"2023-06-03T04:04:58Z","timestamp":1685765098000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transfun\/E106.A\/6\/E106.A_2022EAP1052\/_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,1]]},"references-count":23,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2023]]}},"URL":"https:\/\/doi.org\/10.1587\/transfun.2022eap1052","relation":{},"ISSN":["0916-8508","1745-1337"],"issn-type":[{"value":"0916-8508","type":"print"},{"value":"1745-1337","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6,1]]},"article-number":"2022EAP1052"}}