Department of Applied Mathematics & Physics, Kyoto Univiversity

Technical Report #99009 (April, 1999)

Ordered Binary Decision Diagrams as Knowledge-Bases
by Takashi Horiyama and Toshihide Ibaraki

We propose to make use of ordered binary decision diagrams (OBDDs) as a means of realizing knowledge-bases. We show that the OBDD-based representation is more efficient and suitable in some cases, compared with the traditional CNF-based and/or model-based representations from the view point of space requirement. We then consider two recognition problems of OBDDs, and present polynomial time algorithms for testing whether a given OBDD represents a unate Boolean function, and whether it represents a Horn function.