Streaming and Quantitative Extensions of Answer Set Programming

Abstract

Stream reasoning allows us to draw conclusions in a temporal domain with data that can change at different time points. By using a stream reasoning framework with syntax and semantics based on that of Answer Set Programming (ASP), one obtains an intuitive and declarative formalism. However, while there are vast possibilities to perform quantitative reasoning over static data, the same does not hold in the streaming context. Additionally, (i) there are many different forms quantitative reasoning that (ii) are not trivially integrated into to the temporal setting. We therefore investigate the combination of streaming and quantitative extensions of ASP. First, we introduce two highly general quantitative extensions of ASP by defining an algebraic semantics for quantitative aspects that is based on semirings. These extensions add on the one hand quantitative reasoning capabilities over the set of models and on the other hand succinct specifications of quantitative constraints within the program. For both, we analyze their relation to previous formalisms with similar features mostly showing that ours are a conservative extension. Finally, we combine the quantitative extensions with a temporal framework called LARS to obtain a general framework for quantitative stream reasoning. Apart from their definition, we study the extensions and the general framework in terms of their theoretical properties, including the complexity of typical reasoning tasks, safety of fragments, and expressivity. Second, we notice that reasoning in both extensions involves solving weighted model counting problems over semirings. Interestingly, the complexity of the problem depends on the semiring. However, this dependence has not been characterized. We provide a characterization using a family of novel complexity classes and relate them to well-known classical complexity classes. Last but not least, we consider how reasoning in practice. For this, we only consider a limited fragment, omitting quantitative constraints and temporal aspects but focusing on general quantitative reasoning over the set of models. By a mixture of known results from the literature and novel findings we provide an implementation that at least keeps up with the state of the art in probabilistic reasoning and even provides improved performance on cyclic instances.