析取封闭世界假设的一种过程语义

析取信息的表示是一个重要的研究问题.DCWA(析取封闭假设)为一般演绎数据库提供了一种谨慎语义,并且扩充了标准的良基语义.同时DCWA支持争论推理,为广义封闭世界假设提供了一种逼近.基于此,提出了DCWA的过程语义,并证明了它的可靠性和完备性.     

An Extension to GCWA and Query Evaluation for Disjunctive Deductive Databases

We present a simple and intuitive extension GCWA^G of the generalized closed world assumption (GCWA) from positive disjunctive deductive databases to general disjunctive deductive databases (with default negation). This semantics is defined in terms of unfounded sets and possesses an argumentation-theoretic characterization. We also provide a top-down procedure for GCWA^G, which is sound and complete with respect to GCWA^G. We investigate two query evaluation methods for GCWA^G: database partition, and database splitting. The basic idea of these methods is to divide the original deductive database into several smaller sub-databases and the query evaluation in the original database is transformed into the problem of query evaluation in smaller or simplified components. We prove that these two methods of query evaluation are all sound with respect to GCWA^G.     

A possible world semantics for disjunctive databases

The fundamental problem that arises when a ground atom in a disjunctive database is assumed false is discussed. There are basically two different approaches for inferring negative information for disjunctive databases: J. Minker's (1982) generalized closed world assumption (GCWA) and K.A. Ross and R.W. Topor's (1988) disjunctive database rule (DDR). It is argued that neither approach is satisfactory. A database semantics called PWS is proposed. It is shown that for propositional databases with no negative clauses, the problem of determining if a negative ground literal is inferred under the GCWA is co-NP-hard, while the same problem can be solved efficiently under the DDR and PWS. However, in the general case, the problem becomes co-NP-complete for the DDR and PWS. Relationships among GCWA, DDR, and PWS are highlighted. In general, disjunctive clauses are interpreted inclusively under the DDR and unpredictably under the GCWA     

Inferring negative information from disjunctive databases

We propose criteria that any rule for inferring negative information from disjunctive databases should satisfy, and examine existing rules from this viewpoint. We then present a new inference rule, the ‘disjunctive database rule’ (DDR), and compare it to the existing rules with respect to the criteria. In particular, the DDR is equivalent to the CWA for definite databases, it infers no more negative information than the GCWA, and it interprets disjunction inclusively rather than exclusively. We generalize the DDR to a class of layered databases, describe an implementation of the DDR, ‘negation as positive failure’, and study its soundness and completeness properties.     

Weak Generalized Closed World Assumption

Explicit representation of negative information in logic programs is not feasible in many applications such as deductive databases and artificial intelligence. Defining default rules which allow implicit inference of negated facts from positive information encoded in a logic program has been an attractive alternative to the explicit representation approach. There is, however, a difficulty associated with implicit default rules. Default rules such as the CWA and the GCWA, which closely model logical negation, are in general computationally intractable. This has led to the development of weaker definitions of negation such as the Negation-As-Failure (NF) and the Support-For-Negation (SN) rules which are computationally simpler. These are sound implementations of the CWA and the GCWA, respectively. In this paper, we define an alternative rule of negation based upon the fixpoint definition of the GCWA. This rule, called the Weak Generalized Closed World Assumption (WGCWA), is a weaker definition of the GCWA that allows us to implement a sound negation rule, called the Negation-As-Finite-Failure (NAFF), similar to the NF-rule and less cumbersome than the SN-rule. We present three definitions of the NAFF. Two declarative definitions similar to those for the NF-rule and one procedural definition based on SLI-resolution.     

Classical negation in logic programs and disjunctive databases

An important limitation of traditional logic programming as a knowledge representation tool, in comparison with classical logic, is that logic programming does not allow us to deal directly with incomplete information. In order to overcome this limitation, we extend the class of general logic programs by including classical negation, in addition to negation-as-failure. The semantics of such extended programs is based on the method of stable models. The concept of a disjunctive database can be extended in a similar way. We show that some facts of commonsense knowledge can be represented by logic programs and disjunctive databases more easily when classical negation is available. Computationally, classical negation can be eliminated from extended programs by a simple preprocessor. Extended programs are identical to a special case of default theories in the sense of Reiter.     

Logic programming and reasoning with incomplete information

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 rulesT and formulaF, KF stands for F is known to be true by a reasoner with a set of premisesT and MF 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 will 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.     

