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.

本文研究基于 Sato 分布语义的概率逻辑程序，分析了基于稳定和基于良基模型这两种语义，探讨了 credal 语义产生的概率模型集合是无限单调 Choquet 容量的结果产生的几个有用的结果，并研究了其推理和查询的复杂度。作者对此进行了详细说明，并对无环、分层、周期性的命题和关系程序，提出了推理和查询复杂度的结果，该复杂度达到各种计数层次和指数级别。