{"_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": ["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) \u003c= 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_select_64": {"attribute_name": "著者版フラグ", "attribute_value_mlt": [{"subitem_select_item": "author"}]}, "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_39": {"attribute_name": "NII 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", "download_preview_message": "", "file_order": 0, "filename": "Bit-Parallel_Tree_Pattern_Matching_Algorithms.pdf", "filesize": [{"value": "161.9 kB"}], "format": "application/pdf", "future_date_message": "", "is_thumbnail": false, "licensetype": "license_note", "mimetype": "application/pdf", "size": 161900.0, "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"], "permalink_uri": "http://hdl.handle.net/10091/13658", "pubdate": {"attribute_name": "PubDate", "attribute_value": "2012-03-01"}, "publish_date": "2012-03-01", "publish_status": "0", "recid": "12448", "relation": {}, "relation_version_is_last": true, "title": ["Bit-Parallel Tree Pattern Matching Algorithms for Unordered Labeled Trees"], "weko_shared_id": -1}