| Presentation | 2005-03-18 Horn Functions with Single Two-negated Term Naoki KAWAMURA, Shigeki IWATA, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | A Horn function is a Boolean function where each of its prime implicants contains at most one negative literal. A class of Boolean functions is considered where a single term containing two negative literals is added (logically or-ed) to a Horn function. We show that the function does not contain any prime implicant having three negative literals. We also show that if two terms having two negative literals are added to a Horn function then it may have many prime implicants containing three negative literals. We show that the tautology problem for the considered class of Boolean functions given in disjunctive normal form is P-complete. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Boolean functions / Horn functions / prime implicants / P-complete |
| Paper # | COMP2004-77 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2005/3/11(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) | Horn Functions with Single Two-negated Term |
| Sub Title (in English) | |
| Keyword(1) | Boolean functions |
| Keyword(2) | Horn functions |
| Keyword(3) | prime implicants |
| Keyword(4) | P-complete |
| 1st Author's Name | Naoki KAWAMURA |
| 1st Author's Affiliation | Department of Comuputer Science, The University of Electro-Communications() |
| 2nd Author's Name | Shigeki IWATA |
| 2nd Author's Affiliation | Department of Comuputer Science, The University of Electro-Communications |
| Date | 2005-03-18 |
| Paper # | COMP2004-77 |
| Volume (vol) | vol.104 |
| Number (no) | 743 |
| Page | pp.pp.- |
| #Pages | 5 |
| Date of Issue | |