The joy of Probabilistic Answer Set Programming: Semantics, complexity, expressivity, inference

Abstract Probabilistic Answer Set Programming (PASP) combines rules, facts, and independent probabilistic facts. We review several combinations of logic programming and probabilities, and argue that a very useful modeling paradigm is obtained by adopting a particular semantics for PASP, where one associates a credal set with each consistent program. We examine the basic properties of PASP under this credal semantics, in particular presenting novel results on its complexity and its expressivity, and we introduce an inference algorithm to compute (upper) probabilities given a program.