Notes on nonmonotonic autoepistemic propositional logic

Suchenek, M. A.

Artykuł - szczegóły

Tytuł artykułu

Notes on nonmonotonic autoepistemic propositional logic

Autorzy

Suchenek M. A.

Treść / Zawartość

Pełne teksty:

Pobierz

Identyfikatory

Warianty tytułu

Uwagi dotyczące niemonotonicznego autoepistemicznego rachunku zdań

Języki publikacji

Abstrakty

This paper comprises an in-depth study of semantics of autoepistemic logic that is based on author’s may years of research in the subject matter. It begins with a brief review of semantics of common patterns of nonmonotonic deduction arising from a lack of knowledge, including autoepistemic deduction, in terms of the fixed-point equation F (T, E) = E. Then it narrowly investigates minimal expansion semantics for autoepistemic propositional logic and its „only knowing” consequence operation CnAE. In particular, the following minimalknowledge assumption M K A : ϕ ∈M K A (T) iff ϕ does not add modally positive S5- consequences to T is used to syntactically characterize the operation CnAE by means of suitable completeness theorem. The paper also offers a proof that the consequence operation CnS5 of modal logic S5 is the maximal monotonic consequence operation satisfying CnS5(T) ⊆ M K A (T) for every modal theory T.

Artykuł stanowi dogłębne studium semantyki logiki autoepistemicznej wykorzystujące wyniki wieloletnich badań autora w tym przedmiocie. Rozpoczyna się ono od skrótowego przeglądu semantyk powszechnie stosowanych wzorców niemonotonicznej dedukcji biorącej się z braku wiedzy, włączając w to dedukcję autoepistemiczną, w terminach równania stałopunktowego F (T, E) = E. Następnie bada ono szczegółowo semantykę minimalnych ekspansji dla zdaniowej logiki autoepistemicznej oraz jej operację CnAE odpowiadającą schematowi wnioskowania opartemu na założeniu „wiedząc tylko”. W szczególności następujące założenie M K A o minimalności wiedzy: ϕ ∈M K A (T) wtedy, i tylko wtedy, gdy ϕ nie dokłada modalnie pozytywnych S5-konsekwencji do T jest używane w celu syntaktycznego scharakteryzowania operacji CnAE przy pomocy stosownego twierdzenia o pełności. Artykuł przedstawia też dowód, że operacja konsekwencji CnS5 logiki modalnej S5 jest maksymalną monotoniczną operacją konsekwencji spełniającą CnS5(T) ⊆ M K A (T) dla każdej teorii modalnej T.

Słowa kluczowe

autoepistemic logic semantic autoepistemic deduction

logika autoepistemiczna semantyka rachunek zdań autoepistemiczny

Wydawca

Warszawska Wyższa Szkoła Informatyki

Czasopismo

Zeszyty Naukowe Warszawskiej Wyższej Szkoły Informatyki

Rocznik

2011

Tom

nr 6

Strony

74--92

Opis fizyczny

Bibliogr. 42 poz.

Twórcy

autor

Suchenek M. A.

Department of Computer Science na California State University, Dominguez Hills

Bibliografia

