微信服务号

微信订阅号

2025-4-16- 6
Home > Archive>Volume 26, Issue 8, 2015 >1937-1945. DOI:10.13328/j.cnki.jos.004694
PDF HTML XML Export Cite reminder
Method of Solving Abductive Reasoning Problem via Hitting Set
Author:
Affiliation:

  • Article
    • | |
  • Metrics
    • |
  • Reference [28]
    • |
  • Related [20]
    • |
  • Cited by
    • | |
  • Comments
    Abstract:

    As important type of reasoning besides induction and deduction, abduction has been widely used in many areas, such as AI. Generally speaking, abductive reasoning is the process of inferring causes from the observations. Unlike past research, which uses prime implicate and prime implicant, this study proves that seeking minimal interpretation of abductive problem for propositional logic and propositional modal logic system S5 can be reduced to the problem of seeking minimal hitting set in the corresponding set, and presents a new method for solving abductive problems.

    Reference
    [1] Reiter R. A theory of diagnosis from first principles. Artificial Intelligence, 1987,32(1):57-95. [doi: 10.1016/0004-3702(87)90062- 2]
    [2] Eshghi K. Abductive planning with event calculus. In: Proc. of the 5th Int'l Conf. on Logic Programming. 1988. 562-579.
    [3] Pople Jr HE. On the mechanization of abductive logic. In: Proc. of the 3rd Int'l Joint Conf. on Artificial Intelligence (IJCAI-73). 1973. 147-152.
    [4] Levesque H. A knowledge-level account of abduction. In: Proc. of the llth Int'l Joint Conf. on Artificial Intelligence. Detroit: Morgan Kaufmann Publishers, 1989. 1061-1067.
    [5] Mayer MC, Pirri F. Propositional abduction in modal logic. Logic Journal of the IGPL, 1995,3(6):907-919. [doi: 10.1093/jigpal/3.6. 907]
    [6] Mayer MC, Pirri F. First-Order abduction via tableau and sequent calculi. Logic Journal of the IGPL1, 1993,1(1):99-117. [doi: 10. 1093/jigpal/1.1.99]
    [7] Du JF, Qi GL, Shen YD, Pan JZ. Towards practical ABox abduction in large OWL DL ontologies. In: Proc. of the AAAI 2011. San Francisco: AAAI Press, 2011. 1160-1165.
    [8] Bienvenu M. Complexity of abduction in the EL family of lightweight description logics. In: Proc. of the 11th Int'l Conf. on Principles of Knowledge Representation and Reasoning (KR 2008). AAAI Press, 2008. 220-230.
    [9] Hubauer T, Lamparter S, Pirker M. Automata-Based abduction for tractable diagnosis. In: Proc. of the DL 2010 Workshop. CEUR- WS.org, 2010. 360-371.
    [10] Klarman S, Endriss U, Schlobach S. Abox abduction in the description logic ALC. Journal of Automated Reasoning, 2011,46(1): 43-80. [doi: 10.1007/s10817-010-9168-z]
    [11] Paul G. Approaches to abductive reasoning: An overview. Artificial Intelligence Review, 1993,7(2):109-152. [doi: 10.1007/BF008 49080]
    [12] McIlraith S. Logic-Based abductive inference. Technical Report, KSL-98-19, Stanford: Knowledge Systems Laboratory, Stanford University, 1998.
    [13] Chen R, Jiang YF, Lin L. Study of abductive reasoning: State of the art and problems. Computer Science, 2003,30(5):23-26 (in Chinese with English abstract).
    [14] Eiter T, Gottlob G. The complexity of logic-based abduction. Journal of ACM, 1995,42(1):3-42. [doi: 10.1145/200836.200838]
    [15] Fellows MR, Pfandler A, Rosamond FA, Rummele S. The parameterized complexity of abduction. In: Proc. of the AAAI 2012. AAAI Press, 2012. 743-749.
    [16] Pfandler A, Rummele S, Szeider S. Backdoors to abduction. In: Proc. of the 23rd Int'l Joint Conf. on Artificial Intelligence. AAAI Press, 2013. 1046-1052.
    [17] Greiner R, Smith BA, Wilkerson RW. A correction to the algorithm in Reiter's theory of diagnosis. Artificial Intelligence, 1989, 41(1):79-88. [doi: 10.1016/0004-3702(89)90079-9]
    [18] Wotawa F. A variant of Reiter's hitting set algorithm. Information Processing Letters, 2001,79(1):45-51. [doi: 10.1016/S0020- 0190(00)00166-6]
    [19] Ouyang DT, Ouyang JH, Cheng XC, Liu J. A method of computing hitting set in model based diagnosis. Chinese Journal of Scientific Instrument, 2004,25(4):605-608 (in Chinese with English abstract).
    [20] Zhao XF, Ouyang DT. A method of combining SE-tree to compute all minimal hitting sets. Progress in Natural Science, 2006,16(2): 169-174. [doi: 10.1080/10020070612331343209]
    [21] Jiang YF, Lin L. Computing the minimal hitting sets with binary HS-tree. Ruan Jian Xue Bao/Journal of Software, 2002,13(12): 2267-2274 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/13/2267.htm
    [22] Jiang YF, Lin L. The computation of hitting sets with Boolean formulas. Chinese Journal of Computers, 2003,26(8):919-924 (in Chinese with English abstract).
    [23] Zhang N, Sun JG, Zhao XF, Ouyang DT. Computing minimal hitting sets with genetic algorithm. Journal of Guangxi Normal University: Natural Science Edition, 2006,24(4):62-65 (in Chinese with English abstract).
    [24] Huang J, Chen L, Zou P. Computing minimal diagnosis by compounded genetic and simulated annealing algorithm. Ruan Jian Xue Bao/Journal of Software, 2004,15(9):1345-1350 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/15/1345.htm
    [25] Lin L. Computing minimal hitting sets with logic array in model-based diagnosis. Journal of Jinan University, 2002,22(1):24-27 (in Chinese with English abstract).
    [26] Lin L. Computing minimal hitting sets with from first principles with RHS-tree. Microelectronics & Computer, 2002,19(2):7-10 (in Chinese with English abstract).
    [27] Zhang LM, Ouyang DT, Zeng HL. Computing the minimal hitting sets based on dynamic maximum degree. Journal of Computer Research and Development, 2011,48(2):209-215 (in Chinese with English abstract).
    [28] Rymon R. An SE-tree-based prime implicant generation algorithm. Annals of Mathematics and Artificial Intelligence, 1994,11(1-4): 351-366. [doi: 10.1007/BF01530750] Li ZS, Jiang YF. An retrospect and prospect on model-based diagnostic reasoning. Computer Science, 1998,25(6):54-57 (in Chinese with English abstract).
    Cited by
Get Citation

余泉,李承乾,申宇铭,王驹.溯因推理问题的碰集求解方法.软件学报,2015,26(8):1937-1945

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:November 22,2012
  • Revised:July 07,2014
  • Online: August 05,2015
Links:Institute of Software, CASChina Computer FederationCASNSFC
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address：4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code：100190
Phone：010-62562563 Fax：010-62562533 Email：jos@iscas.ac.cn
Technical Support：Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063