WEKO3
アイテム
{"_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": ["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": "", "affiliationNameLang": "ja"}]}], "creatorNames": [{"creatorName": "Hirata, Kouichi", "creatorNameLang": "en"}, {"creatorName": "平田, 耕一", "creatorNameLang": "ja"}, {"creatorName": "ヒラタ, コウイチ", "creatorNameLang": "ja-Kana"}], "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"}]}, {"creatorNames": [{"creatorName": "Yamada, Keizo"}], "nameIdentifiers": [{"nameIdentifier": "619", "nameIdentifierScheme": "WEKO"}]}, {"creatorNames": [{"creatorName": "Harao, Masateru"}], "nameIdentifiers": [{"nameIdentifier": "620", "nameIdentifierScheme": "WEKO"}]}]}, "item_files": {"attribute_name": "ファイル情報", "attribute_type": "file", "attribute_value_mlt": [{"accessrole": "open_date", "date": [{"dateType": "Available", "dateValue": "2007-11-20"}], "displaytype": "detail", "download_preview_message": "", "file_order": 0, "filename": "j.jsc.2003.09.002.pdf", "filesize": [{"value": "195.0 kB"}], "format": "application/pdf", "future_date_message": "", "is_thumbnail": false, "licensetype": "license_free", "mimetype": "application/pdf", "size": 195000.0, "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"], "permalink_uri": "http://hdl.handle.net/10228/374", "pubdate": {"attribute_name": "公開日", "attribute_value": "2007-11-20"}, "publish_date": "2007-11-20", "publish_status": "0", "recid": "130", "relation": {}, "relation_version_is_last": true, "title": ["Tractable and intractable second-order matching problems"], "weko_shared_id": 3}
Tractable and intractable second-order matching problems
http://hdl.handle.net/10228/374
http://hdl.handle.net/10228/374c651c5cd-c4dc-44b0-b614-16fe40ad8070
名前 / ファイル | ライセンス | アクション |
---|---|---|
j.jsc.2003.09.002.pdf (195.0 kB)
|
|
Item type | 学術雑誌論文 = Journal Article(1) | |||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
公開日 | 2007-11-20 | |||||||||||
資源タイプ | ||||||||||||
資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||||||
資源タイプ | journal article | |||||||||||
タイトル | ||||||||||||
タイトル | Tractable and intractable second-order matching problems | |||||||||||
言語 | ||||||||||||
言語 | eng | |||||||||||
著者 |
平田, 耕一
× 平田, 耕一
WEKO
597
× Yamada, Keizo× Harao, Masateru |
|||||||||||
抄録 | ||||||||||||
内容記述タイプ | Abstract | |||||||||||
内容記述 | 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. | |||||||||||
書誌情報 |
Journal of Symbolic Computation 巻 37, 号 5, p. 611-628, 発行日 2004-05 |
|||||||||||
出版社 | ||||||||||||
出版者 | Elsevier | |||||||||||
DOI | ||||||||||||
関連タイプ | isVersionOf | |||||||||||
識別子タイプ | DOI | |||||||||||
関連識別子 | https://doi.org/10.1016/j.jsc.2003.09.002 | |||||||||||
ISSN | ||||||||||||
収録物識別子タイプ | ISSN | |||||||||||
収録物識別子 | 0747-7171 | |||||||||||
著作権関連情報 | ||||||||||||
権利情報 | Copyright (c) 2003 Elsevier Ltd. | |||||||||||
キーワード | ||||||||||||
主題Scheme | Other | |||||||||||
主題 | Second-order matching problem | |||||||||||
キーワード | ||||||||||||
主題Scheme | Other | |||||||||||
主題 | Second-order unification problem | |||||||||||
キーワード | ||||||||||||
主題Scheme | Other | |||||||||||
主題 | Computational complexity | |||||||||||
出版タイプ | ||||||||||||
出版タイプ | AM | |||||||||||
出版タイプResource | http://purl.org/coar/version/c_ab4af688f83e57aa | |||||||||||
査読の有無 | ||||||||||||
値 | yes | |||||||||||
著者別名 | ||||||||||||
姓名 | Hirata, Kouichi | |||||||||||
言語 | en | |||||||||||
姓名 | 平田, 耕一 | |||||||||||
言語 | ja | |||||||||||
姓名 | ヒラタ, コウイチ | |||||||||||
言語 | ja-Kana | |||||||||||
情報源 | ||||||||||||
識別子タイプ | URI | |||||||||||
関連識別子 | http://www.sciencedirect.com/science/journal/07477171 | |||||||||||
関連名称 | http://www.sciencedirect.com/science/journal/07477171 |