Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

The finite model theory of Bayesian network specifications: Descriptive complexity and zero/one laws

Texto completo
Autor(es):
Cozman, Fabio Gagliardi [1] ; Maua, Denis Deratani [2]
Número total de Autores: 2
Afiliação do(s) autor(es):
[1] Univ Sao Paulo, Escola Politecn, Sao Paulo - Brazil
[2] Univ Sao Paulo, Inst Matemat & Estat, Sao Paulo - Brazil
Número total de Afiliações: 2
Tipo de documento: Artigo Científico
Fonte: INTERNATIONAL JOURNAL OF APPROXIMATE REASONING; v. 110, n. SI, p. 107-126, JUL 2019.
Citações Web of Science: 0
Resumo

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. (C) 2019 Elsevier Inc. All rights reserved. (AU)

Processo FAPESP: 16/18841-0 - Algoritmos para inferência e aprendizado de programas lógicos probabilísticos
Beneficiário:Fabio Gagliardi Cozman
Linha de fomento: Auxílio à Pesquisa - Parceria para Inovação Tecnológica - PITE
Processo FAPESP: 15/21880-4 - PROVERBS -- sistemas booleanos probabilísticos Super-restritos: ferramentas de raciocínio e aplicações
Beneficiário:Marcelo Finger
Linha de fomento: Auxílio à Pesquisa - Regular