On the semantics and complexity of probabilistic logic programs

DOI10.1613/JAIR.5482MaRDI QIDQ5371012zbMATH OpenOpenAlexFDO

Authors Fabio Gagliardi Cozman, D. D. Maua

Publication date 24 October 2017

Published in Journal of Artificial Intelligence Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1701.09000

Mathematics Subject Classification ID

Logic programming (68N17) Semantics in the theory of computing (68Q55)

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.

Recommendations

• The complexity of inferences and explanations in probabilistic logic programming
• Complexity results for probabilistic answer set programming
• Probabilistic logic programming with conditional constraints
• Probabilistic logic programming
• Logic Programming and Nonmonotonic Reasoning

Cited in

(39)

• Probabilistic logic programming
• The complexity of Bayesian networks specified by propositional and relational languages
• Hybrid probabilistic logic programs as residuated logic programs
• On the complexity of inference about probabilistic relational models
• A probabilistic semantics for belief logic
• The joy of probabilistic answer set programming: semantics, complexity, expressivity, inference
• Thirty years of credal networks: specification, algorithms and complexity
• Special issue on probabilistic logic programming (PLP 2018)
• A semantics for hybrid probabilistic logic programs with function symbols
• Open-world probabilistic databases: semantics, algorithms, complexity
• The finite model theory of Bayesian network specifications: descriptive complexity and zero/one laws
• Complexity results for probabilistic answer set programming
• P-log: refinement and a new coherency condition
• The complexity of inferences and explanations in probabilistic logic programming
• Combining probability and logic: papers from Progic 2011
• Probabilities on sentences in an expressive logic
• Statistical statements in probabilistic logic programming
• Improving the efficiency of Gibbs sampling for probabilistic logical models by means of program specialization
• Compositionality of Probabilistic Hennessy-Milner Logic through Structural Operational Semantics
• Modularity of P-log programs
• On the implementation of the probabilistic logic programming language ProbLog
• scientific article; zbMATH DE number 4152345 (Why is no real title available?)
• Probabilistic logic programming with conditional constraints
• Complexity Results for Probabilistic Datalog
• Using histograms to better answer queries to probabilistic logic programs
• Negative probabilities in probabilistic logic programs
• scientific article; zbMATH DE number 7102019 (Why is no real title available?)
• Well–definedness and efficient inference for probabilistic logic programming under the distribution semantics
• Logic Programming and Nonmonotonic Reasoning
• Logic Programming
• scientific article; zbMATH DE number 7649893 (Why is no real title available?)
• An Asymptotic Analysis of Probabilistic Logic Programming, with Implications for Expressing Projective Families of Distributions
• A credal extension of independent choice logic
• Languages for probabilistic modeling over structured and relational domains
• Syntactic requirements for well-defined hybrid probabilistic logic programs
• A distribution semantics for probabilistic term rewriting
• Scaling the weight parameters in Markov logic networks and relational logistic regression models
• Probabilistic answer set programming with discrete and continuous random variables
• \textsc{sm}ProbLog: stable model semantics in ProbLog for probabilistic argumentation

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)