On the relationship between circumscription and negation as failure. (English) Zbl 0663.68097
The aim of this paper is to investigate two powerful methods of handling negative information in logic-based knowledge representation systems: the logical minimization in the form of circumscription and the negation as failure rule, formalized by various closures (or completions) of original theories. We suggest a new, more powerful form of the negation as failure rule and describe an important class of theories for which this form of negation as failure is equivalent to particular forms of circumscription. These results establish a close relationship between the two important formalizations of nonmonotonic reasoning and provide a syntactic characterization of the corresponding circumscriptive theories. This allows us to apply existing methods of deduction using various negation as failure rules to answering queries in a broad class of circumscriptive theories.
MSC:
| 68T99 | Artificial intelligence |
Keywords:
negative information; logic-based knowledge representation systems; circumscription; negation as failure; nonmonotonic reasoningReferences:
| [1] | Apt, K.; Blair, H.; Walker, A., Towards a theory of declarative knowledge, (Minker, J., Foundations of Deductive Databases and Logic Programming (1988), Morgan Kaufmann: Morgan Kaufmann Los Altos), 89-148 |
| [2] | Bossu, G.; Siegel, P., Saturation, nonmonotonic reasoning and the closed world assumption, Artificial Intelligence, 25, 13-63 (1985) · Zbl 0569.68078 |
| [3] | Chandra, A.; Harel, D., Horn clause queries and generalizations, J. Logic Program., 1, 1-15 (1985) · Zbl 0583.68058 |
| [4] | Clark, K. L., Negation as failure, (Gallaire, H.; Minker, J., Logic and Data Bases (1978), Plenum Press: Plenum Press New York), 293-322 |
| [5] | Etherington, D., Reasoning with incomplete information, investigations of non-monotonic reasoning, (Ph.D. Thesis (1986), Department of Computer Science, University of British Columbia: Department of Computer Science, University of British Columbia Vancouver, BC) |
| [6] | Etherington, D.; Mercer, R.; Reiter, R., On the adequacy of predicate circumscription for closed-world reasoning, Comput. Intell., 1, 11-15 (1985) |
| [7] | Fitting, M., A Kripke-Kleene semantics for logic programs, J. Logic Program., 4, 295-312 (1985) · Zbl 0589.68011 |
| [8] | Gabbay, D., Modal provability foundations for negation as failure I (1986), Preprint |
| [9] | Gelfond, M.; Przymusinska, H., Negation as failure: Careful closure procedure, Artificial Intelligence, 30, 273-287 (1986) · Zbl 0635.68119 |
| [10] | Gelfond, M.; Pryzymusinska, H., On the relationship between autoepistemic logic and parallel circumscription, (Proceedings ACM SIGART International Symposium on Methodologies for Intelligent Systems. Proceedings ACM SIGART International Symposium on Methodologies for Intelligent Systems, Knoxville, TN (1986)), 256-262 |
| [11] | Gelfond, M.; Przymusinska, H.; Przymusinski, T., The extended closed world assumption and its relationship to parallel circumscription, (Proceedings ACM SIGACT-SIGMOD Symposium on Principles of Database Systems. Proceedings ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, Cambridge, MA (1986)), 133-139 |
| [12] | Gelfond, M., Przymusinska, H. and Pryzymusinski, T., On the relationship between circumscription and negation as failure II (in preparation).; Gelfond, M., Przymusinska, H. and Pryzymusinski, T., On the relationship between circumscription and negation as failure II (in preparation). |
| [13] | Grant, J.; Minker, J., Answering queries in indefinite databases and the null value problem (1986), Preprint |
| [14] | Hewitt, C., Description and theoretical analysis (using schemata) of PLANNER: A language for proving theorems and manipulating models in a robot, AI Memo 251, MIT Project MAC, Cambridge, MA.; Hewitt, C., Description and theoretical analysis (using schemata) of PLANNER: A language for proving theorems and manipulating models in a robot, AI Memo 251, MIT Project MAC, Cambridge, MA. |
| [15] | Imielinski, T., Results on translating defaults to circumscription, Artificial Intelligence, 32, 131-146 (1987) · Zbl 0667.03014 |
| [16] | Lifschitz, V., On the declarative semantics of logic programs with negation, (Minker, J., Foundations of Deductive Databases and Logic Programming (1988), Morgan Kaufmann: Morgan Kaufmann Los Altos, CA) · Zbl 0718.68019 |
| [17] | Lifschitz, V., Computing circumscription, (Proceedings IJCAI-85. Proceedings IJCAI-85, Los Angeles, CA (1985)), 121-127 |
| [18] | Lifschitz, V., Pointwise circumscription, (Proceedings AAAI-86. Proceedings AAAI-86, Philadelphia, PA (1986)), 406-410 |
| [19] | Lifschitz, V., Closed-world databases and circumscription, Artificial Intelligence, 27, 229-235 (1985) · Zbl 0596.68062 |
| [20] | Lloyd, J. W., Foundations of Logic Programming (1984), Springer: Springer Berlin · Zbl 0547.68005 |
| [21] | McCarthy, J., Circumscription—A form of non-monotonic reasoning, Artificial Intelligence, 13, 27-39 (1980) · Zbl 0435.68073 |
| [22] | McCarthy, J., Applications of circumscription to formalizing common-sense knowledge, Artificial Intelligence, 28, 89-116 (1986) |
| [23] | McDermott, D., Non-monotonic logic II: Non-monotonic modal theories, J. ACM, 29, 1, 33-57 (1982) · Zbl 0477.68099 |
| [24] | McDermott, D.; Doyle, J., Non-monotonic logic I, Artificial Intelligence, 13, 41-72 (1980) · Zbl 0435.68074 |
| [25] | Minker, J., On indefinite data bases and the closed world assumption, (Proceedings Sixth Conference on Automated Deduction (1982)), 292-308 · Zbl 0481.68087 |
| [26] | Moore, R. C., Semantic considerations on nonmonotonic logic, Artificial Intelligence, 25, 75-94 (1985) · Zbl 0569.68079 |
| [27] | Naqvi, S. A., A logic for negation in database systems (1986), Preprint |
| [28] | Przymusinski, T., On the declarative and procedural semantics of stratified deductive databases, (Minker, J., Foundations of Deductive Databases and Logic Programming (1988), Morgan Kaufmann: Morgan Kaufmann Los Altos, CA), 193-216 · Zbl 0726.68067 |
| [29] | Przymusinski, T., Query answering in circumscriptive and closed-world theories, (Proceedings AAAI-86. Proceedings AAAI-86, Philadelphia, PA (1986)), 186-190 |
| [30] | Przymusinski, T., An algorithm to compute circumscription, Artificial Intelligence, 38, 49-73 (1989), (this issue) · Zbl 0663.68098 |
| [31] | Reiter, R., Towards a logical reconstruction of relational database theory, (Brodie, M.; etal., On Conceptual Modeling (1984), Springer: Springer Berlin) |
| [32] | Reiter, R., On closed-world data bases, (Gallaire, H.; Minker, J., Logic and Data Bases (1978), Plenum Press: Plenum Press New York), 55-76 |
| [33] | Reiter, R., A logic for default reasoning, Artificial Intelligence, 13, 81-132 (1980) · Zbl 0435.68069 |
| [34] | Reiter, R., Circumscription implies predicate completion (sometimes), (Proceedings AAAI-82. Proceedings AAAI-82, Pittsburgh, PA (1982)), 418-420 |
| [35] | Roussel, P., PROLOG, manuel de reference et d’utilisation (1985), Group d’Intelligence Artificielle, U.E.R. de Marseille: Group d’Intelligence Artificielle, U.E.R. de Marseille France |
| [36] | Shepherdson, J., Negation as failure: A comparison of Clarke’s completed data bases and Reiter’s closed world assumption, J. Logic Program., 1, 1, 51-79 (1984) · Zbl 0575.68094 |
| [37] | van Emden, M. H.; Kowalski, R. A., The semantics of predicate logic as a programming language, J. ACM, 3, 4, 733-742 (1976) · Zbl 0339.68004 |
| [38] | van Gelder, A., Negation as failure using tight derivations for general logic programs, (Minker, J., Foundations of Deductive Databases and Logic Programming (1988), Morgan Kaufmann: Morgan Kaufmann Los Altos, CA), 149-176 · Zbl 0726.68065 |
| [39] | Yahya, A.; Henschen, L., Deduction in non-Horn databases, J. Autom. Reasoning, 1, 2, 141-160 (1985) · Zbl 0614.68072 |
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.
