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.