Generalized probabilistic satisfiability through integer programming

Glauber De Bona, Fabio G. Cozman, Marcelo Finger

Resultado de la investigación: Contribución a una revistaArtículo

4 Citas (Scopus)

Resumen

© 2015, De Bona et al. Background: This paper studies the generalized probabilistic satisfiability (GPSAT) problem, where the probabilistic satisfiability (PSAT) problem is extended by allowing Boolean combinations of probabilistic assertions and nested probabilistic formulas. Methods: We introduce a normal form for this problem and show that both nesting of probabilities and multi-agent probabilities do not increase the expressivity of GPSAT. An algorithm to solve GPSAT instances in the normal form via mixed integer linear programming is proposed. Results: The implementation of the algorithm is used to explore the complexity profile of GPSAT, and it shows evidence of phase-transition phenomena. Conclusions: Even though GPSAT is considerably more expressive than PSAT, it can be handled using integer linear programming techniques.
Idioma originalInglés estadounidense
PublicaciónJournal of the Brazilian Computer Society
DOI
EstadoPublicada - 29 dic 2015
Publicado de forma externa

Huella Profundice en los temas de investigación de 'Generalized probabilistic satisfiability through integer programming'. En conjunto forman una huella única.

  • Citar esto