Answer Set Programming (ASP) is a popular framework for modelling combinatorial problems. However, ASP cannot be used easily for reasoning about uncertain information. Possibilistic ASP (PASP) is an extension of ASP that combines possibilistic logic and ASP. In PASP a weight is associated with each rule, whereas this weight is interpreted as the certainty with which the conclusion can be established when the body is known to hold. As such, it allows us to model and reason about uncertain information in an intuitive way. In this paper we present new semantics for PASP in which rules are interpreted as constraints on possibility distributions. Special models of these constraints are then identified as possibilistic answer sets. In addition, since ASP is a special case of PASP in which all the rules are entirely certain, we obtain a new characterization of ASP in terms of constraints on possibility distributions. This allows us to uncover a new form of disjunction, called weak disjunction, that has not been previously considered in the literature. In addition to introducing and motivating the semantics of weak disjunction, we also pinpoint its computational complexity. In particular, while the complexity of most reasoning tasks coincides with standard disjunctive ASP, we find that brave reasoning for programs with weak disjunctions is easier.
This paper presents an extension of Disjunctive Datalog (DATALOG sup V, spl sim ) by integrity constraints. These are of two types: strong, that is, classical integrity constraints and weak, that is, constraints that are satisfied if possible. While strong constraints must be satisfied, weak constraints express desiderata, that is, they may be violated-actually, their semantics tends to minimize the number of violated instances of weak constraints. Weak constraints may be ordered according to their importance to express different priority levels. As a result, the proposed language (call it, DATALOG sup V, spl sim ,c ) is well-suited to represent common sense reasoning and knowledge-based problems arising in different areas of computer science such as planning, graph theory optimizations, and abductive reasoning. The formal definition of the language is first given. The declarative semantics of DATALOG sup V, spl sim ,c is defined in a general way that allows us to put constraints on top of any existing (model-theoretic) semantics for DATALOG sup V, spl sim programs. Knowledge representation issues are then addressed and the complexity of reasoning on DATALOG sup V, spl sim ,c programs is carefully determined. An in-depth discussion on complexity and expressiveness of DATALOG sup V, spl sim ,c is finally reported. The discussion contrasts DATALOG sup V, spl sim ,c to DATALOG sup V, spl sim and highlights the significant increase in knowledge modeling ability carried out by constraints. In answer-set programming (ASP), the main focus usually is on computing answer sets which correspond to solutions to the problem represented by a logic program. Simple reasoning over answer sets is sometimes supported by ASP systems (usually in the form of computing brave or cautious consequences), but slightly more involved reasoning problems require external postprocessing. Generally speaking, it is often desirable to use (a subset of) brave or cautious consequences of a program P 1 as input to another program P 2 in order to provide the desired solutions to the problem to be solved. In practice, the evaluation of the program P 1 currently has to be decoupled from the evaluation of P 2 using an intermediate step which collects the desired consequences of P 1 and provides them as input to P 2 . In this work, we present a novel method for representing such a procedure within a single program, and thus within the realm of ASP itself. Our technique relies on rewriting P 1 into a so-called manifold program , which allows for accessing all desired consequences of P 1 within a single answer set. Then, this manifold program can be evaluated jointly with P 2 avoiding any intermediate computation step. For determining the consequences within the manifold program we use weak constraints , which is strongly motivated by complexity considerations. As an application, we present an encoding for computing the ideal extension of an abstract argumentation framework.