1. Espen H. Lian A, Einar Broch Johnsen A, and Arild Waaler A. “Confluent term rewriting for only-knowing logics”. In Proceeding of the 2010 conference on STAIRS 2010, pages 162-174, Amsterdam, The Netherlands, 2010. IOS Press.
2. Krzysztof R. Apt. “Introduction to logic programming”. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, volume B, pages 493-574. Elsevier and MIT, 1990.
3. Jon Barwise, editor. Handbook of Mathematical Logic. North- Holland, Amsterdam, second edition, 1978.
4. Jon Barwise. “An introduction to first-order logic”. In [Bar78a], chapter A.1, pages 5-46. 1978.
5. Genviéve Bossu and Pierre Siegel. “Saturation, nonmonotonic reasoning, and the closed world assumption”. Artificial Intelligence, 25(1):13-64, 1984.
6. Brian F. Chellas. Modal Logic: An Introduction. Cambridge University Press, 1980.
7. David W. Etherington, Robert E. Mercer, and Raymond Reiter. “On the adequacy of predicate circumscription for closed-world reasoning”. Computational Intelligence, 1(1):11-15, 1985.
8. Joseph Y. Halpern and Yoram O. Moses. “Towards a theory of knowledge and ignorance: preliminary report”. In Proceedings of the Conference on Logics and Models of Concurrent Systems, NATO Advanced Study Institute, La Colle-sur-Loup, France, pages 459- 476, 1985.
9. Michael Kaminski. “Embedding a default system into nonmonotonic logics”. Fundamenta Informaticae, 14:345-353, 1991.
10. H. Jerome Keisler. “Fundamentals of model theory”. In [Bar78a], chapter A.2, pages 47-104. 1978.
11. Kurt Konolige. “On the relation between default and autoepistemic logic”. Artificial Intelligence, 35:343-382, 1988.
12. Hector J. Levesque. “All I know: A study in autoepistemic logic”. Artificial Intelligence, 42:263-309, 1990.
13. Vladimir Lifschitz. “Computing circumscription”. In Proceedings of Eight International Joint Conference on Artificial Intelligence, pages 121-127, Los Angeles, 1985.
14. Roger C. Lyndon. “Properties preserved under homomorphism”. Pacific J. Math., 9:143-154, 1959.
15. Wiktor Marek and Mirosław Truszczynski. “Modal logic for default reasoning”. Annals of Applied Mathematicsand Artificial Intelligence, 1:275-302, 1990.
16. Wiktor Marek and Mirosław Truszczynski. “Autoepistemic logic”. JACM, 38(3):588-619, 1991.
17. Wiktor Marek and Mirosław Truszczynski. “Nonmonotonic Logic: Context-Dependent Reasoning”. Artificial Intelligence. Springer- Verlag, 1993.
18. John McCarthy. “Circumscription - a form of non-monotonic reasoning”. Artificial Intelligence, 13(1-2):27-39, 1980.
19. Drew McDermott and Jon Doyle. “Non-monotonic logic I”. Artificial Intelligence, 13(1-2):41-72, 1980.
20. Jack Minker. “On indefinite databases and closed world assumption”. In Proceedings of 6-th Conference on Automated Deduction, Lecture Notes in Computer Science 138, pages 292-308, Berlin, New York, 1982. Springer Verlag.
21. V.W. Marek and A. Nerode. “Nonmonotonic reasoning”. In Encyclopedia of Computer Science and Technology, volume 34, pages 281-289. Marcel Dekker, 1994.
22. Robert C. Moore. “Semantical considerations on nonmonotonic logic”. Artificial Intelligence, 25(1):75-94, 1985.
23. Rohit Parikh. “Monotonic and nonmonotonic logics of knowledge”. Fundamenta Informaticae, 15(3,4):255-274, 1991.
24. Raymond Reiter. “On closed world data bases”. In Hervé Gallaire and Jack Minker, editors, Logic and Data Bases, pages 55-76. Plenum Press, 1978.
25. Jussi Rintanen. “Prioritized autoepistemic logic”. In Proceedings of the European Workshop on Logics in Artificial Intelligence, volume 838 of Lecture Notes in Computer Science, pages 232 - 246, London, UK, 1994. Springer-Verlag.
26. Grigori Schwarz. “Minimal model semantics for nonmonotonic modal logics”. In Proceedings of Seventh Annual IEEE Symposium on Logic in Computer Science, pages 34-43, Santa Cruz, CA, June 22-25 1992. IEEE Computer Society Press.
27. Marek A. Suchenek and Rajshekhar Sunderraman. “Minimal models for closed world data bases with views”. In Zbigniew W. Ras, editor, Methodologies for Intelligent Systems, 5, pages 182-193, New York, 1990. North-Holland.
28. Marek A. Suchenek. “Incremental models of updating data bases”. In C. H. Bergman, R. D. Maddux, and D. L. Pigozzi, editors, Algebraic Logic and Universal Algebra in Computer Science, Lecture Notes in Computer Science 425, pages 243-271, Ames, June 1-4 1988. Springer-Verlag.
29. Marek A. Suchenek. “On generalizations of the closed world assumption in deductive data bases”. In Fourth Southeastern Logic Symposium, Columbia SC, March 24-25 1988. Unpublished presentation.
30. Marek A. Suchenek. “A syntactic characterization of minimal entailment”. In Ewing L. Lusk and Ross A. Overbeek, editors, Logic Programming, North American Conference 1989, pages 81-91, Cambridge, MA, October 16-20 1989. MIT Press.
31. Marek A. Suchenek. “Applications of Lyndon homomorphism theorems to the theory of minimal models”. International Journal of Foundations of Computer Science, 1(1):49-59, 1990.
32. Marek A. Suchenek. “First-order syntactic characterizations of minimal entailment, domain minimal entailment, and Herbrand entailment”. Journal of Automated Reasoning, 10:237-263, 1993.
33. Marek A. Suchenek. “Preservation properties in deductive databases”. Methods of Logic in Computer Science An International Journal, 1:315-338, 1994. An invited paper.
34. Marek A. Suchenek. “Evaluation of queries under the closed-world assumption”. Journal of Automated Reasoning, 18:357-398, 1997.
35. Marek A. Suchenek. “Evaluation of queries under the closed-world assumption II”. Journal of Automated Reasoning, 25:247-289, 2000.
36. Marek A. Suchenek. “Review of the book: G. Antoniou, ‘Nonmonotonic Reasoning’, The MIT Press”. Bulletin of Symbolic Logic, 6(4):484-490, 2000.
37. Marek A. Suchenek. “Sound and complete propositional nonnonotonic logic of hierarchically-minimal models”. In Proceedings of the Intelligent Information Systems 2000 Symposium, Advances in Soft Computing, pages 193-205, Bystra, Poland, June 12-16 2000. Physica-Verlag.
38. Marek A. Suchenek. “On asymptotic decidability of some problems related to artificial intelligence”. In AMS 2003 Spring Western Section Meeting, Special Session on Beyond Classical Boundaries of Computability III, San Francisco, CA, May 3-4 2003. American Mathematical Society. Unpublished presentation, posted at http://csc.csudh.edu/suchenek/Papers/OnAsymptoticDecidabilty .doc.
39. Marek A. Suchenek. “Complete non-monotonic autoepistemic logic”. In Logic in Hungary, Budapest, Hungary, August 5-10 2005. Janos Bolyai Mathematical Society. Unpublished presentation, abstract posted at http://atlasconferences. com/cgi-bin/abstract/caqb-42.
40. Marek A. Suchenek. “On undecidability of non-monotonic logic”. Studia Informatica, 1/2(7):127-132, 2006.
41. Michael Thomas and Heribert Vollmer. “Complexity of nonmonotonic logics”. Computing Research Repository, September 2010.
42. A. Yahya and L. Henschen. “Deduction in non-Horn databases”. Journal of Automated Reasoning, 1:141-160, 1985.

Uwagi

Publikacja opracowana w ramach projektu „Program rozwoju oferty dydaktycznej i podnoszenia kompetencji wykładowców w Warszawskiej Wyższej Szkole Informatyki”

Typ dokumentu

Bibliografia

Identyfikator YADDA

bwmeta1.element.baztech-ce099e62-bdef-489d-a378-c4ef600f9145