Computer Science

Computer Science ›› 2019, Vol. 46 ›› Issue (7): 195-205.doi: 10.11896/j.issn.1002-137X.2019.07.030

• Artificial Intelligence • Previous Articles     Next Articles

Knowledge Forgetting in Multi-agent Modal Logic System KD45n

WEN Xi-ming1,2,FANG Liang-da2,3,YU Quan2,4,CHANG Liang2,WANG Ju2   

  1. (Department of Information Science,Guangdong Institute of Public Administration,Guangzhou 510053,China)1
    (Guangxi Key Laboratory of Trusted Software(Guilin University of Electronic Technology),Guilin,Guangxi 541004,China)2
    (Department of Computer Science,Jinan University,Guangzhou 510632,China)3
    (School of Mathematics and Statistics,Qiannan Normal College for Nationalities,Duyun,Guizhou 558000,China)4
  • Received:2018-07-09 Online:2019-07-15 Published:2019-07-15

PDF (PC)

1111

Abstract: Forgetting plays an important role in knowledge representation and reasoning.It has been extensively studied in many logics and been widely applied to various fields.Modal logic is suitable for representing and reasoning about the knowledge of agents.With the development of the research on multi-agent systems,the investigation on knowledge forgetting in multi-agent modal logics begins to attract attention.However,knowledge forgetting has different properties in different multi-agent modal logic systems,and it cannot be effectively computed in most cases.Therefore,it is necessary to make further investigation on the knowledge forgetting in the multi-agent modal logic system KD45n.Firstly,the knowledge forgetting in the multi-agent modal logic was defined based on model theory.Then,the main properties of knowledge forgetting in KD45n were analyzed.Finally,an effective algorithm to compute knowledge forgetting in KD45n was provided.The computing algorithm adopts the idea of knowledge compilation which is an approach for addressing the intractability of a number of artificial intelligence problems.The alternating cover disjunctive formula is introduced.By compiling the general formula into alternating cover disjunctive formula,knowledge forgetting in KD45n can be effectively computed.The time complexity is double-exponential in the length of the original formula,but polynomial in the length of the compiled one.Compared with the current non-elementary one,the algorithm is more effective and more practical.The results of research show that knowledge forgetting in KD45n satisfies many important properties and can be effectively computed.

Key words: Knowledge compilation, Knowledge forgetting, Multi-agent modal logic, Reasoning about knowledge

CLC Number: 

  • TP181
