R231  
Probabilistic Inference Modulo Theories
Rodrigo de Salvo Braz, Ciaran O'Reilly, Vibhav Gogate, and Rina Dechter

Abstract
We present SGDPLL(T), an algorithm that solves
(among many other problems) probabilistic inference
modulo theories, that is, inference problems
over probabilistic models defined via a logic theory
provided as a parameter (currently, propositional,
equalities on discrete sorts, and inequalities,
more specifically difference arithmetic, on
bounded integers). While many solutions to probabilistic
inference over logic representations have
been proposed, SGDPLL(T) is simultaneously (1)
lifted, (2) exact and (3) modulo theories, that is,
parameterized by a background logic theory. This
offers a foundation for extending it to rich logic
languages such as data structures and relational
data. By lifted, we mean algorithms with constant
complexity in the domain size (the number
of values that variables can take). We also detail
a solver for summations with difference arithmetic
and show experimental results from a scenario in
which SGDPLL(T) is much faster than a stateoftheart
probabilistic solver.
[pdf] 