Abstract 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.

Abstract Answer set programming (ASP) is a form of declarative programming that allows to succinctly formulate and efficiently solve complex problems. An intuitive extension of this formalism is communicating ASP, in which multiple ASP programs collaborate to solve the problem at hand. However, the expressiveness of communicating ASP has not been thoroughly studied. In this paper, we present a systematic study of the additional expressiveness offered by allowing ASP programs to communicate. First, we consider a simple form of communication where programs are only allowed to ask questions to each other. For the most part, we deliberately consider only simple programs, i.e. programs for which computing the answer sets is in P. We find that the problem of deciding whether a literal is in some answer set of a communicating ASP program using simple communication is NP-hard. In other words, due to the ability of these simple ASP programs to communicate and collaborate, we move up a step in the polynomial hierarchy. Second, we modify the communication mechanism to also allow us to focus on a sequence of communicating programs, where each program in the sequence may successively remove some of the remaining models. This mimics a network of leaders, where the first leader has the first say and may remove models that he or she finds unsatisfactory. Using this particular communication mechanism allows us to capture the entire polynomial hierarchy. This means, in particular, that communicating ASP could be used to solve problems that are above the second level of polynomial hierarchy, such as some forms of abductive reasoning as well as PSPACE-complete problems such as STRIPS planning.

Answer set programming (ASP) and possibility theory can be combined to form possibilistic answer set programming (PASP), a framework for non-monotonic reasoning under uncertainty. Existing proposals view answer sets of PASP programs as weighted epistemic states, in which the strength by which different literals are believed to hold may vary. In contrast, in this paper we propose an approach in which epistemic states remain Boolean, but some epistemic states may be considered more plausible than others. A PASP program is then a representation of an incomplete description of these epistemic states where certainties are associated with each rule which is interpreted in terms of a necessity measure. The main contribution of this paper is the introduction of a new semantics for PASP as well as a study of the resulting complexity.

In this article, we introduce fuzzy equilibrium logic as a generalization of both Pearce equilibrium logic and fuzzy answer set programming. The resulting framework combines the capability of equilibrium logic to declaratively specify search problems, with the capability of fuzzy logics to model continuous domains. We show that our fuzzy equilibrium logic is a proper generalization of both Pearce equilibrium logic and fuzzy answer set programming, and we locate the computational complexity of the main reasoning tasks at the second level of the polynomial hierarchy. We then provide a reduction from the problem of finding fuzzy equilibrium logic models to the problem of solving a particular bilevel mixed integer program (biMIP), allowing us to implement reasoners by reusing existing work from the operations research community. To illustrate the usefulness of our framework from a theoretical perspective, we show that a well-known characterization of strong equivalence in Pearce equilibrium logic generalizes to our setting, yielding a practical method to verify whether two fuzzy answer set programs are strongly equivalent. Finally, to illustrate its application potential, we show how fuzzy equilibrium logic can be used to find strong Nash equilibria, even when players have a continuum of strategies at their disposal. As a second application example, we show how to find abductive explanations from Łukasiewicz logic theories.

Abstract In recent years, answer set programming (ASP) has been extended to deal with multivalued predicates. The resulting formalismsallow for the modeling of continuous problems as elegantly as ASP allows for the modeling of discrete problems, by combining thestable model semantics underlying ASP with fuzzy logics. However, contrary to the case of classical ASP where manyefficient solvers have been constructed, to date there is no efficient fuzzy ASP solver. A well-knowntechnique for classical ASP consists of translating an ASP programPto a propositional theory whose models exactlycorrespond to the answer sets ofP. In this paper, we show how this idea can be extended to fuzzy ASP, paving the wayto implement efficient fuzzy ASP solvers that can take advantage of existing fuzzy logic reasoners.

In this paper we propose the use of answer set programming (ASP) to model protein interaction networks. We argue that this declarative formalism rivals the popular boolean networks in terms of ease of use, while at the same time being more expressive. As we demonstrate for the particularcase of a fission yeast network, all information present in a boolean network, as well as relevant background assumptions,can be expressed explicitly in an answer set program. Moreover, readily available answer set solvers can then be used to find the stable states of the network.

Open answer set programming (OASP) is an extension of answer set programming where one may ground a program with an arbitrary superset of the program's constants. We define a fixed-point logic (FPL) extension of Clark's completion such that open answer sets correspond to models of FPL formulas and identify a syntactic subclass of programs, called (loosely)guarded programs. Whereas reasoning with general programs in OASP is undecidable, the FPL translation of (loosely) guarded programs falls in the decidable (loosely) guarded fixed-point logic (μ(L)GF). Moreover, we reduce normal closed ASP to loosely guarded OASP, enabling, for the first time, a characterization of an answer set semantics by μLGF formulas. We further extend the open answer set semantics for programs with generalized literals. Suchgeneralized programs (gPs)have interesting properties, for example, the ability to express infinity axioms. We restrict the syntax of gPs such that both rules and generalized literals areguarded. Via a translation to guarded fixed-point logic, we deduce 2-EXPTIME-completeness of satisfiability checking in suchguarded gPs(GgPs).Bound GgPsare restricted GgPs with EXPTIME-complete satisfiability checking, but still sufficiently expressive to optimally simulatecomputation tree logic(CTL). We translate Datalog lite programs to GgPs, establishing equivalence of GgPs under an open answer set semantics, alternation-free μGF, and Datalog LITE.

