On the semantics and complexity of probabilistic logic programs

DOI10.1613/JAIR.5482zbMATH Open1418.68027OpenAlexW2584623985MaRDI 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)

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

(34)

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

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)