Top-Down Algorithms for Constructing Structured DNNF: Theoretical and Practical Implications

被引：9

作者：

Pipatsrisawat, Knot ^{[1
]}

Darwiche, Adnan ^{[1
]}

机构：

[1] Univ Calif Los Angeles, Dept Comp Sci, Los Angeles, CA 90024 USA

来源：

ECAI 2010 - 19TH EUROPEAN CONFERENCE ON ARTIFICIAL INTELLIGENCE | 2010年 / 215卷

关键词：

D O I：

10.3233/978-1-60750-606-5-3

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

We introduce a top-down compilation algorithm for constructing structured DNNF for any Boolean function. With appropriate restrictions, the algorithm can produce various subsets of DNNF such as deterministic DNNF and OBDD. We derive a size upper bound for structured DNNF based on this algorithm and use the result to generalize similar upper bounds known for several Boolean functions in the case of OBDD. We then discuss two realizations of the algorithm that work on CNF formulas. We show that these algorithms have time and space complexities that are exponential in the treewidth and the dual treewidth of the input.

引用

页码：3 / 8

页数：6

共 14 条

[1] [Anonymous], 2000, SIAM MONOG DISCR MAT, DOI 10.1137/1.9780898719789
[2] BRYANT RE, 1986, IEEE T COMPUT, V35, P677, DOI 10.1109/TC.1986.1676819
[3] Darwiche A, 2009, MODELING AND REASONING WITH BAYESIAN NETWORKS, P1, DOI 10.1017/CBO9780511811357
[4] Darwiche A, 2004, FRONT ARTIF INTEL AP, V110, P328
[5] A knowledge compilation map
Darwiche, A
Marquis, P
[J]. JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH, 2002, 17 : 229 - 264
[6] Dechter R., 2003, Constraint processing
[7] Huang JB, 2005, LECT NOTES COMPUT SC, V3542, P157
[8] Knot Pipatsrisawat, 2010, P AAAI 10 J IN PRESS
[9] MATEESCU R, 2006, P CP 06, V4204, P329
[10] Pipatsrisawat K., 2008, P 23 NAT C ART INT, V1, P517

← 1 2 →