2014/10/24 by Yong Lai, Lai, Yong, Dayou Liu +3
Computer Science · #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #cs.AI
paper · pdf · doi:10.48550/arxiv.1410.6671
7 pages, 6 figures
arxiv created 2014/10/24 · arxiv updated 2014/10/27
This paper augments OBDD with conjunctive decomposition to propose a generalization called OBDD[\wedge]. By imposing reducedness and the finest \wedge-decomposition bounded by integer i (\wedge_\widehati-decomposition) on OBDD[\wedge], we identify a family of canonical languages called ROBDD[\wedge_\widehati], where ROBDD[\wedge_\widehat0] is equivalent to ROBDD. We show that the succinctness of ROBDD[\wedge_\widehati] is strictly increasing when i increases. We introduce a new time-efficiency criterion called rapidity which reflects that exponential operations may be preferable if the language can be exponentially more succinct, and show that: the rapidity of each operation on ROBDD[\wedge_\widehati] is increasing when i increases; particularly, the rapidity of some operations (e.g., conjoining) is strictly increasing. Finally, our empirical results show that: a) the size of ROBDD[\wedge_\widehati] is normally not larger than that of the equivalent \ROBDDC\widehati+1; b) conjoining two ROBDD[\wedge_\widehat1]s is more efficient than conjoining two ROBDD[\wedge_\widehat0]s in most cases, where the former is NP-hard but the latter is in P; and c) the space-efficiency of ROBDD[\wedge_\widehat∞] is comparable with that of d-DNNF and that of another canonical generalization of \ROBDD called SDD.