Title: On the Semantics and Complexity of Probabilistic Logic Programs,
Abstract: We examine the meaning and the complexity of probabilistic logic programs
that consist of a set of rules and a set of independent probabilistic facts
(that is, programs based on Sato's distribution semantics). We focus on two
semantics, respectively based on stable and on well-founded models. We show
that the semantics based on stable models (referred to as the "credal
semantics") produces sets of probability models that dominate infinitely
monotone Choquet capacities, we describe several useful consequences of this
result. We then examine the complexity of inference with probabilistic logic
programs. We distinguish between the complexity of inference when a
probabilistic program and a query are given (the inferential complexity), and
the complexity of inference when the probabilistic program is fixed and the
query is given (the query complexity, akin to data complexity as used in
database theory). We obtain results on the inferential and query complexity for
acyclic, stratified, and cyclic propositional and relational programs,
complexity reaches various levels of the counting hierarchy and even
exponential levels.