×

zbMATH — the first resource for mathematics

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

MSC:
68T30 Knowledge representation
Software:
ROBDD
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Akers, S.B., Binary decision diagrams, IEEE trans. comput., C-27, 509-516, (1978) · Zbl 0377.94038
[2] Brace, K.S.; Rundell, R.L.; Bryant, R.E., Efficient implementation of a BDD package, (), 40-45
[3] Brayton, R.K.; Hachtel, G.D.; Sangiovanni-Vincentelli, A.L., Multilevel logic synthesis, Proc. IEEE, 78, 2, 264-300, (1990)
[4] Bryant, R.E., Graph-based algorithms for Boolean function manipulation, IEEE trans. comput., C-35, 677-691, (1986) · Zbl 0593.94022
[5] Bryant, R.E., On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication, IEEE trans. comput., 40, 205-213, (1991) · Zbl 1220.68060
[6] Buch, P.; Narayan, A.; Newton, A.R.; Sangiovanni-Vincentelli, A., Logic synthesis for large pass transistor circuits, (), 663-670
[7] Burch, J.R.; Clarke, E.M.; McMillan, K.L.; Dill, D.L., Sequential circuit verification using symbolic model checking, (), 46-51
[8] Coudert, O., Doing two-level logic minimization 100 times faster, (), 112-118 · Zbl 0858.94035
[9] Dechter, R.; Pearl, J., Structure identification in relational data, Artificial intelligence, 58, 237-270, (1992) · Zbl 0782.68095
[10] Dowling, W.F.; Gallier, J.H., Linear time algorithms for testing the satisfiability of Horn formula, J. logic programming, 3, 267-284, (1984) · Zbl 0593.68062
[11] Drechsler, R.; Drechsler, N., W G√ľnther, fast exact minimization of bdds, (), 200-205
[12] Eiter, T.; Gottlob, G., The complexity of logic-based abduction, J. ACM, 42, 3-42, (1995) · Zbl 0886.68121
[13] Glymour, C.; Scheines, R.; Spirtes, P.; Kelly, K., Discovering causal structure, (1987), Academic Press Orlando, FL
[14] Hayase, K.; Imai, H., OBDDs of a monotone function and of its implicants, (), 136-145 · Zbl 0912.68002
[15] Horiyama, T.; Ibaraki, T., Reasoning with ordered binary decision diagrams, (), 120-131 · Zbl 1044.68813
[16] Horiyama, T.; Ibaraki, T., Translation among CNFs, characteristic models and ordered binary decision diagrams, (), 231-243 · Zbl 1077.68661
[17] Kautz, H.A.; Kearns, M.J.; Selman, B., Reasoning with characteristic models, (), 34-39
[18] Kautz, H.A.; Kearns, M.J.; Selman, B., Horn approximations of empirical data, Artificial intelligence, 74, 129-245, (1995) · Zbl 1014.03514
[19] Kautz, H.A.; Selman, B., An empirical evaluation of knowledge compilation by theory approximation, (), 155-161
[20] Kavvadias, D.; Papadimitriou, C.; Sideri, M., On Horn envelopes and hypergraph transversals, (), 399-405 · Zbl 0925.03036
[21] Khardon, R.; Roth, D., Reasoning with models, Artificial intelligence, 87, 187-213, (1996)
[22] Lai, Y.T.; Pan, K.R.; Pedram, M., OBDD-based functional decomposition: algorithms and implementation, IEEE trans. CAD, 15, 8, 977-990, (1996)
[23] Madre, J.C.; Coudert, O., A logically complete reasoning maintenance system based on a logical constraint solver, (), 294-299 · Zbl 0747.68072
[24] McCarthy, J.; Hayes, P.J., Some philosophical problems from the standpoint of artificial intelligence, () · Zbl 0226.68044
[25] Minato, S.; Ishiura, N.; Yajima, S., Shared binary decision diagram with attributed edges for efficient Boolean function manipulation, (), 52-57
[26] Ravi, K.; McMillan, K.L.; Shiple, T.R.; Somenzi, F., Approximation and decomposition of binary decision diagrams, (), 445-450
[27] Takahashi, N.; Ishiura, N.; Yajima, S., Fault simulation for multiple faults using BDD representation of fault sets, (), 550-553
[28] Takenaga, Y., Theoretical studies on memory-based parallel computation and ordered binary decision diagrams, ph.D. thesis, (1994), Graduate School of Engineering, Kyoto University Kyoto, Japan
[29] Valiant, L.G., A theory of the learnable, Comm. ACM, 27, 11, 1134-1142, (1984) · Zbl 0587.68077
[30] Yang, C.; Ciesielski, M.; Singhal, V., BDS: A BDD-based logic optimization system, (), 92-97
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.