We extend answer set semantics to deal with inconsistent programs (containing classical negation), by finding a “best” answer set. Within the context of inconsistent programs, it is natural to have a partial order on rules, representing a preference for satisfying certain rules, possibly at the cost of violating less important ones. We show that such a rule order induces a natural order on extended answer sets, the minimal elements of which we call preferred answer sets. We characterize the expressiveness of the resulting semantics and show that it can simulate negation as failure, disjunction and some other formalisms such as logic programs with ordered disjunction. The approach is shown to be useful in several application areas, e.g. repairing database, where minimal repairs correspond to preferred answer sets.

We propose a semantics for disjunctive logic programs, based on the single notion of forcing. We show that the semantics properly extends, in a natural way, previous approaches. A fixpoint characterization is also provided. We also take a closer look at the relationship between disjunctive logic programs and disjunctive‐free logic programs. We present certain criteria under which a disjunctive program is semantically equivalent with its disjunctive‐free (shifted) version.

We suggest a so-called 'robust' semantics for a model of argumentation which represents arguments and their interactions, called 'argumentation frameworks'. We study a variety of additional definitions of acceptability of arguments; we explore the properties of these definitions; we describe their interrelationships: e.g. robust models can be characterized using the minimal (well-founded) models of a meta-framework. The various definitions of acceptability of argument sets can all deal with contradiction within an argumentation framework. Key words: Argumentation framework, semantics

Ordered logic programming is an extension of logic programming that includes, besides classical inference mechanisms, object-oriented abstractions and amenities for non- monotonic reasoning. Ordered logic programs are partially-ordered sets of ‘traditional’ logic programs where negation may also occur in the rule heads. The central issue of this paper is the definition of a new unifying semantics for ordered logic programs, called assumption-free semantics, capable of capturing different interesting semantics such as the well-founded and stable (partial model) semantics. It turns out that every ordered logic program possesses exactly one minimal assumption-free partial model which we call the well-founded partial model and one or more maximal assumption-free partial models called stable partial models. This stable model semantics can be viewed as taking the best of the previous approaches for ordered logic programs while keeping their (common) underlying intuition. We discuss the relationship between stable and well-founded partial models, the main result being that the intersection of all stable partial models is exactly the well-founded partial model in all cases but a special type of ordered logic programs.

An extension of logic programming, called “ordered logic programming”, which includes some abstractions of the object-oriented paradigm, is presented. An ordered program consists of a number of modules (objects), where each module is composed by a number of rules possibly with negated head predicates. A sort of “isa” hierarchy can be defined among the modules in order to allow for rule inheritance. Therefore, every module sees its own rules as local rules and the rules of the other modules to which it is connected by the “isa” hierarchy as global rules. In this way, as local rules may hide global rules, it is possible to deal with default properties and exceptions. This new approach represents a novel attempt to combine the logic paradigm with the object-oriented one in knowledge base systems. Moreover, this approach provides a new ground for explaining some recent proposals of semantics for classical logic programs with negation in the rule bodies and gives an interesting semantics to logic programs with negated rule heads.

We develop semantics for a logic, called ordered logic (OL), which models the most important aspects of object-oriented programming languages, such as object identity, multiple inheritance and defaults. The logic is based on a partially ordered structure of logical theories, which play the role of objects. OL is non-monotonic under the natural modeltheoretic semantics. A non-deterministic procedure is defined that has all models as fixpoints. It is shown that, for a well-behaved subclass of theories, this procedure can be used to generate exactly the set of ‘preferred’ models, where preference is based on the lack of ‘assumptions’. Classical logic programs with negation by failure are special cases of OL theories. From the above we can then derive a syntactic characterization of logic programs with stable models.

In this paper we present a user interface to the KIWI object oriented database system. The system combines ease of use with a powerful customisation facility which greatly simplifies the development of end-user applications. This is achieved by using the underlying object-oriented language (OOPS+) features such as inheritance to define a consistent and orthogonal set of graphical object classes that can be used to attach a tailor-made external representation of (a view on) objects and/or classes. In addition, using the same tools, it becomes a simple matter to define general purpose browsing and manipulation tools which otherwise would have to be developed separately.

This paper studies an extension of the notion of a finite index ETOL system. It turns out that by setting some quite natural restrictions on the set of bare derivation trees of an ETOL system (that is derivation trees stripped of labels) one can characterize languages of finite rank. Several properties of the new class of ETOL systems are investigated; in particular their relationship to ETOL systems of finite rank and ETOL systems of finite index is investigated.