A Unifying Approach for Nonmonotonic S4F, (Reflexive) Autoepistemic Logic, and Answer Set Programming

• Autorzy: Su Ezgi Iraz

Identyfikatory

DOI

10.3233/FI-2020-1972

• Języki publikacji: EN

Abstrakty

EN

This paper presents a general strategy, bringing together some major types of nonmonotonic reasoning under a monotonic bimodal setting. Such formalisms are also of interest to the fields of knowledge representation and declarative programming. We exemplify the methodology, capturing minimal model reasoning that underlies nonmonotonicity over S4F first, but then we also show how to apply the technique to other nonmonotonic logics respectively based on the modal logics KD45 and SW5 . We naturally succeed it, by modifying only the axioms of the underlying modal logic and show that it successfully works. The last two formalisms are also known as autoepistemic logic (AEL) and its reflexive extension (RAEL) in the given order: AEL is an important form of nonmonotonic reasoning, introduced by Robert C. Moore in order to allow an agent to reason about his own knowledge. Equilibrium logic (EL) is a general-purpose nonmonotonic reasoning formalism, proposed more recently by David Pearce as a semantical framework for answer set programming (ASP). The latter is an efficient declarative problem solving approach with lots of applications to science and technology. Fariñas et al. have embedded EL (and so ASP) into a monotonic bimodal logic. We take this work as an initiative and successfully apply a similar methodology to closely aligned nonmonotonic modal logics. We finally discuss the potential capability to subsume the epistemic extensions of ASP within our unified paradigm.

Słowa kluczowe

EN

nonmonotonic reasoning; minimal model semantics; autoepistemic equilibrium logic; answer set programming; epistemic specification; monotonic modal logic; Kripke model

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2020
• Tom: Vol. 176, nr 3/4
• Strony: 205--234
• Opis fizyczny: Bibliogr. 63 poz., tab.

Twórcy

autor

Su Ezgi Iraz

• Computer Engineering Program, Faculty of Engineering, Istanbul Aydin University, Istanbul, Turkey

Bibliografia

