# On the Semantics and Complexity of Probabilistic Logic Programs

arXiv: https://arxiv.org/abs/1701.09000 · HTML: https://mlsanity.com/paper/1701.09000/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Jan 2017.

## Built on by (most cited first, 9 of 9)

- [A Compositional Atlas for Algebraic Circuits](https://mlsanity.com/paper/2412.05481/) (2024)
- [smProbLog: Stable Model Semantics in ProbLog for Probabilistic Argumentation](https://mlsanity.com/paper/2304.00879/) (2023)
- [SMProbLog: Stable Model Semantics in ProbLog and its Applications in Argumentation](https://mlsanity.com/paper/2110.01990/) (2021)
- [Scaling the weight parameters in Markov logic networks and relational logistic regression models](https://mlsanity.com/paper/2103.15140/) (2021)
- [Syntactic Requirements for Well-defined Hybrid Probabilistic Logic Programs](https://mlsanity.com/paper/2109.08283/) (2021)
- [Think Smart, Act SMARL! Analyzing Probabilistic Logic Shields for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2411.04867/) (2024)
- [Probabilistic Answer Set Programming with Discrete and Continuous Random Variables](https://mlsanity.com/paper/2409.20274/) (2024)
- [A Distribution Semantics for Probabilistic Term Rewriting](https://mlsanity.com/paper/2410.15081/) (2024)
- [Integrating Belief Domains into Probabilistic Logic Programs](https://mlsanity.com/paper/2507.17291/) (2025)

## Abstract (arXiv)

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.