Epistemic extensions of answer set programming

but due to the non-monotonic nature of ASP; the weight can reflect the certainty that the rule itself is correct. ASP programs with incorrect rules may have erroneous conclusions; omitting a correct rule may also lead to errors. To derive the most certain conclusions from an uncertain ASP program; the weight can reflect the certainty with which we can conclude the head of a rule when its body is satisfied. This corresponds with how the weight is understood when defining semantics for PASP in terms of constraints on possibility distributions. On the other hand; we highlight how the weight attached to a rule in PASP can be interpreted in different ways. On the one hand; some decision problems are easier. Thirdly; while the complexity of most reasoning tasks coincides with disjunction in ordinary ASP; called weak disjunction; that has not been previously considered in the ASP literature. When examining the complexity of weak disjunction we unearth that; we obtain a new characterization of ASP in terms of constraints on possibility distributions. This allows us to uncover a new form of disjunction; since ASP is a special case of PASP in which all the rules are entirely certain; we show how semantics for PASP can be defined in terms of constraints on possibility distributions. These new semantics adhere to a different intuition for negation-as-failure than current work on PASP to avoid unintuitive conclusions in specific settings. In addition; 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. Secondly; where each program in the sequence may successively remove some of the remaining models. This mimics a sequence of leaders; we modify the communication mechanism to also allow us to focus on a sequence of communicating programs; it is shown that the addition of this easy form of communication allows us to move one step up in the polynomial hierarchy. Furthermore; i.e. they can communicate. For the least complex variant of ASP; simple programs; one ASP program can conceptually query another program as to whether it believes some literal to be true or not; which is a framework that allows us to study the formal properties of communication and the complexity of the resulting system in ASP. It is based on an extension of ASP in which we consider a network of ordinary ASP programs. These communicating programs are extended with a new kind of literal based on the notion of asking questions. As such; we introduce Communicating Answer Set Programming (CASP); namely Possibilistic Answer Set Programming (PASP); there are contexts in which the current semantics for PASP lead to unintuitive results. In this thesis we address these issues in the followings ways. Firstly; ASP lacks the means to easily model and reason about uncertain information. While extensions of ASP have been proposed to deal with uncertainty; where each context encodes a different aspect of the real world. Extensions of ASP have been proposed to model such multi-context systems; but the exact effect of communication on the overall expressiveness remains unclear. In addition; it is not an ideal framework to model common-sense reasoning. For example; in ASP we cannot model multi-context systems; while ASP similarly allows us to revise knowledge; we conclude that the bird can fly. When new knowledge becomes available (e.g. the bird is a penguin) we may need to retract conclusions. However; in common-sense reasoning; Answer Set Programming (ASP) is a declarative programming language based on the stable model semantics and geared towards solving complex combinatorial problems. The strength of ASP stems from the use of a non-monotonic operator. This operator allows us to retract previously made conclusions as new information becomes available. Similarly; we may arrive at conclusions based on the absence of information. When an animal is for example a bird; and we do not know that this bird is a penguin; we thus need to consider all situations in which some; none; or all of the least certain rules are omitted. This corresponds to treating some rules as optional and reasoning about which conclusions remain valid regardless of the inclusion of these optional rules. Semantics for PASP are introduced based on this idea and it is shown that some interesting problems in Artificial Intelligence can be expressed in terms of optional rules. For both CASP and the new semantics for PASP we show that most of the concepts that we introduced can be simulated using classical ASP. This provides us with implementations of these concepts and furthermore allows us to benefit from the performance of state-of-the-art ASP solvers.

Toegankelijkheid:Open