Probability Aggregates in Probability Answer Set Programming

Preprint English OPEN
Saad, Emad (2013)
  • Subject: Computer Science - Artificial Intelligence

Probability answer set programming is a declarative programming that has been shown effective for representing and reasoning about a variety of probability reasoning tasks. However, the lack of probability aggregates, e.g. {\em expected values}, in the language of disjunctive hybrid probability logic programs (DHPP) disallows the natural and concise representation of many interesting problems. In this paper, we extend DHPP to allow arbitrary probability aggregates. We introduce two types of probability aggregates; a type that computes the expected value of a classical aggregate, e.g., the expected value of the minimum, and a type that computes the probability of a classical aggregate, e.g, the probability of sum of values. In addition, we define a probability answer set semantics for DHPP with arbitrary probability aggregates including monotone, antimonotone, and nonmonotone probability aggregates. We show that the proposed probability answer set semantics of DHPP subsumes both the original probability answer set semantics of DHPP and the classical answer set semantics of classical disjunctive logic programs with classical aggregates, and consequently subsumes the classical answer set semantics of the original disjunctive logic programs. We show that the proposed probability answer sets of DHPP with probability aggregates are minimal probability models and hence incomparable, which is an important property for nonmonotonic probability reasoning.
  • References (18)
    18 references, page 1 of 2

    [Burdick et al., 2007] D. Burdick, P. Deshpande, T.S. Jayram, R. Ramakrishnan, and S. Vaithyanathan. Olap over uncertain and imprecise data. VLDB, 16(1):123-144, 2007.

    [Faber et al., 2010] W. Faber, N. Leone, and G. Pfeifer. Semantics and complexity of recursive aggregates in answer set programming. Artificial Intelligence, 2010.

    [Ferraris and Lifschitz, 2005] P. Ferraris and V. Lifschitz. Weight constraints as nested expressions. TPLP, 5:45-74, 2005.

    [Ferraris and Lifschitz, 2010] P. Ferraris and V. Lifschitz. On the stable model semantics of first-order formulas with aggregates. In Nonmonotonic Reasoning, 2010.

    [Gelfond and Lifschitz, 1991] M. Gelfond and V. Lifschitz. Classical negation in logic programs and disjunctive databases. New Generation Computing, 9(3- 4):363-385, 1991.

    [Jayram et al., 2007] T.S. Jayram, S. Kale, and E. Vee. Efficient aggregation algorithms for probabilistic data. In Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007.

    [Niemela and Simons, 2000] I. Niemela and P. Simons. Extending the smodels system with cardinality and weight constraints. In In Jack Minker, editor, LogicBased AI, pages 491-521, 2000.

    [Pelov and Truszczynski, 2004] N. Pelov and M. Truszczynski. Semantics of disjunctive programs with monotone aggregates - an operator-based approach. In NMR, 2004.

    [Pelov et al., 2007] N. Pelov, M. Denecker, and M. Bruynooghe. Well-fouded and stable semantics of logic programs with aggregates. TPLP, 7:355 - 375, 2007.

    [Pelov, 2004] N. Pelov. Semantics of logic programs with aggregates. PhD thesis, Katholieke Univer-siteit Leuven, Leuven, Belgium, 2004.

  • Similar Research Results (2)
  • Metrics
    No metrics available
Share - Bookmark