TY - JOUR
T1 - The finite model theory of Bayesian network specifications: Descriptive complexity and zero/one laws
AU - Cozman, Fabio Gagliardi
AU - Mauá, Denis Deratani
PY - 2019/7/1
Y1 - 2019/7/1
N2 - © 2019 Elsevier Inc. This paper studies specification languages that describe Bayesian networks using predicates and other logical constructs. First, we adopt an abstract syntax for relational Bayesian network specifications, and review definability and complexity results. We then propose a novel framework to study the descriptive complexity of relational Bayesian network specifications, and show that specifications based on function-free first-order logic capture the complexity class PP; we also exhibit specification languages, based on second-order quantification, that capture the hierarchy of complexity classes PPNP…NP, a result that does not seem to have equivalent in the literature. Finally, we derive zero/one laws for Bayesian network specifications based on function-free first-order logic, indicating their value in definability analysis.
AB - © 2019 Elsevier Inc. This paper studies specification languages that describe Bayesian networks using predicates and other logical constructs. First, we adopt an abstract syntax for relational Bayesian network specifications, and review definability and complexity results. We then propose a novel framework to study the descriptive complexity of relational Bayesian network specifications, and show that specifications based on function-free first-order logic capture the complexity class PP; we also exhibit specification languages, based on second-order quantification, that capture the hierarchy of complexity classes PPNP…NP, a result that does not seem to have equivalent in the literature. Finally, we derive zero/one laws for Bayesian network specifications based on function-free first-order logic, indicating their value in definability analysis.
UR - https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85064933017&origin=inward
UR - https://www.scopus.com/inward/citedby.uri?partnerID=HzOxMe3b&scp=85064933017&origin=inward
U2 - 10.1016/j.ijar.2019.04.003
DO - 10.1016/j.ijar.2019.04.003
M3 - Article
SP - 107
EP - 126
JO - International Journal of Approximate Reasoning
JF - International Journal of Approximate Reasoning
SN - 0888-613X
ER -