On the semantics and complexity of probabilistic logic programs
From MaRDI portal
Publication:5371012
DOI10.1613/JAIR.5482zbMATH Open1418.68027arXiv1701.09000OpenAlexW2584623985MaRDI QIDQ5371012FDOQ5371012
Authors: Fabio Gagliardi Cozman, D. D. Maua 
Publication date: 24 October 2017
Published in: Journal of Artificial Intelligence Research (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1701.09000
Recommendations
Cited In (31)
- P-log: refinement and a new coherency condition
- A credal extension of independent choice logic
- Improving the efficiency of Gibbs sampling for probabilistic logical models by means of program specialization
- On the implementation of the probabilistic logic programming language ProbLog
- Probabilistic logic programming with conditional constraints
- Combining probability and logic: papers from Progic 2011
- Probabilities on sentences in an expressive logic
- A semantics for hybrid probabilistic logic programs with function symbols
- Special issue on probabilistic logic programming (PLP 2018)
- A probabilistic semantics for belief logic
- Languages for probabilistic modeling over structured and relational domains
- Hybrid probabilistic logic programs as residuated logic programs
- Title not available (Why is that?)
- Complexity Results for Probabilistic Datalog
- Modularity of P-log programs
- Probabilistic logic programming
- Well–definedness and efficient inference for probabilistic logic programming under the distribution semantics
- Logic Programming and Nonmonotonic Reasoning
- Syntactic requirements for well-defined hybrid probabilistic logic programs
- Using histograms to better answer queries to probabilistic logic programs
- Title not available (Why is that?)
- Logic Programming
- Title not available (Why is that?)
- The joy of probabilistic answer set programming: semantics, complexity, expressivity, inference
- Open-world probabilistic databases: semantics, algorithms, complexity
- Thirty years of credal networks: specification, algorithms and complexity
- The complexity of Bayesian networks specified by propositional and relational languages
- Compositionality of Probabilistic Hennessy-Milner Logic through Structural Operational Semantics
- Statistical statements in probabilistic logic programming
- The finite model theory of Bayesian network specifications: descriptive complexity and zero/one laws
- Complexity results for probabilistic answer set programming
This page was built for publication: On the semantics and complexity of probabilistic logic programs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5371012)
