{"created":"2021-03-01T06:15:21.586919+00:00","id":12448,"links":{},"metadata":{"_buckets":{"deposit":"2aea3562-b6cb-4a76-a53b-139db5ced2ea"},"_deposit":{"id":"12448","owners":[],"pid":{"revision_id":0,"type":"depid","value":"12448"},"status":"published"},"_oai":{"id":"oai:soar-ir.repo.nii.ac.jp:00012448","sets":["1221:1222"]},"author_link":["37918","37919"],"item_13_biblio_info_6":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicIssueDates":{"bibliographicIssueDate":"2009","bibliographicIssueDateType":"Issued"},"bibliographicPageEnd":"565","bibliographicPageStart":"554","bibliographicVolumeNumber":"5664","bibliographic_titles":[{"bibliographic_title":"Lecture Notes in Computer Science"}]}]},"item_13_description_19":{"attribute_name":"内容記述","attribute_value_mlt":[{"subitem_description":"Algorithms and Data Structures, 11th International Symposium, WADS 2009, Banff, Canada, August 21-23, 2009.","subitem_description_type":"Other"}]},"item_13_description_20":{"attribute_name":"抄録","attribute_value_mlt":[{"subitem_description":"The following tree pattern matching problem is considered: Given two unordered labeled trees P and T, find all occurrences of P in T. Here P and T are called a pattern tree and a target tree, respectively. We first introduce a new problem called the pseudo-tree pattern matching problem. Then we show two efficient bit-parallel algorithms for the pseudo-tree pattern matching problem. One runs in O(L(P).n.l. [h/w]) time and O(n.l.[h/w]) space, and another one runs in O((L(P).n+h.2(l)).[h.l/W]) time and O((n + h.2(l)).[h.l/W]) space, where n is the number of nodes in T, h and l are the height of P and the number of leaves of P, respectively, and W is the length of a computer-word. The parameter L(P), called a recursive level of P, is defined to be the number of occurrences of the same label on a path from the root to a leaf. Hence we have L(P) <= h. Finally, we give an algorithm to extract all occurrences from pseud-occurrences in O(n.L(P).l(3/2)) time and O(n.L(P).l) space.","subitem_description_type":"Abstract"}]},"item_13_description_30":{"attribute_name":"資源タイプ（コンテンツの種類）","attribute_value_mlt":[{"subitem_description":"Article","subitem_description_type":"Other"}]},"item_13_description_5":{"attribute_name":"引用","attribute_value_mlt":[{"subitem_description":"Lecture Notes in Computer Science. 5664:554-565 (2009)","subitem_description_type":"Other"}]},"item_13_link_3":{"attribute_name":"信州大学研究者総覧へのリンク","attribute_value_mlt":[{"subitem_link_text":"Yamamoto, Hiroaki","subitem_link_url":"http://soar-rd.shinshu-u.ac.jp/profile/ja.ONfpOCSh.html"}]},"item_13_publisher_4":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"SPRINGER VERLAG"}]},"item_13_relation_48":{"attribute_name":"DOI","attribute_value_mlt":[{"subitem_relation_name":[{"subitem_relation_name_text":"10.1007/978-3-642-03367-4_48"}],"subitem_relation_type_id":{"subitem_relation_type_id_text":"https://doi.org/10.1007/978-3-642-03367-4_48","subitem_relation_type_select":"DOI"}}]},"item_13_rights_62":{"attribute_name":"権利","attribute_value_mlt":[{"subitem_rights":"Copyright© 2009 Springer. The original publication is available at www.springerlink.com"}]},"item_13_source_id_35":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"0302-9743","subitem_source_identifier_type":"ISSN"}]},"item_13_source_id_40":{"attribute_name":"書誌レコードID","attribute_value_mlt":[{"subitem_source_identifier":"AA0071599X","subitem_source_identifier_type":"NCID"}]},"item_1627890897769":{"attribute_name":"出版タイプ","attribute_value_mlt":[{"subitem_version_resource":"http://purl.org/coar/version/c_ab4af688f83e57aa","subitem_version_type":"AM"}]},"item_creator":{"attribute_name":"著者","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Yamamoto,  Hiroaki"}],"nameIdentifiers":[{"nameIdentifier":"37918","nameIdentifierScheme":"WEKO"}]},{"creatorNames":[{"creatorName":"Takenouchi,  Daichi"}],"nameIdentifiers":[{"nameIdentifier":"37919","nameIdentifierScheme":"WEKO"}]}]},"item_files":{"attribute_name":"ファイル情報","attribute_type":"file","attribute_value_mlt":[{"accessrole":"open_date","date":[{"dateType":"Available","dateValue":"2015-09-28"}],"displaytype":"detail","filename":"Bit-Parallel_Tree_Pattern_Matching_Algorithms.pdf","filesize":[{"value":"161.9 kB"}],"format":"application/pdf","licensetype":"license_note","mimetype":"application/pdf","url":{"label":"Bit-Parallel_Tree_Pattern_Matching_Algorithms.pdf","url":"https://soar-ir.repo.nii.ac.jp/record/12448/files/Bit-Parallel_Tree_Pattern_Matching_Algorithms.pdf"},"version_id":"2c03c2da-0197-40cb-9114-4496d239249b"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"eng"}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourcetype":"conference paper","resourceuri":"http://purl.org/coar/resource_type/c_5794"}]},"item_title":"Bit-Parallel Tree Pattern Matching Algorithms for Unordered Labeled Trees","item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"Bit-Parallel Tree Pattern Matching Algorithms for Unordered Labeled Trees","subitem_title_language":"en"}]},"item_type_id":"13","owner":"1","path":["1222"],"pubdate":{"attribute_name":"PubDate","attribute_value":"2012-03-01"},"publish_date":"2012-03-01","publish_status":"0","recid":"12448","relation_version_is_last":true,"title":["Bit-Parallel Tree Pattern Matching Algorithms for Unordered Labeled Trees"],"weko_creator_id":"1","weko_shared_id":-1},"updated":"2022-12-14T04:07:29.650624+00:00"}