Complementary Knowledge Compilation Using the Hyper Extension Rule

作     者：NIU Dangdang LIU Lei LYU Shuai XU Yue NIU Dangdang;LIU Lei;LYU Shuai;XU Yue

作者机构：College of Computer Science and Technology Jilin University Key Laboratory of Symbolic Computation and Knowledge Engineering Ministry of Education Jilin University 

出 版 物：《Chinese Journal of Electronics》 (电子学报(英文))

年 卷 期：2019年第28卷第2期

页      面：259-265页

核心收录：

学科分类：08[工学] 0835[工学-软件工程] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：supported by the National Natural Science Foundation of China(No.61300049,No.61502197,No.61503044,No.61763003) the Natural Science Research Foundation of Jilin Province of China(No.20180101053JC) 

主　　题：Knowledge compilation Extension rule Hyper extension rule Compilation language Each pair contains complementary literals(EPCCL) theory 

摘      要：We introduce the concept of Complementary formula(COMF), which is a new and non-equivalent way for Knowledge compilation(KC). Based on the Hyper extension rule(HER) which is an expansion of Extension rule(ER), we design a compilation algorithm which can formula compile each Conjunctive normal form(CNF)formula to complementary Fully complementary connected diagram(c-FCCD), named as C2C(CNF formula to cFCCD). Theoretically, c-FCCD is a kind of complementary formulae of the input formulae and can support all queries and partial transformations in KC map. Experimentally,C2C is competitive with the EPCCL compilers KCER,C2E, UKCHER, DKCHER and IKCHER.