Generalized Probabilistic Satisfiability.

This paper studies the Generalized Probabilistic Satisfiability (GPSAT) problem, where the probabilistic satisfiability problem is extended by allowing Boolean combinations of probabilistic assertions and nested probabilistic formulas. We introduce a normal form for this problem and show that nesting of probabilities does not increase the expressivity in GPSAT. An algorithm to solve GPSAT problems via mixed integer programming is proposed, and its implementation shows evidence of phase-transition phenomena. [ABSTRACT FROM PUBLISHER]