The finite model theory of Bayesian networks: Descriptive complexity

Fabio Gagliardi Cozman, Denis Deratani Mauá

Resultado de la investigación: Contribución a una conferenciaArtículo de conferencia

Resumen

© 2018 International Joint Conferences on Artificial Intelligence.All right reserved. We adapt the theory of descriptive complexity to encompass Bayesian networks, so as to quantify the expressivity of Bayesian network specifications based on predicates and quantifiers. We show that Bayesian network specifications that employ first-order quantification capture the complexity class PP; by allowing quantification over predicates, the resulting Bayesian network specifications capture each class in the hierarchy PPNP...NP , a result that does not seem to have equivalent in the literature.
Idioma originalInglés estadounidense
Páginas5229-5233
Número de páginas5
DOI
EstadoPublicada - 1 ene 2018
Publicado de forma externa
EventoIJCAI International Joint Conference on Artificial Intelligence -
Duración: 1 ene 2018 → …

Conferencia

ConferenciaIJCAI International Joint Conference on Artificial Intelligence
Período1/01/18 → …

Huella Profundice en los temas de investigación de 'The finite model theory of Bayesian networks: Descriptive complexity'. En conjunto forman una huella única.

  • Citar esto

    Cozman, F. G., & Mauá, D. D. (2018). The finite model theory of Bayesian networks: Descriptive complexity. 5229-5233. Papel presentado en IJCAI International Joint Conference on Artificial Intelligence, . https://doi.org/10.24963/ijcai.2018/727