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

(38)

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