The descriptive complexity of Bayesian network specifications

Fabio G. Cozman, Denis D. Mauá

Resultado de la investigación: Capítulo del libro/informe/acta de congresoContribución a la conferencia

2 Citas (Scopus)

Resumen

© Springer International Publishing AG 2017. We adapt the theory of descriptive complexity to Bayesian networks, by investigating how expressive can be specifications based on predicates and quantifiers. We show that Bayesian network specifications that employ first-order quantification capture the complexity class PP; that is, any phenomenon that can be simulated with a polynomial time probabilistic Turing machine can be also modeled by such a network. We also show that, by allowing quantification over predicates, the resulting Bayesian network specifications capture the complexity class PPNP, a result that does not seem to have equivalent in the literature.
Idioma originalInglés estadounidense
Título de la publicación alojadaThe descriptive complexity of Bayesian network specifications
Páginas93-103
Número de páginas11
ISBN (versión digital)9783319615806
DOI
EstadoPublicada - 1 ene 2017
Publicado de forma externa
EventoLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) -
Duración: 1 ene 2018 → …

Serie de la publicación

NombreLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volumen10369 LNAI
ISSN (versión impresa)0302-9743

Conferencia

ConferenciaLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Período1/01/18 → …

Huella Profundice en los temas de investigación de 'The descriptive complexity of Bayesian network specifications'. En conjunto forman una huella única.

  • Citar esto

    Cozman, F. G., & Mauá, D. D. (2017). The descriptive complexity of Bayesian network specifications. En The descriptive complexity of Bayesian network specifications (pp. 93-103). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10369 LNAI). https://doi.org/10.1007/978-3-319-61581-3_9