The descriptive complexity of Bayesian network specifications

Fabio G. Cozman; Denis D. Mauá

doi:10.1007/978-3-319-61581-3_9

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 congreso › Contribució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 original	Inglés estadounidense
Título de la publicación alojada	The descriptive complexity of Bayesian network specifications
Páginas	93-103
Número de páginas	11
ISBN (versión digital)	9783319615806
DOI	https://doi.org/10.1007/978-3-319-61581-3_9
Estado	Publicada - 1 ene 2017
Publicado de forma externa	Sí
Evento	Lecture 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

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

Conferencia

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

Acceder al documento

10.1007/978-3-319-61581-3_9

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

@inproceedings{60aa75661cf540e3b2c262ba49031464,

title = "The descriptive complexity of Bayesian network specifications",

abstract = "{\textcopyright} 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.",

author = "Cozman, {Fabio G.} and Mau{\'a}, {Denis D.}",

year = "2017",

month = jan,

day = "1",

doi = "10.1007/978-3-319-61581-3_9",

language = "American English",

isbn = "9783319615806",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "93--103",

booktitle = "The descriptive complexity of Bayesian network specifications",

note = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) ; Conference date: 01-01-2018",

}

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

The descriptive complexity of Bayesian network specifications. / Cozman, Fabio G.; Mauá, Denis D.

The descriptive complexity of Bayesian network specifications. 2017. p. 93-103 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10369 LNAI).

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

TY - GEN

T1 - The descriptive complexity of Bayesian network specifications

AU - Cozman, Fabio G.

AU - Mauá, Denis D.

PY - 2017/1/1

Y1 - 2017/1/1

N2 - © 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.

AB - © 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.

UR - https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85025146815&origin=inward

UR - https://www.scopus.com/inward/citedby.uri?partnerID=HzOxMe3b&scp=85025146815&origin=inward

U2 - 10.1007/978-3-319-61581-3_9

DO - 10.1007/978-3-319-61581-3_9

M3 - Conference contribution

SN - 9783319615806

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 93

EP - 103

BT - The descriptive complexity of Bayesian network specifications

T2 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Y2 - 1 January 2018

ER -