Hybrid Probabilistic Programs: Algorithms and Complexity
Files
Publication or External Link
Date
Advisor
Citation
DRUM DOI
Abstract
Hybrid Probabilistic Programs (HPPs) are logic programs that allow the
programmer to explicitly encode his knowledge of the dependencies between
events being described in the program. In this paper, we classify HPPs
into three classes called HPP_1,HPP_2 and HPP_r for r >= 3. For these
classes, we provide three types of results for HPPs. First, we develop
algorithms to compute the set of all ground consequences of an HPP. Then
we provide algorithms and complexity results for the problems of
entailment (Given an HPP P and a query Q as input, is Q a logical consequence of P?'') and consistency (
Given an HPP P as input, is P
consistent?''). Our results provide a fine characterization of when
polynomial algorithms exist for the above problems, and when these
problems become intractable.
(Also cross-referenced as UMIACS-TR-98-76)