Characterizing and extending answer set semantics using possibility theory
From MaRDI portal
Publication:4592973
Abstract: Answer Set Programming (ASP) is a popular framework for modeling combinatorial problems. However, ASP cannot easily be used 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, where 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.
Recommendations
- Semantics for possibilistic answer set programs: uncertain rules versus rules with uncertain conclusions
- A characterization of answer sets for logic programs
- Semantical characterizations and complexity of equivalences in answer set programming
- Relating and extending semantical approaches to possibilistic reasoning
- Extensions of answer set programming
- Extensions of answer set programming
- Symbolic and Quantitative Approaches to Reasoning with Uncertainty
- The joy of probabilistic answer set programming: semantics, complexity, expressivity, inference
Cites work
- scientific article; zbMATH DE number 25190 (Why is no real title available?)
- scientific article; zbMATH DE number 610968 (Why is no real title available?)
- scientific article; zbMATH DE number 1844513 (Why is no real title available?)
- A Simple Modal Logic for Reasoning about Revealed Beliefs
- A synthetic view of belief revision with uncertain inputs in the framework of possibility theory
- An alternative approach to the semantics of disjunctive logic programs and deductive databases
- Autoepistemic logic
- Disjunctive logic programs with inheritance
- Epistemic entrenchment and possibilistic logic
- Epistemic foundation of stable model semantics
- Knowledge Representation, Reasoning and Declarative Problem Solving
- Logic Programming
- Logic in Computer Science
- Manifold Answer-Set Programs for Meta-reasoning
- Nonmonotonic reasoning, conditional objects and possibility theory
- On the complexity of fragments of modal logics
- On the transformation between possibilistic logic bases and possibilistic causal networks
- Possibilistic nested logic programs
- Possibilistic uncertainty handling for answer set programming
- Probability Theory
- Revisiting Epistemic Specifications
- Semantical considerations on nonmonotonic logic
- Semantics for possibilistic disjunctive programs
- The Boolean Hierarchy I: Structural Properties
- Thirteen Definitions of a Stable Model
Cited in
(11)- Possibilistic nested logic programs and strong equivalence
- Semantics for possibilistic answer set programs: uncertain rules versus rules with uncertain conclusions
- Reasoning and learning in the setting of possibility theory -- overview and perspectives
- The Hurwicz Decision Rule’s Relationship to Decision Making with the Triangle and Beta Distributions and Exponential Utility
- A Generalised Approach for Encoding and Reasoning with Qualitative Theories in Answer Set Programming
- Logic programming
- Possibilistic uncertainty handling for answer set programming
- Generalized possibilistic logic: foundations and applications to qualitative reasoning about uncertainty
- Syntax and semantics of multi-adjoint normal logic programming
- The joy of probabilistic answer set programming: semantics, complexity, expressivity, inference
- Semantics for Possibilistic Disjunctive Programs
This page was built for publication: Characterizing and extending answer set semantics using possibility theory
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4592973)
