Research on Construction and Complexity of SDD in Knowledge Compilation
This paper focus on the Sentential Decision Diagram(SDD)within the context of knowledge compilation.Specifical-ly,it begins by outlining the fundamental concepts of sentential decision diagrams along with their associated techniques.On this basis,the bottom-up construction method of general SDD is proposed.At the same time,the algorithm optionally com-presses each partition to return the compressed SDD.This study provides an in-depth analysis of the complexity of the Apply functions for both uncompressed SDD and normalized,compressed SDD.Theoretical research shows that the former supports polynomial time Apply function,while the latter has the characteristics of exponential time Apply function.The final experi-mental results show that although the Apply function of uncompressed SDD has polynomial time complexity,the Apply func-tion of normalized and compressed SDD can obtain smaller SDD size and less compilation time than the Apply function of un-compressed SDD and other advanced SDD construction methods.
artificial intelligenceknowledge compilationsentential decision diagramV-treeconjunctive/disjunctive normal formnormalizationcomplexitycompilation time
NETL
NSTL
万方数据
