{"created":"2023-05-15T11:55:16.505430+00:00","id":129,"links":{},"metadata":{"_buckets":{"deposit":"efd3fbe0-01b5-4a5a-a984-c68f48cd1ace"},"_deposit":{"created_by":3,"id":"129","owners":[3],"pid":{"revision_id":0,"type":"depid","value":"129"},"status":"published"},"_oai":{"id":"oai:kyutech.repo.nii.ac.jp:00000129","sets":["8:24"]},"author_link":["597"],"item_21_biblio_info_6":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicIssueDates":{"bibliographicIssueDate":"2005-12-02","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"1","bibliographicPageEnd":"94","bibliographicPageStart":"84","bibliographicVolumeNumber":"348","bibliographic_titles":[{"bibliographic_title":"Theoretical Computer Science"}]}]},"item_21_description_4":{"attribute_name":"抄録","attribute_value_mlt":[{"subitem_description":"A conjunctive query problem is a problem to determine whether or not a tuple belongsto the answer of a conjunctive query over a database. In this paper, a tuple,a conjunctive query and a database in relational database theory are regarded as aground atom, a nonrecursive function-free definite clause and a finite set of groundatoms, respectively, in inductive logic programming terminology. An acyclic conjunctivequery problem is a conjunctive query problem with acyclicity. Concernedwith the acyclic conjunctive query problem, in this paper, we present the hardnessresults of predicting acyclic conjunctive queries from an instance with a j-databaseof which predicate symbol is at most j-ary. Also we deal with two kinds of instances,a simple instance as a set of ground atoms and an extended instance as aset of pairs of a ground atom and a description. We mainly show that, from both asimple and an extended instances, acyclic conjunctive queries are not polynomialtimepredictable with j-databases (j ≥ 3) under the cryptographic assumptions,and predicting acyclic conjunctive queries with 2-databases is as hard as predictingDNF formulas. Hence, the acyclic conjunctive queries become a natural examplethat the equivalence between subsumption-efficiency and efficient pac-learnabilityfrom both a simple and an extended instances collapses.","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.tcs.2005.09.006","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/03043975"}],"subitem_relation_type_id":{"subitem_relation_type_id_text":"http://www.sciencedirect.com/science/journal/03043975","subitem_relation_type_select":"URI"}}]},"item_21_rights_13":{"attribute_name":"権利","attribute_value_mlt":[{"subitem_rights":"Copyright (c) 2005 Elsevier B.V."}]},"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":"0304-3975","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":[{},{},{},{}]}]},"item_files":{"attribute_name":"ファイル情報","attribute_type":"file","attribute_value_mlt":[{"accessrole":"open_date","date":[{"dateType":"Available","dateValue":"2007-11-20"}],"displaytype":"detail","filename":"j.tcs.2005.09.006.pdf","filesize":[{"value":"172.6 kB"}],"format":"application/pdf","licensetype":"license_note","mimetype":"application/pdf","url":{"label":"j.tcs.2005.09.006.pdf","url":"https://kyutech.repo.nii.ac.jp/record/129/files/j.tcs.2005.09.006.pdf"},"version_id":"0996a0dc-d7c9-4183-82f2-b3bdcbc0add7"}]},"item_keyword":{"attribute_name":"キーワード","attribute_value_mlt":[{"subitem_subject":"acyclic conjunctive query","subitem_subject_scheme":"Other"},{"subitem_subject":"inductive logic programming","subitem_subject_scheme":"Other"},{"subitem_subject":"prediction","subitem_subject_scheme":"Other"},{"subitem_subject":"prediction-preserving reduction","subitem_subject_scheme":"Other"},{"subitem_subject":"subsumption","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":"Prediction-hardness of acyclic conjunctive queries","item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"Prediction-hardness of acyclic conjunctive queries"}]},"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":"129","relation_version_is_last":true,"title":["Prediction-hardness of acyclic conjunctive queries"],"weko_creator_id":"3","weko_shared_id":3},"updated":"2023-10-25T06:26:53.847396+00:00"}