Characterizing and extending answer set semantics using possibility theory

DOI10.1017/S147106841300063XzbMATH Open1379.68041arXiv1312.0127OpenAlexW2104448458MaRDI QIDQ4592973FDOQ4592973

Dirk Vermeir, Kim Bauters, Martine De Cock, Steven Schockaert

Publication date: 9 November 2017

Published in: Theory and Practice of Logic Programming (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1312.0127

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

zbMATH Keywords

answer set programminglogic programmingpossibility theory

Mathematics Subject Classification ID

Reasoning under uncertainty in the context of artificial intelligence (68T37) Logic programming (68N17)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Knowledge Representation, Reasoning and Declarative Problem Solving
• Probability Theory
• Logic in Computer Science
• On the transformation between possibilistic logic bases and possibilistic causal networks
• Revisiting Epistemic Specifications
• Thirteen Definitions of a Stable Model
• Autoepistemic logic
• The Boolean Hierarchy I: Structural Properties
• Semantical considerations on nonmonotonic logic
• Epistemic entrenchment and possibilistic logic
• Logic Programming
• Nonmonotonic reasoning, conditional objects and possibility theory
• A Simple Modal Logic for Reasoning about Revealed Beliefs
• A synthetic view of belief revision with uncertain inputs in the framework of possibility theory
• Title not available (Why is that?)
• Possibilistic uncertainty handling for answer set programming
• Epistemic foundation of stable model semantics
• Title not available (Why is that?)
• An alternative approach to the semantics of disjunctive logic programs and deductive databases
• Disjunctive logic programs with inheritance
• Manifold Answer-Set Programs for Meta-reasoning
• Semantics for possibilistic disjunctive programs
• Title not available (Why is that?)

Cited In (7)

• Possibilistic nested logic programs and strong equivalence
• 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
• Generalized possibilistic logic: foundations and applications to qualitative reasoning about uncertainty
• Syntax and semantics of multi-adjoint normal logic programming

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)