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

Probabilistic Answer Set Programming (PASP) combines rules, facts, and independent probabilistic facts. We 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.