Complementary Knowledge Compilation Using the Hyper Extension Rule

NIU Dangdang; LIU Lei; LYU Shuai; XU Yue

doi:10.1049/cje.2018.06.009

Volume 28 Issue 2

Turn off MathJax

Article Contents

Article Navigation > Chinese Journal of Electronics > 2019 > 28(2): 259-265

NIU Dangdang, LIU Lei, LYU Shuai, et al., “Complementary Knowledge Compilation Using the Hyper Extension Rule,” Chinese Journal of Electronics, vol. 28, no. 2, pp. 259-265, 2019, doi: 10.1049/cje.2018.06.009

Citation:

NIU Dangdang, LIU Lei, LYU Shuai, et al., “Complementary Knowledge Compilation Using the Hyper Extension Rule,” Chinese Journal of Electronics, vol. 28, no. 2, pp. 259-265, 2019, doi: 10.1049/cje.2018.06.009

Citation:

PDF( 554 KB)

Complementary Knowledge Compilation Using the Hyper Extension Rule

doi: 10.1049/cje.2018.06.009

NIU Dangdang^1,2,
LIU Lei¹,
LYU Shuai^{1,2
,},
XU Yue^1,2

1.
College of Computer Science and Technology, Jilin University, Changchun 130012, China;
2.
Key Laboratory of Symbolic Computation and Knowledge Engineering, Ministry of Education, Jilin University, 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, machine learning and automated reasoning. (Email:lus@jlu.edu.cn)
Received Date: 2017-03-31
Rev Recd Date: 2017-10-31
Publish Date: 2019-03-10

Abstract

Abstract

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.
- Knowledge compilation,
- Extension rule,
- Hyper extension rule,
- Compilation language,
- Each pair contains complementary literals (EPCCL) theory

FullText(HTML)

References(13)

References

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

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.

F. Koriche, J.M. Laginez, P. Marquis, et al., “Knowledge compilation for model counting: Affine decision trees”, Proc. of the 23rd International Joint Conference on Artificial Intelligence, Beijing, China, pp.947-953, 2013.

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

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

P. Marquis, “Existential closures for knowledge compilation”, Proc. of the 22nd International Joint Conference on Artificial Intelligence, Barcelona, Catalonia, Spain, pp.996-1001, 2011.

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. (in Chinese)

L. Liu, D.D. Niu, Z. Li, et. al., “Dynamic online reasoning algorithm based on the hyper extension rule”, Journal of Harbin Engineering University, Vol.36, No.12, pp.1614-1619, 2015. (in Chinese)

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

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

M.H. Yin, H. Lin and J.G. Sun, “Counting models using extension rules”, Proc. of the 22nd AAAI Conference on Artificial Intelligence, Vancouver, British Columbia, Canada, pp.1916-1917, 2007.

Relative Articles

Supplements(0)

Cited By

Proportional views