Provenienzanalyse und Halbringsemantik für Logiken und Spiele

SS 2024

Anmerkung: Diese Veranstaltung wird in englischer Sprache gehalten.


  • Anmeldung: Bitte melden Sie sich zur Vorlesung über RWTHonline an. Zu den Prüfungen müssen Sie sich separat anmelden.

  • Die vollständigen Lernmaterialien sind nur im Moodle-Lernraum verfügbar.


Art Termin Ort   Veranstalter
V2 Di 14:30 16:00 2350|111 (AH II) Vorlesung (Beginn 9. April) E. Grädel


Semiring provenance is a successful approach, originating in database theory, to provide detailed information on how atomic facts combine to yield the result of a query or the truth of a logical statement. This is achieved by defining semiring semantics for various logics, where we evaluate logical statements not just by true or false, but by values in some comutative semiring. In this course, we introduce semiring semantics and study its properties and applications for provenance analysis of logic and games. More specifically, we may cover these topics:

  • Algebraic and order-theoretic foundations of commutative semirings.
  • Semiring semantics for database query languages (relational algebra, datalog,...) and logics (first-order logic, modal logics, fixed-point logics, ...), with applications to confidence scores, cost computation, and access control.
  • General provenance analysis by semirings of polynomials and formal power series.
  • Model-theoretic and algorithmic properties of semiring semantics.
  • Strategy analysis in finite and infinite games.


  • Commutative semirings and their algebraic properties. Semiring interpretations. Semiring valuations of logical statements, database queries, and positions in games. Fundamental facts about the model theory and complexity of semiring valuations.
  • The student will be able to evaluate logical statements in various semirings, to track which combinations of basic facts are responsible for the truth of a complex statement, to apply semiring valuations in the analyis of issues such as confidence, cost, access control, proof counts, or repairs, and to analyse the available strategies in games via semiring valuations.


  • Mathematische Logik


  • Informatik (M.Sc.) / Theoretische Informatik
  • Mathematik (M.Sc.) / Angewandte Mathematik


Erich Grädel