Knowledge Compilation Methods Based on the Clausal Relevance and Extension Rule

NIU Dangdang; LIU Lei; LYU Shuai

doi:10.1049/cje.2018.04.006

Volume 27 Issue 5

Turn off MathJax

Article Contents

Article Navigation > Chinese Journal of Electronics > 2018 > 27(5): 1037-1042

NIU Dangdang, LIU Lei, LYU Shuai, “Knowledge Compilation Methods Based on the Clausal Relevance and Extension Rule,” Chinese Journal of Electronics, vol. 27, no. 5, pp. 1037-1042, 2018, doi: 10.1049/cje.2018.04.006

Citation:

NIU Dangdang, LIU Lei, LYU Shuai, “Knowledge Compilation Methods Based on the Clausal Relevance and Extension Rule,” Chinese Journal of Electronics, vol. 27, no. 5, pp. 1037-1042, 2018, doi: 10.1049/cje.2018.04.006

Citation:

PDF( 241 KB)

Knowledge Compilation Methods Based on the Clausal Relevance and Extension Rule

doi: 10.1049/cje.2018.04.006

1.
College of Computer Science and Technology, Jilin University, Changchun 130012, China;
2.
Key Laboratory of Symbolic Computation and Knowledge Engineering(Jilin University), Ministry of Education, Changchun 130012, China

Funds: This work is supported by the National Natural Science Foundation of China (No.61300049, No.61502197, No.61503044, No.61763003) and the Natural Science Research Foundation of Jilin Province of China (No.20180101053JC).

More Information

Corresponding author: LYU Shuai (corresponding author) was born in 1981. He received the M.S. and Ph.D. degrees in computer software and theory from College of Computer Science and Technology, Jilin University, China in 2007 and 2010, respectively. He is currently an associate professor in College of Computer Science and Technology, Jilin University, China. His research interests include artificial intelligence, automated reasoning and intelligent planning. (Email:lus@jlu.edu.cn)
Received Date: 2016-03-01
Rev Recd Date: 2016-11-08
Publish Date: 2018-09-10

Abstract

Abstract

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.
- Extension rule,
- Knowledge compilation,
- Clausal relevance,
- Heuristic strategy

FullText(HTML)

References(17)

References

A. Darwiche and P. Marquis, “A knowledge compilation map”, Journal of Artificial Intelligence Research, Vol.17, pp.229-264, 2002.

H. Fargier, P. Marquis and A. Niveau, “Towards a knowledge compilation map for heterogeneous representation languages”, Proc. of the 23rd International Joint Conference on Artificial Intelligence, Beijing, China, pp.877-883, 2013.

H. Fargier, P. Marquis, A. Niveau and N. Schmidt, “A knowledge compilation map for ordered real-valued decision diagrams”, Proc. of the 28th National Conference on Artificial Intelligence, Québec, Canada, pp.1049-1055, 2014.

H. Fargier and P. Marquis, “Disjunctive closures for knowledge compilation”, Artificial Intelligence, Vol.216, pp.129-162, 2014.

S.M. Kazemi and D. Poole, “Knowledge compilation for lifted probabilistic inference: Compiling to a low-level language”, Proc. the 15th International Conference on Principles of Knowledge Representation and Reasoning, Cape Town, South Africa, pp.561-564, 2016.

Y. Lai, D.Y. Liu and S.S. Wang, “Reduced ordered binary decision diagram with implied literals: A new knowledge compilation approach”, Knowledge and Information Systems, Vol.35, No.3, pp.665-712, 2013.

H. Lin, J.G. Sun and Y.M. Zhang, “Theorem proving based on the extension rule”, Journal of Automated Reasoning, Vol.31, No.1, pp.11-21, 2003.

H. Lin and J.G. Sun, “Knowledge compilation using the extension rule”, Journal of Automated Reasoning, Vol.32, No.2, pp.93-102, 2004.

D.Y. Liu, Y. Lai and H. Lin, “C2E: An EPCCL compiler with good performance”, Chinese Journal of Computer, Vol.36, No.6, pp.1254-1260, 2013.

L. Liu, D.D. Niu, Z. Li and S. YU, “Dynamic online reasoning algorithm based on the hyper extension rule”, Journal of Harbin Engineering University, Vol.36, No.12, pp.1614-1619, 2015.

L. Liu, D.D. Niu and S. YU, “Knowledge compilation methods based on the hyper extension rule”, Chinese Journal of Computers, Vol.39, No.8, pp.1681-1696, 2016.

D.D. Niu, L. Liu and S. YU, “Knowledge compilation algorithm based on computing the intersection for EPCCL theories”, Journal of Software, Vol.28, No.8, pp.2096-2112, 2017.

J.Y. Xu and R.M. Stephan, “HIAWSC: An immune algorithm based heuristic web service composition framework”, Chinese Journal of Electronics, Vol.23, No.3, pp.579-585, 2014.

D.M. Dai and D.J. Mu, “Heuristic genetic algorithm for feature selection in incomplete information systems”, Acta Electronica Sinica, Vol.41, No.3, pp.451-455, 2013. (in Chinese)

H.B. Li, Y.C. Liang, N. Zhang, J.S. Guo, D. Xu and Z.S. Li, “Improving degree-based variable ordering heuristics for solving constraint satisfaction problems”, Journal of Heuristics, Vol.22, No.2, pp.125-145, 2016.

W.X. Gu, J.Y. Wang and M.H. Yin, “Knowledge compilation using extension rule based on MCN and MO heuristic strategies”, Journal of Computer Research and Development, Vol.48, No.11, pp.2064-2073, 2011.

A. Darwiche, “SDD: A new canonical representation of propositional knowledge bases”, Proc. of the 22nd International Joint Conference on Artificial Intelligence, Barcelona, Catalonia, Spain, pp.819-826, 2011.

Relative Articles

Supplements(0)

Cited By

Proportional views