Logic programming and reasoning with incomplete information. (English) Zbl 0858.68013
Summary: The purpose of this paper is to expand the syntax and semantics of logic programs and disjunctive databases to allow for the correct representation of incomplete information in the presence of multiple extensions. The language of logic programs with classical negation, epistemic disjunction, and negation by failure is further expanded by new modal operators K and M (where for the set of rules \(T\) and formula \(F\), \(KF\) stands for “F is known to be true by a reasoner with a set of premises \(T\)” and M\(F\) means “F may be believed to be true” by the same reasoner). Sets of rules in the extended language will be called epistemic specifications. We define the semantics of epistemic specifications (which expands the semantics of disjunctive databases from) and demonstrate their applicability to formalization of various forms of commonsense reasoning. In particular, we suggest a new formalization of the closed world assumption which seems to better correspond to the assumption’s intuitive meaning.
MSC:
| 68N17 | Logic programming |
References:
| [1] | N. Bidoit and C. Froidevaux, Minimalism subsumes default logic and circumscription, in:Proc. LICS-87 (1987) pp. 89-97. |
| [2] | C. Baral, J. Lobo and J. Minker, Wf3: A semantics for negation in normal disjunctive logic programs, in:Proc. Int. Symp. Methodologies of Intelligent Systems (1991). |
| [3] | C. Sakama, Possible model semantics for disjunctive databases, in:Proc. 1st Int. Conf. on Deductive and Object Oriented Databases (1989) pp. 1055-1060. |
| [4] | E. Chan, A possible world semantics for non-horn databases, Technical Report CS-89-47, University of Waterloo (1989). |
| [5] | K. Clark, Negation as failure, in:Logic and Data Bases, eds. H. Gallaire and J. Minker (Plenum, New York, 1978) pp. 293-322. |
| [6] | M. Gelfond, On stratified autoepistemic theories, in: Proc. AAAI-87 (1987) 207-211. |
| [7] | M. Gelfond, Strong introspection, in: Proc. AAAI-91 (1991) 386-391. |
| [8] | M. Gelfond and V. Lifschitz, The stable model semantics for logic programming, in:Logic Programming: Proc. 5th Int. Conf. Symp., eds. R. Kowalski and K. Bowen (1988) pp. 1070-1080. |
| [9] | M. Gelfond and V. Lifschitz, Logic programs with classical negation, in:Logic Programming: Proc. 7th Int. Conf., eds. D. Warren and P. Szeredi (1990) pp. 579-597. |
| [10] | M. Gelfond and V. Lifschitz, Classical negation in logic programs and disjunctive databases, New Generation Comp. (1991) pp. 365-387. · Zbl 0735.68012 |
| [11] | M. Gelfond, V. Lifschitz, H. Przymusi?ska and M. Truszczy?ski, Disjunctive defaults, in:Principles of Knowledge Representation and Reasoning: Proc. 2nd Int. Conf. eds. J. Allen, R. Fikes and E. Sandewall (1991) pp. 230-237. |
| [12] | M. Gelfond and H. Przymusinska, Negation as failure: Careful closure procedure, Artificial Intelligence 30 (1986) 273-287. · Zbl 0635.68119 · doi:10.1016/0004-3702(86)90001-9 |
| [13] | M. Gelfond and H. Przymusi?ska, Definitions in epistemic specifications, in:Logic Programming and Non-monotonic Reasoning: Proc. 1st Int. Workshop, eds. A. Nerod, V. Marek and V.S. Subramanian (1991) pp. 245-259. |
| [14] | M. Gelfond, H. Przymusinska and T. Przymusinski, The extended closed world assumption and its relation to parallel circumscription, in:Proc. 5th ACM Symp. on Principles of Database Systems (1986) pp. 133-139. |
| [15] | R. Kowalski and F. Sadri, Logic programs with exceptions, in:Logic Programming: Proc. 7th Int. Conf., eds. D. Warren and P. Szeredi (1990) pp. 598-613. |
| [16] | H. Levesque, Making believers out of computers, Artificial Intelligence 30 (1986) 81-108. · doi:10.1016/0004-3702(86)90068-8 |
| [17] | H. Levesque, All I know: a study in autoepistemic logic, Artificial Intelligence 42 (1990) 263-310. · Zbl 0724.03019 · doi:10.1016/0004-3702(90)90056-6 |
| [18] | J. Lobo, J. Minker and A. Rajasekar,Foundations of Disjunctive Logic Programming (MIT Press, 1992). · Zbl 0755.68033 |
| [19] | J. Lloyd and R. Topor, Making prolog more expressive, J. Logic Progr. 3 (1984) 225-240. · Zbl 0584.68022 · doi:10.1016/0743-1066(84)90011-6 |
| [20] | J. McCarthy, Circumscription ? a form of non-monotonic reasoning, Artificial Intelligence 13(1, 2) (1980) 27-39, 171-172. · Zbl 0435.68073 · doi:10.1016/0004-3702(80)90011-9 |
| [21] | D. McDermott and J. Doyle, Nonmonotonic logic I, Artificial Intelligence 13 (1980) 41-72. · Zbl 0435.68074 · doi:10.1016/0004-3702(80)90012-0 |
| [22] | J. Minker, On indefinite data bases and the closed world assumption, in:Proc. CADE-82 (1982) pp. 292-308. · Zbl 0481.68087 |
| [23] | R. Moore, Semantical considerations on nonmonotonic logic, Artificial Intelligence 25 (1985) 75-94. · Zbl 0569.68079 · doi:10.1016/0004-3702(85)90042-6 |
| [24] | W. Marek and M. Truszczy?ski, Modal logic for default reasoning, to appear. |
| [25] | L. Pereira, L. Caires and J. Alferes, Hypothetical reasoning with well founded semantics, in:Proc. 3rd Scand. Conf. on AI (1991). |
| [26] | H. Przymusinska and T. Przymusinski, Semantic issues in deductive databases and logic programs, in:Formal Techniques in Artificial Intelligence, ed. R. Manerji (North-Holland, Amsterdam, 1990) pp. 321-367. · Zbl 0704.68034 |
| [27] | T. Przymusinski, On the declarative semantics of deductive databases and logic programs, in:Foundations of Deductive Databases and Logic Programming, ed. J. Minker (Morgan Kaufmann, San Mateo, CA, 1988) pp. 193-216. · Zbl 0726.68067 |
| [28] | T. Przymusinski, Extended stable semantics for normal and disjunctive programs, in:Logic Programming: Proc. 7th Int. Conf., eds. D. Warren and P. Szeredi (1990) pp. 459-477. |
| [29] | D. Pearce and G. Wagner, Reasoning with negative information 1 ? strong negation in logic programming, Technical Report, Gruppe für Logic, Wissentheorie and Information, Freie Universität Berlin (1989). · Zbl 0746.03020 |
| [30] | R. Reiter, On closed world data bases, in:Logic and Data Bases, eds. H. Gallaire and J. Minker (Plenum, New York, 1978) pp. 119-140. |
| [31] | R. Reiter, A logic for default reasoning, Artificial Intelligence 13 (1980) 81-132. · Zbl 0435.68069 · doi:10.1016/0004-3702(80)90014-4 |
| [32] | R. Reiter, On asking what a database knows, in:Computational Logic: Symp. Proc, ed. J. Lloyd (Springer, 1990) pp. 96-113. |
| [33] | K. Ross and R. Topor, Inferring negative information from disjunctive databases, J. Automated Reasoning 4(4) (1988) 397-424. · Zbl 0662.68101 · doi:10.1007/BF00297247 |
| [34] | G. Wagner, Database needs two kinds of negation, in:Proc. MFDBS-91, Lecture Notes in Computer Science, 495 (1991). |
| [35] | L. Yahya and A. Henschen, Deduction in non-horn databases, J. Automated Reasoning 1 (1985) 141-160. · Zbl 0614.68072 · doi:10.1007/BF00244994 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