Overview of disjunctive logic programming

The field of disjunctive programming started approximately in 1982 and has reached its first decade. The first result in the field was the development of the Generalized Closed World Assumption (GCWA). Major results have been made in this field since 1986. An overview is presented of the developments that have taken place, which include model theoretic, proof theoretic and fixpoint semantics for disjunctive, and extended normal disjunctive theories including alternative forms of negation.Dedicated to Chitta Baral, José Alberto Fernández, Jorge Lobo and Arcot Rajasekar.     

Default logic as a query language

Research in nonmonotonic reasoning has focused largely on the idea of representing knowledge about the world via rules that are generally true but can be defeated. Even if relational databases are nowadays the main tool for storing very large sets of data, the approach of using nonmonotonic AI formalisms as relational database query languages has been investigated to a much smaller extent. In this work, we propose a novel application of Reiter's default logic by introducing a default query language (DQL) for finite relational databases, which is based on default rules. The main result of this paper is that DQL is as expressive as SO_∃∀ the existential-universal fragment of second-order logic. This result is not only of theoretical importance: We exhibit queries-which are useful in practice-that can be expressed with DQL and cannot with other query languages based on nonmonotonic logics such as DATALOG with negation under the stable model semantics. In particular, we show that DQL is well-suited for diagnostic reasoning     

Logic knowledge bases with two default rules

Logic knowledge based systems (LKBS) containing at most one form of default negation and explicit (or “classical”) negation have been studied in the literature. In this paper we describe a class of LKBS containing multiple forms of default negation in addition to explicit negation. We define a semantics for these systems in terms of the well‐founded semantics defined by Van Gelder et al. (1988) and the stable semantics introduced by Gelfond and Lifschitz (1988) and later extended to the 3‐valued case by Przymusinski (1991). We investigate properties of the new combined semantics and calculate the computational complexity of three main reasoning tasks for this semantics, namely existence of models, skeptical and credulous reasoning. An effective procedure to construct the collection of models characterizing the semantics of such a system is given. Applications to knowledge representation and knowledge base merging are presented. This revised version was published online in June 2006 with corrections to the Cover Date.     

On the computational cost of disjunctive logic programming: Propositional case

This paper addresses complexity issues for important problems arising with disjunctive logic programming. In particular, the complexity of deciding whether a disjunctive logic program is consistent is investigated for a variety of well-known semantics, as well as the complexity of deciding whether a propositional formula is satisfied by all models according to a given semantics. We concentrate on finite propositional disjunctive programs with as well as without integrity constraints, i.e., clauses with empty heads; the problems are located in appropriate slots of the polynomial hierarchy. In particular, we show that the consistency check is ₂ ^p -complete for the disjunctive stable model semantics (in the total as well as partial version), the iterated closed world assumption, and the perfect model semantics, and we show that the inference problem for these semantics is ₂ ^p -complete; analogous results are derived for the answer sets semantics of extended disjunctive logic programs. Besides, we generalize previously derived complexity results for the generalized closed world assumption and other more sophisticated variants of the closed world assumption. Furthermore, we use the close ties between the logic programming framework and other nonmonotonic formalisms to provide new complexity results for disjunctive default theories and disjunctive autoepistemic literal theories.Parts of the results in this paper appeared in form of an abstract in the Proceedings of the Twelfth ACM SIGACT SIGMOD-SIGART Symposium on Principles of Database Systems (PODS-93), pp. 158–167. Other parts appeared in shortened form in the Proceedings of the International Logic Programming Symposium, Vancouver, October 1993 (ILPS-93), pp. 266–278. MIT Press.     

An alternative approach to the semantics of disjunctive logic programs and deductive databases

In this paper, we study a new semantics of logic programming and deductive databases. Thepossible model semantics is introduced as a declarative semantics of disjunctive logic programs. The possible model semantics is an alternative theoretical framework to the classical minimal model semantics and provides a flexible inference mechanism for inferring negation in disjunctive logic programs. We also present a proof procedure for the possible model semantics and show that the possible model semantics has an advantage from the computational complexity point of view.This is a revised and extended version of the paper [36] which was presented at the Tenth International Conference on Logic Programming, Budapest, 21–25 June 1993.     

Model theoretic approach to view updates in deductive databases

The view update problem for deductive databases has been defined as the problem of accomplishing the update of an intensional predicate by modifying appropriately the extensional database. A previous paper by Grant, Horty, Lobo, and Minker developed algorithms for the insertion and the deletion of an intensional predicate in certain important classes of stratified disjunctive deductive databases. This paper introduces a model theoretic approach which encompasses a wide class of Herbrand semantics, including the perfect model and stable model semantics, for disjunctive databases including negation. This generalizes the earlier results: now the intensional database may contain disjunctive and denial rules, and the database may be required to satisfy integrity constraints. As in the previous paper, the algorithms are proved to be correct and best according to the criterion of causing minimal change to the database, where the first priority is to minimize deletions.     

'Classical' Negation in Nonmonotonic Reasoning and Logic Programming

Gelfond and Lifschitz were the first to point out the need for a symmetric negation in logic programming and they also proposed a specific semantics for such negation for logic programs with the stable semantics, which they called 'classical'. Subsequently, several researchers proposed different, often incompatible, forms of symmetric negation for various semantics of logic programs and deductive databases. To the best of our knowledge, however, no systematic study of symmetric negation in non-monotonic reasoning was ever attempted in the past. In this paper we conduct such a systematic study of symmetric negation. We introduce and discuss two natural, yet different, definitions of symmetric negation: one is called strong negation and the other is called explicit negation. For logic programs with the stable semantics, both symmetric negations coincide with Gelfond–Lifschitz' 'classical negation'. We study properties of strong and explicit negation and their mutual relationship as well as their relationship to default negation 'not', and classical negation '¬'. We show how one can use symmetric negation to provide natural solutions to various knowledge representation problems, such as theory and interpretation update, and belief revision. Rather than to limit our discussion to some narrow class of nonmonotonic theories, such as the class of logic programs with some specific semantics, we conduct our study so that it is applicable to a broad class of non-monotonic formalisms. In order to achieve the desired level of generality, we define the notion of symmetric negation in the knowledge representation framework of AutoEpistemic logic of Beliefs, introduced by Przymusinski.     

A logic-based calculus of events

We outline an approach for reasoning about events and time within a logic programming framework. The notion of event is taken to be more primitive than that of time and both are represented explicitly by means of Horn clauses augmented with negation by failure. The main intended applications are the updating of databases and narrative understanding. In contrast with conventional databases which assume that updates are made in the same order as the corresponding events occur in the real world, the explicit treatment of events allows us to deal with updates which provide new information about the past. Default reasoning on the basis of incomplete information is obtained as a consequence of using negation by failure. Default conclusions are automatically withdrawn if the addition of new information renders them inconsistent. Because events are differentiated from times, we can represent events with unknown times, as well as events which are partially ordered and concurrent.     

Graph theoretical structures in logic programs and default theories

In this paper we present a graph representation of logic programs and default theories. We show that many of the semantics proposed for logic programs with negation can be expressed in terms of notions emerging from graph theory, establishing in this way a link between the fields. Namely the stable models, the partial stable models, and the well-founded semantics correspond respectively to the kernels, semikernels and the initial acyclic part of an associated graph. This link allows us to consider both theoretical (existence, uniqueness) and computational problems (tractability, algorithms, approximations) from a more abstract and rather combinatorial point of view. It also provides a clear and intuitive understanding about how conflicts between rules are resolved within the different semantics. Furthermore, we extend the basic framework developed for logic programs to the case of Default Logic by introducing the notions of partial, deterministic and well-founded extensions for default theories. These semantics capture different ways of reasoning with a default theory.     

On the relationship between annotated logic programs and nonmonotonic formalisms

Abstract

In the past we developed a semantics for a restricted annotated logic language for inheritance reasoning. Here we generalize it to annotated Horn logic programs. We first provide a formal account of the language, describe its semantics, and provide an interpreter written in Prolog for it. We then investigate its relationship to Belnap's 4-valued logic, Gelfond and Lifschitz's semantics for logic programs with negation, Brewka's prioritized default logics and other annotated logics due to Kifer et al.     

Logic programs with exceptions

We extend logic programming to deal with default reasoning by allowing the explicit representation of exceptions in addition to general rules. To formalise this extension, we modify the answer set semantics of Gelfond and Lifschitz, which allows both classical negation and negation as failure. We also propose a transformation which eliminates exceptions by using negation by failure. The transformed program can be implemented by standard logic programming methods, such as SLDNF. The explicit representation of rules and exceptions has the virtue of greater naturalness of expression. The transformed program, however, is easier to implement.