[1]BOOLE G.The laws of thought[M].London:Walton and Maberley,1854.<br /> [2]LIN F Z.On strongest necessary and weakest sufficient conditions [J].Artificial Intelligence,2001,128(1-2):143-159.<br /> [3]DOHERTY P,LUKASZEWICZ W,SZALAS A.Computing strongest necessary and weakest sufficient conditions of first-order formulas[C]∥Proceedings of the 17th International Joint Conference on Artificial Intelligence (IJCAI-2001).Morgan Kaufmann Publishers,2001:145-154.<br /> [4]LIN F Z,REITER R.Forget it! [C]∥Proceedings of AAAI Fall Symposium on Relevance.AAAI Press,1994:141-146.<br /> [5]LANG J,LIBERATORE P,MARQUIS P.Propositional independence:Formula-variable independence and forgetting[J].Journal of Artificial Intelligence Research,2003(18):391-443.<br /> [6]FANG L D,WAN H,LIU X Q,et al.Dependence in propositional logic:Formula-formula dependence an formula forgetting-application to belief update and conservative extension[C]∥Proceedings of the 32th AAAI Conference on Artificial Intelligence (AAAI-2018).AAAI Press,2018:1835-1844.<br /> [7]SU K L,SATTAR A,LV G F,et al.Variable forgetting in reasoning about knowledge [J].Journal of Artificial Intelligence Research,2009(35):677-716.<br /> [8]LANG J,MARQUIS P.Reasoning under inconsistency:A forgetting-based approach [J].Artificial Intelligence,2010,174(12-13):799-823.<br /> [9]ZHANG Y,FOO N.Solving logic program conflict through strong and weak forgettings [J].Artificial Intelligence,2006,170(8／9):739-778.<br /> [10]ZHANG X W.Forgetting for distance-based reasoning and repair in DL-Lite [J].Knowledge-Based Systems,2016(107):246-260.<br /> [11]XIAO P,WANG K W,WANG Z.Inconsistency-tolerant forgetting in DL-lite [C]∥Proceedings of the 16th International Semantic Web Conference.Springer,2017.<br /> [12]CATE B T,CONRADIE W,MARX M,et al.Definitorially complete description logics [C]∥Proceedings of the 10th International Conference on Principles of Knowledge Representation and Reasoning (KR-2006).AAAI Press,2006:79-89.<br /> [13]WANG Z,WANG K W,TOPOR R W,et al.Uniform interpolation for ALC revisited [C]∥Australasian Joint Conference on Advances in Artificial Intelligence (ACAI-2009).Springer,2009:528-537.<br /> [14]WANG Z,WANG K W,TOPOR R W,et al.Tableau-based forgetting in ALC ontologies [C]∥Proceedings of the 19th European Conference on Artificial Intelligence (ECAI-2010).IOS Press,2010:47-52.<br /> [15]WANG K W,WANG Z,TOPOR R W,et al.Eliminating con- cepts and roles from ontologies in expressive descriptive logics [J].Computational Intelligence,2014,30(2):205-232.<br /> [16]KONTCHAKOV R,WOLTER F,ZAKHARYASCHEV M. Logic-based ontology comparison and module extraction,with an application to DL-Lite [J].Artificial Intelligence,2010,174(15):1093-1141.<br /> [17] KONEV B,WALTHER D,WOLTER F.Forgetting and uniform interpolation in large-scale description logic terminologies [C]∥Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI-2009).AAAI Press,2009:830-835.<br /> [18] LUTZ C,SEYLAN I,WOLTER F.An automata-theoretic approach to uniform interpolation and approximation in the description logic EL [C]∥Proceedings of the 14th International Conference on Principles of Knowledge Representation and Reasoning (KR-2012).AAAI Press,2012:286-296.<br /> [19]LUTZ C,WOLTER F.Foundations for uniform interpolation and forgetting in expressive description logics [C]∥Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI-2011).AAAI Press,2011:989-995.<br /> [20]LUDWIG M,KONEV B.Practical uniform interpolation and forgetting for ALC TBoxes with applications to logical Diffe-rence[C]∥Proceedings of the 14th International Conference on Principles of Knowledge Representation and Reasoning (KR-2014).AAAI Press,2014:318-327.<br /> [21]KOOPMANN P,SCHMIDT R A.Count and forget:Uniform interpolation of SHQ-ontologies [C]∥Proceedings of the 7th International Joint Conference on Automated Reasoning (IJCAR-2014).Springer,2014:434-448.<br /> [22]ZHAO Y,SCHMIDT R A.Concept forgetting in ALCOI-onto- logies using an Ackermann approach [C]∥Proceedings of the 14th International Semantic Web Conference (ISWC-2015).New York:Springer,2015:587-602.<br /> [23]KOOPMANN P,SCHMIDT R A.Uniform interpolation and forgetting for ALC ontologies with ABoxes[C]∥Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI-2015).AAAI Press,2015:175-181.<br /> [24]WANG Z,WANG K W,TOPOR R W,et al.Forgetting for knowledge bases in DL-Lite [J].Annals of Mathematics and Artificial Intelligence,2010,58(1-2):117-151.<br /> [25]KONTCHAKOV R,WOLTER F,ZAKHARYASCHEV M. Can you tell the difference between DL-Lite ontologies? [C]∥Proceedings of the 11th International Conference on Principles of Knowledge Representation and Reasoning (KR-2008),AAAI Press,2008:285-295.<br /> [26]NAYAK A,CHEN Y,LIN F Z.Forgetting and knowledge update [C]∥Proceedings of 19th Australian Joint Conference on Artificial Intelligence (AI-2006).Springer,2006:131-140.<br /> [27]LIN F Z,REITER R.How to progress a database [J].Artificial Intelligence,1997,92(1-2):131-167.<br /> [28]ZHANG Y,ZHOU Y.Knowledge forgetting:Properties and applications [J].Artificial Intelligence,2009,173(16-17):1525-1537.<br /> [29]LIU Y M,LAKEMEYER G.On first-order definability and computability of progression for local-effect actions and beyond [C]∥Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI-2009).AAAI Press,2009:860-866.<br /> [30]LIU Y M,WEN X M.On the progression of know- ledge in the situation calculus [C]∥Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI-2011).AAAI Press,2009:976-982.<br /> [31]FANG L D,LIU Y M,WEN X M.On the progression of know- ledge and belief for nondeterministic actions in the situation calculus [C]∥Proceedings of the 29th International Conference on Artificial Intelligence.AAAI Press,2015:2955-2963.<br /> [32]XU D,LIN Z Q.A prime implicates-based formulae forgetting [C]∥Proceedings of IEEE International Conference on Computer Science and Automation Engineering (CSAE-2011).IEEE,2011:128-132.<br /> [33]NONNENGART A,OHLBACH H J,SZALAS A.Elimination of Predicate Quantifiers[C]∥Proceedings of the 16th International Conference on Automated Deduction (CADE-16).Springer,1999:159-181.<br /> [34]ZHANG Y,ZHOU Y.Forgetting revisited [C]∥Proceedings of the 12th International Conference on the Principles ofKnow-ledge Representation and Reasoning (KR-2010).AAAI Press,2010:602-604.<br /> [35]ZHANG Y,ZHOU Y.Bounded forgetting [C]∥Proceedings of the 25th AAAI Conference on Artificial Intelligence (AAAI-2011),AAAI Press,2011:280-285.<br /> [36]WANG Y S,WANG K W,WANG Z,et al.Knowledge forgetting in circumscription:A preliminary report [C]∥Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI-2015).AAAI Press,2015:1649-1655.<br /> [37]WANG Y S,WANG K W,ZHANG M Y.Forgetting for answer set programs revisited [C]∥Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI-2013).AAAI Press,2013:1162-1168.<br /> [38]WANG Y S,ZHANG Y,ZHOU Y,et al.Knowledge forgetting in answer set programming [J].Journal of Artificial Intelligence Research,2014,(50):31-70.<br /> [39]DELGRANDE J,WANG K W.A syntax-independent approach to forgetting in disjunctive logic programs [C]∥Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI-2015).AAAI Presss,2015:1482-1488.<br /> [40]JI J M,YOU J H,WANG Y S.On forgetting postulates in answer set programming [C]∥Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI-2015).AAAI Press,2015:3076-3083.<br /> [41]EITER T,WANG K W.Semantic forgetting in answer set programming [J].Artificial Intelligence,2008,172(14):1644-1672.<br /> [42]WANG Z,WANG K W,ZHANG X W.Forgetting and unfolding for existential rules [C]∥Proceedings of the 32nd AAAI Conference on Artificial Intelligence (AAAI-18).AAAI Press,2018:2013-2020.<br /> [43]HALPERN J Y,MOSES Y.A guide to completeness and complexity for modal logics of knowledge and belief [J].Artificial Intelligence,1992,54(3):319-379.<br /> [44]HERZIG A,MENGIN J.Uniform interpolation by resolution in modal logic [C]∥Proceedings of the 11th European Conference on Logics in Artificial Intelligence(JELIA 2008).Springer,2008:219-231.<br /> [45]VISSER A.Uniform interpolation and layered bisimulation[M]∥ G del’96:Logical Foundations of Mathematics,Computer Scien-ce and Physics.Springer,1996:139-164.<br /> [46]B LKOV M.Uniform interpolation and propositional quanti- fiers in modal logics[J].Studia Logica,2007,85(1):1-31.<br /> [47]GHILARDI S,LUTZ C,WOLTER F,et al.Conservative extensions in modal logic [C]∥Advances in Modal Logic 6,Papers From the Sixth Conference on “Advances in Modal Logic”.College Publications,2006:187-207.<br /> [48]GHILARDI S,ZAWADOWSKI M.Undefinability of proposi- tional quantifiers in the modal system S4[J].Studia Logica,1995,55(2):259-271.<br /> [49]FANG L D,LIU Y M,DITMARSCH H V.Forgetting in multi-agent modal logics [C]∥Proceedings of the 25 International Joint Conference on Artificial Intelligence (IJCAI-2016).AAAI Press,2016:1066-1073.<br /> [50]BAADER F,CALVANESE D,MCGUINNESS D L,et al.The description logic handbook:theory,implementation,and applications [M].New York:Cambridge University Press,2003:154-155.<br /> [51]HUANG X,FANG B Q,WAN H,et al.A general multi-agent epistemic planner based on higher-order belief change [C]∥Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI-2017).AAAI Press,2017:1093-1101.<br /> [52]KRIPKE S.Semantic analysis of modal logic[J].Zeitschrift fur Mathematische Logik und Grundlagen der Mathematik,1963(9):67-96.<br /> [53]BLACKBURN P,DE RIJKE M,VENEMA Y.Modal Logic [M].Cambridge:Cambridge University Press,2001:55-57.<br /> [54]JANIN D,WALUKIEWICZ I.Automata for the modal μ-calculus and related results [M]∥Mathematical Foundations of Computer Science 1995.Springer,1995:552-562.
[1] GU Wen-xiang,ZHAO Xiao-wei,YIN Ming-hao. Knowledge Compilation Survey [J]. Computer Science, 2010, 37(7): 20-26.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.