This paper introduces an abductive framework for updating knowledge bases represented by extended disjunctive programs. We first provide a simple transformation from abductive programs to update programs which are log...
详细信息
This paper introduces an abductive framework for updating knowledge bases represented by extended disjunctive programs. We first provide a simple transformation from abductive programs to update programs which are logic programs specifying changes on abductive hypotheses. Then, extended abduction, which was introduced by the same authors as a generalization of traditional abduction, is computed by the answer sets of update programs. Next, different types of updates, view updates and theory updates are characterized by abductive programs and computed by update programs. The task of consistency restoration is also realized as special cases of these updates. Each update problem is comparatively assessed from the computational complexity viewpoint. The result of this paper provides a uniform framework for different types of knowledge base updates, and each update is computed using existing procedures of logicprogramming.
The non-classical, nonmonotonic inference relation associated with the answer set semantics for logic programs gives rise to a relationship of strong equivalence between logical programs that can be verified in 3-valu...
详细信息
The non-classical, nonmonotonic inference relation associated with the answer set semantics for logic programs gives rise to a relationship of strong equivalence between logical programs that can be verified in 3-valued Godel logic, G3, the strongest non-classical intermediate propositional logic (Lifschitz et al., 2001). In this paper we will show that KC (the logic obtained by adding axiom -A boolean OR -A to intuitionistic logic), is the weakest intermediate logic for which strongly equivalent logic programs, in a language allowing negations, are logically equivalent.
Schlipf (1995) proved that Stable logicprogramming (SLP) solves all NP decision problems. We extend Schliprs result to prove that SLP solves all search problems in the class NP. Moreover, we do this in a uniform way ...
详细信息
Schlipf (1995) proved that Stable logicprogramming (SLP) solves all NP decision problems. We extend Schliprs result to prove that SLP solves all search problems in the class NP. Moreover, we do this in a uniform way as defined in Marek and Truszczynski (1991). Specifically, we show that there is a single DATALOG(-) program P-Trg such that given any Turing machine M, any polynomial p with non-negative integer coefficients and any input a of size n over a fixed alphabet Sigma, there is an extensional database edb(M,p,sigma) such that there is a one-to-one correspondence between the stable models of edb(M,p,sigma) boolean OR P-Trg and the accepting computations of the machine M that reach the final state in at most p(n) steps. Moreover, edb (M,p,sigma) can be computed in polynomial time from p, a and the description of M and the decoding of such accepting computations from its corresponding stable model of edb (M,***) boolean OR P-Trg can be computed in linear time. A similar statement holds for Default logic with respect to Sigma(2)(P)-search problems.(1).
We introduce a methodology and framework for expressing general preference information in logicprogramming under the answer set semantics. An ordered logic program is an extended logic program in which rules,are name...
详细信息
We introduce a methodology and framework for expressing general preference information in logicprogramming under the answer set semantics. An ordered logic program is an extended logic program in which rules,are named by unique terms, and in which preferences among rules are given by a set of atoms of form s < t where s and t are names. An ordered logic program is transformed into a second, regular, extended logic program wherein the preferences are respected, in that the answer sets obtained in the transformed program correspond with the preferred answer sets of the original program. Our approach allows the specification of dynamic orderings, in which preferences can appear arbitrarily within a program. Static orderings (in which preferences are external to a logic program) are a trivial restriction of the general dynamic case. First, we develop a specific approach to reasoning with preferences, wherein the preference ordering specifies the order in which rules are to be applied. We then demonstrate the wide range of applicability of our framework by showing how other approaches, among them that of Brewka and Eiter, can be captured within our framework. Since the result of each of these transformations is an extended logic program, we can make use of existing implementations, such as dlv and smodels. To this end, we have developed a publicly available compiler as a front-end for these programming systems.
We provide a semantic framework for preference handling in answer set programming. To this end, we introduce preference preserving consequence operators. The resulting fixpoint characterizations provide us with a unif...
详细信息
We provide a semantic framework for preference handling in answer set programming. To this end, we introduce preference preserving consequence operators. The resulting fixpoint characterizations provide us with a uniform semantic framework for characterizing preference handling in existing approaches. Although our approach is extensible to other semantics by means of an alternating fixpoint theory, we focus here on the elaboration of preferences under answer set semantics. Alternatively, we show how these approaches can be characterized by the concept of order preservation. These uniform semantic characterizations provide us with new insights about inter-relationships and moreover about ways of implementation.
Representing defeasibility is an important issue in common sense reasoning. In reasoning about action and change, this issue becomes more difficult because domain and action related defeasible information may conflict...
详细信息
Representing defeasibility is an important issue in common sense reasoning. In reasoning about action and change, this issue becomes more difficult because domain and action related defeasible information may conflict with general inertia rules. Furthermore, different types of defeasible information may also interfere with each other during the reasoning. In this paper, we develop a prioritized logicprogramming approach to handle defeasibilities in reasoning about action. In particular, we propose three action languages and AF(0), AF(1) and AF(2) which handle three types of defeasibilities in action domains named defeasible constraints, defeasible observations and actions with defeasible and abnormal effects respectively. Each language with a higher superscript can be viewed as an extension of the language with a lower superscript. These action languages inherit the simple syntax of A language but their semantics is developed in terms of transition systems where transition functions are defined based on prioritized logic programs. By illustrating various examples, we show that our approach eventually provides a powerful mechanism to handle various defeasibilities in temporal prediction and postdiction. We also investigate semantic properties of these three action languages and characterize classes of action domains that present more desirable solutions in reasoning about action within the underlying action languages.
An open ended list is a well known data structure in Prolog programs. It is frequently used to represent a value changing over time, while this value is referred to from several places in the data structure of the app...
详细信息
An open ended list is a well known data structure in Prolog programs. It is frequently used to represent a value changing over time, while this value is referred to from several places in the data structure of the application. A weak point in this technique is that the time complexity is linear in the number of updates to the value represented by the open ended list. In this programming pearl we present a variant of the open ended list, namely an open ended tree, with an update and access time complexity logarithmic in the number of updates to the value.
Most recently, Answer Set programming (ASP) has been attracting interest as a new paradigm for problem solving. An important aspect, for which several approaches have been presented, is the handling of preferences bet...
详细信息
Most recently, Answer Set programming (ASP) has been attracting interest as a new paradigm for problem solving. An important aspect, for which several approaches have been presented, is the handling of preferences between rules. In this paper, we consider the problem of implementing preference handling approaches by means of meta-interpreters in Answer Set programming. In particular, we consider the preferred answer set approaches by Brewka and Eiter, by Delgrande, Schaub and Tompits, and by Wang, Zhou and Lin. We present suitable meta-interpreters for these semantics using DLV, which is an efficient engine for ASP. Moreover, we also present a meta-interpreter for the weakly preferred answer set approach by Brewka and Eiter, which uses the weak constraint feature of DLV as a tool for expressing and solving an underlying optimization problem. We also consider advanced meta-interpreters, which make use of graph-based characterizations and often allow for more efficient computations. Our approach shows the suitability of ASP in general and of DLV in particular for fast prototyping. This can be fruitfully exploited for experimenting with new languages and knowledge-representation formalisms.
This paper describes learning in a compiler for algorithms solving classes of the logic minimization problem MINSAT, where the underlying propositional formula is in conjunctive normal form (CNF) and where costs are a...
详细信息
This paper describes learning in a compiler for algorithms solving classes of the logic minimization problem MINSAT, where the underlying propositional formula is in conjunctive normal form (CNF) and where costs are associated with the True/False values of the variables. Each class consists of all instances that may be derived from a given propositional formula and costs for True/False values by fixing or deleting variables, and by deleting clauses. The learning step begins once the compiler has constructed a solution algorithm for a given class. The step applies that algorithm to comparatively few instances of the class, analyses the performance of the algorithm on these instances, and modifies the underlying propositional formula, with the goal that the algorithm will perform much better on all instances of the class.
The search for an appropriate characterization of negation as failure inlogic programs in the mid 1980s led to several proposals. Amongst them the stable model semantics -later referred to as answer set semantics, and...
详细信息
The search for an appropriate characterization of negation as failure inlogic programs in the mid 1980s led to several proposals. Amongst them the stable model semantics -later referred to as answer set semantics, and the well-founded semantics are the most popular andwidely referred ones. According to the latest (September 2002) list of most cited source documentsin the CiteSeer database (http://***) the original stable model semantics paper(Gelfond and Lifschitz, 1988) is ranked 10th with 649 citations and the well-founded semantics paper(Van Gelder et al., 1991) is ranked 70th with 306 citations. Since 1988 - when stable modelssemantics was proposed - there has been a large body of work centered around logic programs withanswer set semantics covering topics such as: systematic program development, systematic programanalysis, knowledge representation, declarative problem solving, answer set computing algorithms,complexity and expressiveness, answer set computing systems, relation with other nonmonotonic andknowledge representation formalisms, and applications to various tasks. This large body ofbuilding-block results makes logicprogramming with answer sets (sometimes called A-Prolog orAnsProlog) an attractive and suitable language for declarative programming, knowledgerepresentation, and further development. In this direction, the new millennium has seen an AAAISymposium (Spring 2001), a Dagstuhl seminar (in 2002), and the publication of the first textbook onthe topic (Baral, 2003). This special issues follows those events.
暂无评论