| 講演名 | 2004/3/9 部分定義ブール関数のダブルホーン拡張および限定ホーン拡張 飯田 雅臣, 牧野 和久, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 本稿では,与えられた部分定義プール関数(pdBf)についてダブルホーン,限定ホーンによる拡張を見つける問題を考える.このような問題を解くことによって,生成規則知識ベースを単純化することができる.また,一般に命題推論の計算動作の改良にもつながる.このとき,単純化の中でも(i)知識ベースサイズの最小化と(ii)推論の計算が効率的に行われるように生成規則の表現を変えることが重要である.本稿では(i),(ii)を達成するダブルホーン拡張と限定ホーン拡張について,その充足解の数において極小な拡張を多項式時間に求める方法を議論する.一方,それぞれの最小の拡張を求める問題がNP困難であることを示す. |
| 抄録(英) | We study the task of finding double Horn extensions and restricted Horn extensions of a given partially defined Boolean function (pdBf). Finding these extensions enable as to simplify production rules of knowledge-based systems and generally improve the calculation of deduction. In particular, it is significant for the simplification (i) to minimize the size of the knowledge base and (ii) to modify representations in the knowledge base in order to calculate deduction efficiently. In this paper we discuss the method for finding a minimal double Horn extension and a minimal restricted Horn extension which attain (i) and (ii) in polynomial time. We also show the problems of finding a minimum double Horn extension and of finding a minimum restricted Horn extension, are both NP-hard. |
| キーワード(和) | 部分定義プール関数 / 拡張 / ホーン関数 / 知識ベース |
| キーワード(英) | partially defined Boolean function / extension / Horn function / knowledge base |
| 資料番号 | COMP2003-86 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2004/3/9(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 部分定義ブール関数のダブルホーン拡張および限定ホーン拡張 |
| サブタイトル（和） | |
| タイトル（英） | Double Horn extensions and restricted Horn extensions of a partially defined Boolean function |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 部分定義プール関数 / partially defined Boolean function |
| キーワード(2)（和/英） | 拡張 / extension |
| キーワード(3)（和/英） | ホーン関数 / Horn function |
| キーワード(4)（和/英） | 知識ベース / knowledge base |
| 第 1 著者 氏名（和/英） | 飯田 雅臣 / Masaomi IIDA |
| 第 1 著者 所属（和/英） | 東京工業大学大学院情報理工学研究科 Graduate School of Information Science and Engineering, Tokyo Institute of Technology |
| 第 2 著者 氏名（和/英） | 牧野 和久 / Kazuhisa MAKINO |
| 第 2 著者 所属（和/英） | 大阪大学大学院基礎工学研究科 Division of Mathematical Science for Social Systems, Graduate School of Engineering Science, Osaka University |
| 発表年月日 | 2004/3/9 |
| 資料番号 | COMP2003-86 |
| 巻番号（vol） | vol.103 |
| 号番号（no） | 723 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |