Open for all UnRAVeL Members: Research Seminar by RTG QuantLA: Semiring Extension of Answer Set Programs and Sum-of-Product Problems

Tuesday, April 27, 2021, 1:00pm

Location: Online Session

Speaker: Thomas Eiter (TU Vienna)

 

Abstract: 

Weighted Logic is a powerful tool for specifying calculations over semirings that depend on qualitative information. This offers the possibility to express quantitative measures of many different natures and to approach respective reasoning problems such as probabilistic reasoning, preferential reasoning and quantitative queries in a uniform manner. In this talk, we shall review recent work on an extension of Answer Set Programming (ASP) with semiring computations, in which weighted formulas are evaluated over the answer sets of a logic program such that the reasoning problems above are supported. Notably, some quantitative extensions of ASP can be formalized using semiring computations, as well as the well-known Problog formalism. The complexity of program evaluation apparently depends much on the the complexity of the underlying semiring, which in turn depends on its representation; under natural conditions, the evaluation problem is in FPSPACE(poly). We then consider the evaluation of specific semiring expressions, namely sum-of-product expressions (SOP), to which many problems such as SAT, #SAT, and probabilistic inference amount. SOPs can be characterized by NP(R), a novel generalization of NP over a semiring R, which links to well-known complexity classes.

joint work with Rafael Kiesel