BIBLIOS

   Ciências References Management System

Visitor Mode (Login)
Need help?


Back

Publication details

Document type
Conference papers

Document subtype
Full paper

Title
Classical Generalized Probabilistic Satisfiability

Participants in the publication
Carlos Caleiro (Author)
Filipe Casal (Author)
Dep. Informática
 LASIGE
 Andreia Mordido (Author)
Dep. Informática
 LASIGE
Summary
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.

Date of Publication
2017-08

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

Publication Identifiers
ISBN - 9780999241103

Address
Melbourne, Australia

Publisher
International Joint Conferences on Artificial Intelligence Organization

Document Identifiers
DOI - https://doi.org/10.24963/ijcai.2017/126
URL - http://dx.doi.org/10.24963/ijcai.2017/126

Rankings
CORE A* (2017) -

Keywords
Satisfiability solver Probabilistic satisfiability Probabilistic reasoning Satisfiability problem


Export

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} }