BIBLIOS

   Sistema de Gestão de Referências Bibliográficas de Ciências

Modo Visitante (Login)
Need help?


Voltar

Detalhes Referência

Tipo
Artigos em Revista

Tipo de Documento
Artigo Completo

Título
Generalized Probabilistic Satisfiability

Participantes na publicação
Carlos Caleiro (Author)
Filipe Casal (Author)
Dep. Informática
 LASIGE
 Andreia Mordido (Author)
Dep. Informática
 LASIGE
Resumo
We analyze a generalized probabilistic satisfiability problem (GenPSAT) which consists in deciding the satisfiability of linear inequalities involving probabilities of classical propositional formulas. GenPSAT is proved to be NP-complete and we present a polynomial reduction to Mixed-Integer Programming. Capitalizing on this translation, we implement and test a solver for the GenPSAT problem. As previously observed for many other NP-complete problems, we are able to detect a phase transition behaviour for GenPSAT.

Data de Publicação
2017-06

Suporte
Electronic Notes in Theoretical Computer Science

Identificadores da Publicação
ISSN - 1571-0661

Editora
Elsevier BV

Volume
332

Número de Páginas
17
Página Inicial
39
Página Final
56

Identificadores do Documento
DOI - https://doi.org/10.1016/j.entcs.2017.04.004
URL - http://dx.doi.org/10.1016/j.entcs.2017.04.004

Identificadores de Qualidade
SCIMAGO Q2 (2016) - 0.261 - Computer Science (miscellaneous)

Keywords
Probabilistic Satisfiability GenPSAT Mixed-Integer Programming Phase Transition


Exportar referência

APA
Carlos Caleiro, Filipe Casal, Andreia Mordido, (2017). Generalized Probabilistic Satisfiability. Electronic Notes in Theoretical Computer Science, 332, 39-56. ISSN 1571-0661. eISSN . http://dx.doi.org/10.1016/j.entcs.2017.04.004

IEEE
Carlos Caleiro, Filipe Casal, Andreia Mordido, "Generalized Probabilistic Satisfiability" in Electronic Notes in Theoretical Computer Science, vol. 332, pp. 39-56, 2017. 10.1016/j.entcs.2017.04.004

BIBTEX
@article{35843, author = {Carlos Caleiro and Filipe Casal and Andreia Mordido}, title = {Generalized Probabilistic Satisfiability}, journal = {Electronic Notes in Theoretical Computer Science}, year = 2017, pages = {39-56}, volume = 332 }