Open AccessKnowledge Compilation Methods Based on the Clausal Relevance and Extension Rule
Author(s) -
NIU Dangdang,
LIU Lei,
LYU Shuai
Publication year - 2018
Publication title -
chinese journal of electronics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.267
H-Index - 25
eISSN - 2075-5597
pISSN - 1022-4653
DOI - 10.1049/cje.2018.04.006
Subject(s) - extension (predicate logic) , relevance (law) , computer science , natural language processing , programming language , political science , law
We introduce the concepts of Relevancematrix (RM) and Relevance‐set (RS). And we construct the association between RM and the Knowledge compilation (KC) methods based on Extension rule (ER). Based on the basic parameters of RS and the relationship between RM and the KC methods based on ER, we design two efficient heuristics, called M2S (maximum sum of elements in RS and sum of literals in RS) and MNE (minimum number of maximum terms not extended by RS). Both of above heuristics intend to find the minimum set of maximum terms which cannot be extended by RS. Furthermore, we apply M2S and MNE on KCER. M2S_KCER (KCER with M2S) and MNE_KCER (KCER with MNE) are designed and implemented based on M2S and MNE, respectively. Experimentally, for the SAT instances with random lengths of clauses, M2S_KCER and MNE_KCER can improve the efficiency and quality of KCER sharply, and they are two best KC algorithms of EPCCL (each pair contains complementary literal) theory in all KC algorithms based on KCER.