Fixed point semantics for stream reasoning

Abstract

Menschen sind im Alltag mit Datenströmen (engl. ``streams'') aus ihrer Umgebung konfrontiert und das Schließen (engl. ``reasoning'') aus solchen Datenströmen ist für die menschliche Intelligenz von zentraler Bedeutung. Moderne digitale Dienste, wie zum Beispiel Google und Facebook, generieren in kürzester Zeit zahlreiche Daten die es maschinell zu verarbeiten gilt. Im letzten Jahrzehnt hat sich innerhalb der Künstlichen Intelligenz eine Forschungsrichtung dafür als besonders relevant hervorgehoben---das sogenannte Stream Reasoning. Vor kurzem wurde der regel-basierte Formalismus LARS für das nicht-monotone daten-basierte Schließen unter Anwendung der Antwortmengensemantik entwickelt. Syntaktisch sind LARS-Programme nichts anderes als Logikprogramme mit Negation, die zusätzlich Operatoren zum Ausdrücken zeitlicher Zusammenhänge erlauben, wobei der Fenster-Operator (engl. ``window operator'') von besonderem Interesse ist---dieser erlaubt es, relevante Zeitpunkte auszuwählen. Da LARS fixe Zeitintervalle für die Evaluierung von Programmen voraussetzt, ist der Formalismus in der aktuellen Form nicht flexibel genug, um konstruktiv mit sich rasch verändernden Daten umzugehen. Außerdem hat sich gezeigt, dass die von LARS verwendete und auf FLP-Redukten basierende Erweiterung der Antwortmengensemantik zirkuläre Schlüsse zulässt, wie sie auch von anderen Erweiterungen der klassischen Antwortmengensemantik bereits bekannt sind. Diese Doktorarbeit behebt alle erwähnten Schwächen von LARS und leistet einen Beitrag zu den Grundlagen des Stream Reasonings indem sie eine operationale Fixpunktsemantik für eine flexible Variante von LARS entwickelt die korrekt und konstruktiv in dem Sinne ist, dass Antwortmengen durch iterierte Anwendung eines Fixpunktoperators erzeugt werden und dadurch frei von zirkulären Schlüssen sind.

Reasoning over streams of input data is an essential part of human intelligence. During the last decade stream reasoning has emerged as a research area within the AI-community with many potential applications. In fact, the increased availability of streaming data via services like Google and Facebook has raised the need for reasoning engines coping with data that changes at high rate. Recently, the rule-based formalism LARS for non-monotonic stream reasoning under the answer set semantics has been introduced. Syntactically, LARS programs are logic programs with negation incorporating operators for temporal reasoning, most notably window operators for selecting relevant time points. Unfortunately, by preselecting fixed intervals for the semantic evaluation of programs, the rigid semantics of LARS programs is not flexible enough to constructively cope with rapidly changing data dependencies. Moreover, we show that defining the answer set semantics of LARS in terms of FLP reducts leads to undesirable circular justications similar to other ASP extensions. This thesis fixes all of the aforementioned shortcomings of LARS. More precisely, we contribute to the foundations of stream reasoning by providing an operational fixed point semantics for a fully flexible variant of LARS and we show that our semantics is sound and constructive in the sense that answer sets are derivable bottom-up and free of circular justications.