• [1] Levesque HJ. All I know: a study in Autoepistemic Logic. Artificial intelligence, 1990. 42(2-3):263-309.
• [2] Chen J. The Logic of Only Knowing as a Unified Framework for Non-Monotonic Reasoning. Fundamenta Informaticae, 1994. 21(3):205-220. doi:10.3233/FI-1994-2133.
• [3] Chen J. Relating only knowing to minimal belief and negation as failure. Journal of Experimental and Theoretical Artificial Intelligence, 1994. 6(4):409-429. doi:10.1080/09528139408953796.
• [4] Chen J. The Generalized Logic of only Knowing (GOL) That Covers the Notion of Epistemic Specifications. Journal of Logic and Computation, 1997. 7(2):159-174. doi:10.1093/logcom/7.2.159.
• [5] Lakemeyer G, Levesque HJ. Only-Knowing: taking It Beyond Autoepistemic Reasoning. In: Veloso MM, Kambhampati S (eds.), Proceedings of the 20th National Conference on Artificial Intelligence and the 17th Innovative Applications of Artificial Intelligence Conference. AAAI Press. 2005 pp. 633-638. ISBN:1-57735-236-X. URL http://www.aaai.org/Library/AAAI/2005/aaai05-099.php.
• [6] Lakemeyer G, Levesque HJ. Towards an Axiom System for Default Logic. In: Proceedings of the Twenty-First National Conference on Artificial Intelligence and the 18th Innovative Applications of Artificial Intelligence Conference. AAAI Press, 2006 pp. 263-268. URL http://www.aaai.org/Library/AAAI/2006/aaai06-042.php.
• [7] Lakemeyer G, Levesque HJ. Only-Knowing meets nonmonotonic modal logic. In: Brewka G, Eiter T, McIlraith SA (eds.), Proceedings of the Thirteenth International Conference on Principles of Knowledge Representation and Reasoning. AAAI Press. 2012 pp. 350-357. ISBN:978-1-57735-560-1. URL http://www.aaai.org/ocs/index.php/KR/KR12/paper/view/4507.
• [8] Fariñas del Cerro L, Herzig A, Su EI. Combining Equilibrium Logic and Dynamic Logic. In: Cabalar P, Son TC (eds.), Proceedings of the Twelfth International Conference on Logic Programming and Nonmonotonic Reasoning, volume 8148 of Lecture Notes in Computer Science. Springer. 2013 pp. 304-316. ISBN:978-3-642-40563-1. doi:10.1007/978-3-642-40564-8.
• [9] Fariñas del Cerro L, Herzig A, Su EI. Capturing equilibrium models in modal logic. Journal of Applied Logic, 2014. 12(2):192-207. doi:10.1016/j.jal.2013.12.003.
• [10] Su EI. Extensions of equilibrium logic by modal concepts. Ph.D. thesis, Institut de Recherche en Informatique de Toulouse, France, 2015. URL https://tel.archives-ouvertes.fr/tel-01636791.
• [11] Su EI. A Monotonic View on Reflexive Autoepistemic Reasoning. In: Balduccini M, Janhunen T (eds.), Proceedings of the 14th International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 2017, Espoo, Finland, July 3-6, 2017, volume 10377 of Lecture Notes in Computer Science. Springer, Springer. 2017 pp. 85-100. ISBN:978-3-319-61659-9. doi:10.1007/978-3-319-61660-5_10.
• [12] Su EI. An S4F-related monotonic modal logic. In: Monica DD, Murano A, Rubin S, Sauro L (eds.), Joint Proceedings of the 18th Italian Conference on Theoretical Computer Science (ICTCS 2017) and the 32nd Italian Conference on Computational Logic (CILC 2017) co-located with the 2017 IEEE International Workshop on Measurements and Networking (2017 IEEE M&N), Naples, Italy, September 26-28, 2017, volume 1949 of CEUR Workshop Proceedings. CEUR-WS.org 2017, 2017 pp. 346-360. URL http://ceur-ws.org/Vol-1949.
• [13] Schwarz GF. Reflexive autoepistemic logic. Fundamenta Informaticae, 1992. 17(1-2):157-173.
• [14] Moore RC. Semantical Considerations on Nonmonotonic Logic. Artificial Intelligence, 1985. 25(1).
• [15] Segerberg K. An essay in classical modal logic. Filosofiska studier. Filosofiska föreningen och Filosofiska institutionen vid Uppsala universitet, 1971. URL https://books.google.pt/books?id=HAAZAQAAIAAJ.
• [16] Truszczyński M. Embedding Default Logic into Modal Nonmonotonic Logics. In: Proceedings of the First International Workshop on Logic Programming and Nonmonotonic Reasoning. 1991 pp. 151-165.
• [17] Schwarz GF, Truszczyński M. Modal logic S4F and the minimal knowledge paradigm. In: Moses Y (ed.), Proceedings of the Fourth Conference on Theoretical Aspects of Reasoning about Knowledge. Morgan Kaufmann Publishers Inc., Morgan Kaufmann. 1992 pp. 184-198. ISBN:1-55860-243-7.
• [18] Schwarz G, Truszczyński M. Minimal Knowledge Problem: a New Approach. Artificial Intelligence, 1994. 67(1):113-141. doi:10.1016/0004-3702(94)90013-2.
• [19] Cabalar P, Lorenzo D. New insights on the intuitionistic interpretation of Default Logic. In: de Mántaras RL, Saitta L (eds.), Proceedings of the Sixteenth European Conference on Artificial Intelligence. IOS Press, 2004 pp. 798-802.
• [20] Truszczyński M. The Modal Logic S4F, the Default Logic, and the Logic Here-and-There. In: Proceedings of the Twenty-Second AAAI Conference on Artificial Intelligence. 2007 pp. 508-514. URL http://www.aaai.org/Library/AAAI/2007/aaai07-080.php.
• [21] Pearce D, Uridia L. A Logic Related to Minimal Knowledge. In: Esteva M, Fernández A, Giret A (eds.), Proceedings of the 2nd Workshop on Agreement Technologies (WAT-2009), Sevilla, Spain, November 9, 2009, volume 635. 2009 URL http://ceur-ws.org/Vol-635/.
• [22] Pearce D, Uridia L. An approach to minimal belief via objective belief. In: Proceedings of the 22nd International Joint Conference on Artificial Intelligence, volume 22. AAAI Press, 2011 pp. 1045-1050.
• [23] Reiter R. A Logic for Default Reasoning. Artificial Intelligence, 1980. 13(1-2):81-132. doi:10.1016/0004-3702(80)90014-4.
• [24] Lifschitz V. Minimal Belief and Negation as Failure. Artificial Intelligence, 1994. 70(1-2):53-72. doi:10.1016/0004-3702(94)90103-1.
• [25] Hughes GE, Cresswell MJ. A new introduction to modal logic. Routledge, 2012. ISBN:1134800282, 9781134800285.
• [26] Schwarz GF. Minimal model semantics for nonmonotonic modal logics. In: Proceedings of the Seventh Annual Symposium on Logic in Computer Science. IEEE Computer Society Press. ISBN:0-8186-2735-2, 1992 pp. 34-43. doi:10.1109/LICS.1992.185517. URL http://dx.doi.org/10.1109/LICS.1992.185517.
• [27] Marek VW, Truszczyński M. Nonmonotonic logic: context-dependent reasoning. Springer, 1993.
• [28] Moore RC. Autoepistemic Logic Revisited. Artificial Intelligence, 1993. 59(1-2):27-30. doi:10.1016/0004-3702(93)90165-8.
• [29] Fariñas del Cerro L, Herzig A, Su EI. Epistemic Equilibrium Logic. In: Yang Q, Wooldridge M (eds.), Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015, Buenos Aires, Argentina, July 25-31, 2015. AAAI Press. 2015 pp. 2964-2970. ISBN:978-1-57735-738-4. URL http://ijcai.org/Abstract/15/419.
• [30] Su EI. Epistemic Answer Set Programming. In: Calimeri et al. [50], 2019 pp. 608-626. doi:10.1007/978-3-030-19570-0\_40.
• [31] Su EI, Fariñas del Cerro L, Herzig A. Autoepistemic equilibrium logic and epistemic specifications. Artificial Intelligence, 2020. 282:103249. doi:10.1016/j.artint.2020.103249.
• [32] Su EI. Revisiting epistemic answer set programing and epistemic splitting property. In: Workshop on Epistemic Extensions of Logic Programming (EELP 2019) of the 35th International Conference of Logic Programming, Las Cruces, New Mexico, USA, September 20-25, 2019.
• [33] Schwarz G. On Embedding Default Logic into Moore’s Autoepistemic Logic. Artificial Intelligence, 1996. 80(1-2):349-359. doi:10.1016/0004-3702(95)00117-4.
• [34] Truszczyński M. Modal Interpretations of Default Logic. In: Mylopoulos J, Reiter R (eds.), Proceedings of the 12th International Joint Conference on Artificial Intelligence. Morgan Kaufmann. 1991 pp. 393-398. ISBN:1-55860-160-0. URL http://ijcai.org/proceedings/1991-1.
• [35] Lifschitz V, Schwarz G. Extended logic programs as autoepistemic theories. In: Pereira LM, Nerode A (eds.), Proceedings of the Second International Workshop on Logic Programming and Non-monotonic Reasoning. MIT Press. 1993 pp. 101-114. ISBN: 0-262-66083-0.
• [36] Marek VW, Truszczyński M. Relating autoepistemic and default Logics. In: Brachman RJ, Levesque HJ, Reiter R (eds.), Proceedings of the First International Conference on Principles of Knowledge Representation and Reasoning. Morgan Kaufmann, 1989 pp. 276-288.
• [37] Schwarz GF. Autoepistemic logic of knowledge. In: Proceedings of the First International Workshop on Logic Programming and Nonmonotonic Reasoning. MIT Press, 1991 pp. 260-274.
• [38] Heyting A. Die formalen Regeln der intuitionistischen Logik. Sitzungsber. preuss. Akad. Wiss., 1930. 42-71:158-169.
• [39] Pearce D. Equilibrium logic. Annals of Mathematics and Artificial Intelligence, 2006. 47(1-2):3-41. doi:10.1007/s10472-006-9028-z.
• [40] Stalnaker R. A note on nonmonotonic modal logic. Artificial Intelligence, 1993. 64(2):183-196.
• [41] Stalnaker R. What is a Nonmonotonic Consequence Relation? Fundamenta Informaticae, 1994. 21(1/2):7-21.
• [42] Schwarz G. Autoepistemic Logic of Knowledge. In: LPNMR. 1991 pp. 260-274.
• [43] Schwarz G. Reflexive Autoepistemic logic. Fundamenta Informaticae, 1992. 17(1-2):157-173.
• [44] Marek V, Truszczynski M. Relating Autoepistemic and Default Logics. In: Brachman RJ, Levesque HJ, Reiter R (eds.), First International Conference on Principles of Knowledge Representation and Reasoning (KR’89). Morgan Kaufmann, Toronto, Canada, 1989 pp. 276-288.
• [45] Marek W, Truszczyński M. Nonmonotonic Logic: Context-Dependent Reasoning. Springer-Verlag, 1993.
• [46] Schwarz G. Minimal Model Semantics for Nonmonotonic Modal Logics. In: Proceedings of the Seventh Annual IEEE Symposium on Logic in Computer Science (LICS 1992). IEEE Computer Society Press, 1992 pp. 34-43.
• [47] Konolige K. On the Relation Between Default and Autoepistemic Logic. Artificial Intelligence, 1988. 35(3):343-382. doi:10.1016/0004-3702(88)90021-5.
• [48] Su EI. Strongly Equivalent Epistemic Answer Set Programs. In: Alviano et al. [49], 2019 pp. 101-115. doi:10.1007/978-3-030-35166-3\_8.
• [49] Alviano M, Greco G, Scarcello F (eds.). AI*IA 2019 - Advances in Artificial Intelligence – XVIII th International Conference of the Italian Association for Artificial Intelligence, Rende, Italy, November 19-22, 2019, Proceedings, volume 11946 of Lecture Notes in Computer Science. Springer, 2019. ISBN:978-3-030-35165-6. doi:10.1007/978-3-030-35166-3.
• [50] Calimeri F, Leone N, Manna M (eds.). Logics in Artificial Intelligence - 16th European Conference, JELIA 2019, Rende, Italy, May 7-11, 2019, Proceedings, volume 11468 of Lecture Notes in Computer Science. Springer, 2019. ISBN:978-3-030-19569-4. doi:10.1007/978-3-030-19570-0.
• [51] Schwarz G, Truszczynski M. Modal Logic S4F and The Minimal Knowledge Paradigm. In: TARK. 1992 pp. 184-198.
• [52] Halpern JY, Moses Y. Towards a Theory of Knowledge and Ignorance: Preliminary Report. In: Apt KR (ed.), Logics and Models of Concurrent Systems. Springer-Verlag, 1985 pp. 459-476.
• [53] Schwarz G. Autoepistemic Logic of Knowledge. In: Nerode A, Marek VW, Subrahmanian VS (eds.), Logic Programming and Non-monotonic Reasoning, Proceedings of the First International Workshop, Washington, D.C., USA, July 1991. The MIT Press. ISBN:0-262-64027-9, 1991 pp. 260-274.
• [54] Gabbay DM, Hogger CJ, Robinson JA (eds.). Autoepistemic Logic, volume 3. Oxford Science Publications, 1995.
• [55] Kahl PT. Refining the semantics for epistemic logic programs. Ph.D. thesis, 2014.
• [56] Gelfond M. New Semantics for Epistemic Specifications. In: Delgrande JP, Faber W (eds.), Logic Programming and Nonmonotonic Reasoning - 11th International Conference, LPNMR 2011, Vancouver, Canada, May 16-19, 2011. Proceedings, volume 6645 of Lecture Notes in Computer Science. Springer. 2011 pp. 260-265. ISBN:978-3-642-20894-2. doi:10.1007/978-3-642-20895-9.
• [57] Blackburn P, de Rijke M, Venema Y. Modal logic, volume 53. Cambridge University Press, Cambridge Tracts in Theoretical Computer Science, 2002.
• [58] Pearce D. A New Logical Characterisation of Stable Models and Answer Sets. In: Dix J, Pereira LM, Przymusinski TC (eds.), Non-Monotonic Extensions of Logic Programming, NMELP ’96, Bad Honnef, Germany, September 5-6, 1996, Selected Papers, volume 1216 of Lecture Notes in Computer Science. Springer. 1996 pp. 57-70. ISBN:3-540-62843-6. doi:10.1007/BFb0023798.
• [59] Marek TM V Wiktor. Reflexive autoepistemic logic and logic programming. In: Proceedings of the Second International Workshop on Logic Programming and Non-Monotonic Reasoning. MIT Press, 1993 pp. 115-131.
• [60] Shoham Y. A semantical approach to nonmonotonic logics. In: Proceedings of the Tenth International Joint Conference on Artificial Intelligence. Morgan Kaufmann Publishers Inc., 1987 pp. 1413-1419.
• [61] Baral C. Knowledge representation, reasoning and declarative problem solving. Cambridge University Press, New York, NY, USA, 2003. ISBN:0521818028.
• [62] Gelfond M, Lifschitz V. The Stable Model Semantics for Logic Programming. In: Kowalski RA, Bowen KA (eds.), Proceedings of the Fifth International Conference on Logic Programming. MIT Press. 1988 pp. 1070-1080. ISBN:0-262-61056-6.
• [63] Gelfond M, Lifschitz V. Classical Negation in Logic Programs and Disjunctive Databases. New Generation Computing, 1991. 9(3/4):365-386. doi:10.1007/BF03037169.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).