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 Conferência

Tipo de Documento
Artigo Completo

Título
Classical 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 classical generalized probabilistic satisfiability problem (GGenPSAT) which consists in deciding the satisfiability of Boolean combinations of linear inequalities involving probabilities of classical propositional formulas. GGenPSAT coincides precisely with the satisfiability problem of the probabilistic logic of Fagin et al. and was proved to be NP-complete. Here, we present a polynomial reduction of GGenPSAT to SMT over the quantifier-free theory of linear integer and real arithmetic. Capitalizing on this translation, we implement and test a solver for the GGenPSAT problem. As previously observed for many other NP-complete problems, we are able to detect a phase transition behavior for GGenPSAT.

Data de Publicação
2017-08

Evento
Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence

Identificadores da Publicação
ISBN - 9780999241103

Local
Melbourne, Australia

Editora
International Joint Conferences on Artificial Intelligence Organization

Identificadores do Documento
DOI - https://doi.org/10.24963/ijcai.2017/126
URL - http://dx.doi.org/10.24963/ijcai.2017/126

Identificadores de Qualidade
CORE A* (2017) -

Keywords
Satisfiability solver Probabilistic satisfiability Probabilistic reasoning Satisfiability problem


Exportar referência

APA
Carlos Caleiro, Filipe Casal, Andreia Mordido, (2017). Classical Generalized Probabilistic Satisfiability. Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, -

IEEE
Carlos Caleiro, Filipe Casal, Andreia Mordido, "Classical Generalized Probabilistic Satisfiability" in Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, Melbourne, Australia, 2017, pp. -, doi: 10.24963/ijcai.2017/126

BIBTEX
@InProceedings{35845, author = {Carlos Caleiro and Filipe Casal and Andreia Mordido}, title = {Classical Generalized Probabilistic Satisfiability}, booktitle = {Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence}, year = 2017, pages = {-}, address = {Melbourne, Australia}, publisher = {International Joint Conferences on Artificial Intelligence Organization} }