Hybrid Probabilistic Programs: Algorithms and Complexity
| dc.contributor.author | Dekhtyar, Michael | en_US |
| dc.contributor.author | Dekhtyar, Alex | en_US |
| dc.contributor.author | Subrahmanian, V.S. | en_US |
| dc.date.accessioned | 2004-05-31T22:55:07Z | |
| dc.date.available | 2004-05-31T22:55:07Z | |
| dc.date.created | 1998-12 | en_US |
| dc.date.issued | 1998-12-18 | en_US |
| dc.description.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) | en_US |
| dc.format.extent | 286014 bytes | |
| dc.format.mimetype | application/postscript | |
| dc.identifier.uri | http://hdl.handle.net/1903/987 | |
| dc.language.iso | en_US | |
| dc.relation.isAvailableAt | Digital Repository at the University of Maryland | en_US |
| dc.relation.isAvailableAt | University of Maryland (College Park, Md.) | en_US |
| dc.relation.isAvailableAt | Tech Reports in Computer Science and Engineering | en_US |
| dc.relation.isAvailableAt | UMIACS Technical Reports | en_US |
| dc.relation.ispartofseries | UM Computer Science Department; CS-TR-3969 | en_US |
| dc.relation.ispartofseries | UMIACS; UMIACS-TR-98-76 | en_US |
| dc.title | Hybrid Probabilistic Programs: Algorithms and Complexity | en_US |
| dc.type | Technical Report | en_US |