{"created":"2023-05-15T11:55:16.546019+00:00","id":130,"links":{},"metadata":{"_buckets":{"deposit":"87673e75-7d2f-4ad9-b5f4-1cb0f2db5482"},"_deposit":{"created_by":3,"id":"130","owners":[3],"pid":{"revision_id":0,"type":"depid","value":"130"},"status":"published"},"_oai":{"id":"oai:kyutech.repo.nii.ac.jp:00000130","sets":["8:24"]},"author_link":["619","620","597"],"item_21_biblio_info_6":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicIssueDates":{"bibliographicIssueDate":"2004-05","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"5","bibliographicPageEnd":"628","bibliographicPageStart":"611","bibliographicVolumeNumber":"37","bibliographic_titles":[{"bibliographic_title":"Journal of Symbolic Computation"}]}]},"item_21_description_4":{"attribute_name":"抄録","attribute_value_mlt":[{"subitem_description":"The second-order matching problem is to determine whether or not afirst-order term without variables is an instance of a second-order termthat is allowed to contain not only individual variables but also functionvariables. It is well-known that the second-order matching problemis NP-complete in general. In this paper, we first introduce the severalrestrictions for the second-order matching problems, such as the boundednumber, arity and occurrence of function variables, ground that containsno individual variables, flat that contains no function constants, and predicatethat no function variable occurs in the terms of arguments of eachfunction variable. By combining the above restrictions, we give the sharpseparations of tractable second-order matching problems from intractableones. Finally, we compare them with the separations of decidable secondorderunification problems from undecidable ones.","subitem_description_type":"Abstract"}]},"item_21_description_60":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"subitem_description":"Journal Article","subitem_description_type":"Other"}]},"item_21_full_name_3":{"attribute_name":"著者別名","attribute_value_mlt":[{"affiliations":[{"affiliationNames":[{"affiliationName":"","lang":"ja"}],"nameIdentifiers":[]}],"familyNames":[{"familyName":"Hirata","familyNameLang":"en"},{"familyName":"平田","familyNameLang":"ja"},{"familyName":"ヒラタ","familyNameLang":"ja-Kana"}],"givenNames":[{"givenName":"Kouichi","givenNameLang":"en"},{"givenName":"耕一","givenNameLang":"ja"},{"givenName":"コウイチ","givenNameLang":"ja-Kana"}],"nameIdentifiers":[{"nameIdentifier":"597","nameIdentifierScheme":"WEKO"},{"nameIdentifier":"20274558","nameIdentifierScheme":"e-Rad","nameIdentifierURI":"https://nrid.nii.ac.jp/ja/nrid/1000020274558"},{"nameIdentifier":"55730619500","nameIdentifierScheme":"Scopus著者ID","nameIdentifierURI":"https://www.scopus.com/authid/detail.uri?authorId=55730619500"},{"nameIdentifier":"189","nameIdentifierScheme":"九工大研究者情報","nameIdentifierURI":"https://hyokadb02.jimu.kyutech.ac.jp/html/189_ja.html"}],"names":[{"name":"Hirata, Kouichi","nameLang":"en"},{"name":"平田, 耕一","nameLang":"ja"},{"name":"ヒラタ, コウイチ","nameLang":"ja-Kana"}]}]},"item_21_publisher_7":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"Elsevier"}]},"item_21_relation_12":{"attribute_name":"DOI","attribute_value_mlt":[{"subitem_relation_type":"isVersionOf","subitem_relation_type_id":{"subitem_relation_type_id_text":"https://doi.org/10.1016/j.jsc.2003.09.002","subitem_relation_type_select":"DOI"}}]},"item_21_relation_14":{"attribute_name":"情報源","attribute_value_mlt":[{"subitem_relation_name":[{"subitem_relation_name_text":"http://www.sciencedirect.com/science/journal/07477171"}],"subitem_relation_type_id":{"subitem_relation_type_id_text":"http://www.sciencedirect.com/science/journal/07477171","subitem_relation_type_select":"URI"}}]},"item_21_rights_13":{"attribute_name":"権利","attribute_value_mlt":[{"subitem_rights":"Copyright (c) 2003 Elsevier Ltd."}]},"item_21_select_59":{"attribute_name":"査読の有無","attribute_value_mlt":[{"subitem_select_item":"yes"}]},"item_21_source_id_8":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"0747-7171","subitem_source_identifier_type":"ISSN"}]},"item_21_text_36":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"Department of Artificial Intelligence, Kyushu Institute of Technology, Kawazu 680-4, Iizuka 820-8502, Japan"}]},"item_21_version_type_58":{"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":[{"creatorAffiliations":[{"affiliationNameIdentifiers":[],"affiliationNames":[{"affiliationName":""}]}],"creatorNames":[{"creatorName":"Hirata, Kouichi","creatorNameLang":"en"},{"creatorName":"平田, 耕一","creatorNameLang":"ja"},{"creatorName":"ヒラタ, コウイチ","creatorNameLang":"ja-Kana"}],"familyNames":[{},{},{}],"givenNames":[{},{},{}],"nameIdentifiers":[{},{},{},{}]},{"creatorNames":[{"creatorName":"Yamada, Keizo"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Harao, Masateru"}],"nameIdentifiers":[{}]}]},"item_files":{"attribute_name":"ファイル情報","attribute_type":"file","attribute_value_mlt":[{"accessrole":"open_date","date":[{"dateType":"Available","dateValue":"2007-11-20"}],"displaytype":"detail","filename":"j.jsc.2003.09.002.pdf","filesize":[{"value":"195.0 kB"}],"format":"application/pdf","licensetype":"license_note","mimetype":"application/pdf","url":{"label":"j.jsc.2003.09.002.pdf","url":"https://kyutech.repo.nii.ac.jp/record/130/files/j.jsc.2003.09.002.pdf"},"version_id":"f46ea083-6677-4a02-90dd-fc2efba8afe1"}]},"item_keyword":{"attribute_name":"キーワード","attribute_value_mlt":[{"subitem_subject":"Second-order matching problem","subitem_subject_scheme":"Other"},{"subitem_subject":"Second-order unification problem","subitem_subject_scheme":"Other"},{"subitem_subject":"Computational complexity","subitem_subject_scheme":"Other"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"eng"}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourcetype":"journal article","resourceuri":"http://purl.org/coar/resource_type/c_6501"}]},"item_title":"Tractable and intractable second-order matching problems","item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"Tractable and intractable second-order matching problems"}]},"item_type_id":"21","owner":"3","path":["24"],"pubdate":{"attribute_name":"公開日","attribute_value":"2007-11-20"},"publish_date":"2007-11-20","publish_status":"0","recid":"130","relation_version_is_last":true,"title":["Tractable and intractable second-order matching problems"],"weko_creator_id":"3","weko_shared_id":3},"updated":"2023-10-25T06:26:53.555751+00:00"}