We introduce aProbLog, a generalization of the probabilistic logic programming language ProbLog. An aProbLog program consists of a set of definite clauses and a set of algebraic facts; each such fact is labeled with an element of a semiring. A wide variety of labels is possible, ranging from probability values to reals (representing costs or utilities), polynomials, Boolean functions or data structures. The semiring is then used to calculate labels of possible worlds and of queries. We formally define the semantics of aProbLog and study the aProbLog inference problem, which is concerned with computing the label of a query. Two conditions are introduced that allow one to simplify the inference problem, resulting in four different algorithms and settings. Representative basic problems for each of these four settings are: is there a possible world where a query is true (SAT), how many such possible worlds are there (#SAT), what is the probability of a query being true (PROB), and what is the most likely world where the query is true (MPE). We further illustrate these settings with a number of tasks requiring more complex semirings.

@inproceedings{KimmigAAAI11,
  author = "Kimmig, Angelika and Van den Broeck, Guy and De Raedt, Luc",
  title = "An algebraic {P}rolog for reasoning about possible worlds",
  booktitle = "Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence, ",
  editor = "Burgard, Wolfram and Roth, Dan",
  publisher = "AAAI Press",
  pages = "209--214",
  year = "2011",
  url="http://starai.cs.ucla.edu/papers/KimmigAAAI11.pdf",
  keywords   = {conference,selective}
}