NIU Dangdang, LIU Lei, LYU Shuai, XU Yue. Complementary Knowledge Compilation Using the Hyper Extension Rule[J]. Chinese Journal of Electronics, 2019, 28(2): 259-265. doi: 10.1049/cje.2018.06.009
Citation: NIU Dangdang, LIU Lei, LYU Shuai, XU Yue. Complementary Knowledge Compilation Using the Hyper Extension Rule[J]. Chinese Journal of Electronics, 2019, 28(2): 259-265. doi: 10.1049/cje.2018.06.009

Complementary Knowledge Compilation Using the Hyper Extension Rule

doi: 10.1049/cje.2018.06.009
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
  • 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.
  • loading
  • 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.
  • 加载中

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Article Metrics

    Article views (140) PDF downloads(162) Cited by()
    Proportional views
    Related

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return