知识编译中的SDD构建及其复杂度研究  

Research on Construction and Complexity ofSDD in Knowledge Compilation

作　　者：梁建华 杨文忠[2] 赵宇 LIANG Jianhua;YANG Wenzhong;ZHAO Yu(Ministry of Basic Medical Education,Dazhou Vocational College of Chinese Medicine,Dazhou Sichuan 635000,China;School of computer science and technology,Xinjiang University,Urumqi 830046,China;Fifth Military Represent Office of Chongqing District,Chongqing 404000,China)

机构地区：[1]达州中医药职业学院基础医学教育部,四川达州635000 [2]新疆大学信息科学与技术学院,乌鲁木齐830046 [3]驻重庆地区第五军代室,重庆404000

出　　处：《人工智能科学与工程》2024年第4期11-20,共10页ARTIFICIAL INTELLIGENCE SCIENCE AND ENGINEERING

基　　金：国家自然科学基金项目(62262065)。

摘　　要：本文针对知识编译中的句子决策图(SDD)进行了研究。首先,阐述了关于句子决策图的基本概念及其相关技术。然后,在此基础上提出了一般SDD的自下而上的构建方法。同时,算法还可选地压缩每个划分,以返回压缩后的SDD,并对未压缩SDD和规范、压缩SDD的Apply函数的复杂度进行了深入研究。理论研究表明:前者支持多项式时间Apply函数,后者具有指数级时间Apply函数的特性。最后,实验结果表明:尽管未压缩SDD的Apply函数具有多项式时间复杂度,但规范、压缩SDD的Apply函数能得到比未压缩SDD的Apply函数以及其他先进SDD构建方法更小的SDD和更短的编译时间。This paper focus on the Sentential Decision Diagram(SDD)within the context of knowledge compilation.Specifically,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 compresses 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 experimental results show that although the Apply function of uncompressed SDD has polynomial time complexity,the Apply function of normalized and compressed SDD can obtain smaller SDD size and less compilation time than the Apply function of uncompressed SDD and other advanced SDD construction methods.

关 键 词：人工智能 知识编译 句子决策图 V形树 合取/析取范式 规范性 复杂度 编译时间 

分 类 号：TP301[自动化与计算机技术—计算机系统结构] TP181[自动化与计算机技术—计算机科学与技术]