| Presentation | 1995/11/17 Learnability of Ordered Binary Decision Diagrams Kouichi Hirata, Ayumi Shinohara, Satoshi Matsumoto, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | Ordered binary decision diagrams (OBDDs, for short) represent Boolean functions as directed acyclic graphs. In this paper, we investigate the learnability of OBDDs. First, we show that OBDDs representing totally symmetric functions of n variables are polynomial-time learnable with at most n+1 equivalence queries alone, or just n+1 membership queries alone. Also we show that OBDDs representing the conjunction, or disjunction, of literals over n variables are polynomial-time learnable with at most TL equivalence queries alone. Hence, we can conclude that all of them are polynomial-time PAC-learnable with respect to n. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Binary decision diagram / PAC-learning / Exact learning with queries / Algorithmic learning theory |
| Paper # | COMP95-61 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 1995/11/17(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 | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Learnability of Ordered Binary Decision Diagrams |
| Sub Title (in English) | |
| Keyword(1) | Binary decision diagram |
| Keyword(2) | PAC-learning |
| Keyword(3) | Exact learning with queries |
| Keyword(4) | Algorithmic learning theory |
| 1st Author's Name | Kouichi Hirata |
| 1st Author's Affiliation | Department of Artificial Intelligence, Kyushu Institute of Technology() |
| 2nd Author's Name | Ayumi Shinohara |
| 2nd Author's Affiliation | Research Institute of Fundamental Information Science, Kyushu University |
| 3rd Author's Name | Satoshi Matsumoto |
| 3rd Author's Affiliation | Research Institute of Fundamental Information Science, Kyushu University |
| Date | 1995/11/17 |
| Paper # | COMP95-61 |
| Volume (vol) | vol.95 |
| Number (no) | 374 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |