| Presentation | 2004/3/9 Double Horn extensions and restricted Horn extensions of a partially defined Boolean function Masaomi IIDA, Kazuhisa MAKINO, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | 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. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | partially defined Boolean function / extension / Horn function / knowledge base |
| Paper # | COMP2003-86 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2004/3/9(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Double Horn extensions and restricted Horn extensions of a partially defined Boolean function |
| Sub Title (in English) | |
| Keyword(1) | partially defined Boolean function |
| Keyword(2) | extension |
| Keyword(3) | Horn function |
| Keyword(4) | knowledge base |
| 1st Author's Name | Masaomi IIDA |
| 1st Author's Affiliation | Graduate School of Information Science and Engineering, Tokyo Institute of Technology() |
| 2nd Author's Name | Kazuhisa MAKINO |
| 2nd Author's Affiliation | Division of Mathematical Science for Social Systems, Graduate School of Engineering Science, Osaka University |
| Date | 2004/3/9 |
| Paper # | COMP2003-86 |
| Volume (vol) | vol.103 |
| Number (no) | 723 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |