The complexity of Bayesian networks specified by propositional and relational languages

DOI10.1016/J.ARTINT.2018.06.001zbMath1451.68257arXiv1612.01120OpenAlexW2560444858WikidataQ62046506 ScholiaQ62046506MaRDI QIDQ1711881

Fabio G. Cozman, Denis Deratani Mauá

Publication date: 18 January 2019

Published in: Artificial Intelligence (Search for Journal in Brave)

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

zbMATH Keywords

Bayesian networkscomplexity theoryrelational logicplate modelsprobabilistic relational models

Mathematics Subject Classification ID

Database theory (68P15) Logic in artificial intelligence (68T27) Probabilistic graphical models (62H22)

Related Items (4)

The joy of probabilistic answer set programming: semantics, complexity, expressivity, inference ⋮ A structured view on weighted counting with relations to counting, quantum computation and applications ⋮ Some thoughts on knowledge-enhanced machine learning ⋮ The finite model theory of Bayesian network specifications: descriptive complexity and zero/one laws

Uses Software

• MEBN
• BUGS
• IBAL
• MayBMS
• KnowRob
• PR-OWL
• BLOG
• BayesOWL
• Trio

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of weighted and unweighted \(\#\)CSP
• Negative probabilities in probabilistic logic programs
• The complexity of computing the permanent
• Answering queries from context-sensitive probabilistic knowledge bases
• Elements of finite model theory.
• Complexity of DNF minimization and isomorphism testing for monotone formulas
• Managing and mining uncertain data
• The complexity of combinatorial problems with succinct input representation
• Complexity results for classes of quantificational formulas
• Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P
• Probabilistic Horn abduction and Bayesian networks
• The independent choice logic for modelling multiple agents under uncertainty
• Holographic reduction, interpolation and hardness
• The complexity of problems for quantified constraints
• Complex probabilistic modeling with recursive relational Bayesian networks
• A complexity theory for feasible closure properties
• MEBN: a language for first-order Bayesian knowledge bases
• On probabilistic inference by weighted model counting
• The effect of combination functions on the complexity of relational Bayesian networks
• PRL: a probabilistic relational language
• Soft computing in ontologies and semantic web.
• Subtractive reductions and complete problems for counting complexity classes
• Phase transitions of PP-complete satisfiability problems
• On the hardness of approximate reasoning
• The Complexity of Counting in Sparse, Regular, and Planar Graphs
• FPTAS for Counting Weighted Edge Covers
• The Necessity of Bounded Treewidth for Efficient Inference in Bayesian Networks
• Polynomial Space Counting Problems
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• Probabilistic Databases
• The Bayesian Description Logic ${\mathcal{BEL}}$
• PP is as Hard as the Polynomial-Time Hierarchy
• A differential approach to inference in Bayesian networks
• Logical and Relational Learning
• Modeling and Reasoning with Bayesian Networks
• The DL-Lite Family and Relations
• The Complexity of Enumeration and Reliability Problems
• Computational Complexity of Probabilistic Turing Machines
• Complexity classes defined by counting quantifiers
• Lower complexity bounds for lifted inference
• Inference and learning in probabilistic logic programs using weighted Boolean formulas
• The Parameterized Complexity of Counting Problems
• 10.1162/jmlr.2003.3.4-5.993
• A note on succinct representations of graphs
• Asymptotic Conditional Probabilities: The Unary Case
• On the Semantics and Complexity of Probabilistic Logic Programs
• A Simple FPTAS for Counting Edge Covers
• Bayesian Networks
• Inductive Logic Programming
• The dichotomy of probabilistic inference for unions of conjunctive queries
• The Independent Choice Logic and Beyond
• Algorithmic Learning Theory
• Theory and Applications of Models of Computation

This page was built for publication: The complexity of Bayesian networks specified by propositional and relational languages