NOL Seminar with Erich Grädel
published: 2021-10-12
event date:
2021-10-25
The Nordic Online Logic Seminar is organised monthly over Zoom, with expository talks on topics of interest for the broader logic community. The seminar is open for professional or aspiring logicians and logic aficionados worldwide. If you wish to receive the Zoom ID and password for it, as well as further announcements, please subscribe here: https://listserv.gu.se/sympa/subscribe/nordiclogic.
Next talk: Monday, October 25, 16.00-17.30 CEST (UTC+2), on Zoom (details will be provided to the subscribers)
Title: Semiring Semantics for Logical Statements with Applications to the Strategy Analysis of Games
Speaker: Erich Grädel, Professor of Mathematical Foundations of Computer Science at RWTH Aachen University
Abstract:
Semiring semantics of logical formulae generalises the classical Boolean
semantics by permitting multiple truth values from certain semirings. In the
classical Boolean semantics, a model of a formula assigns to each (instantiated)
literal a Boolean value. K-interpretations, for a semiring K, generalize this by
assigning to each such literal a value from K. We then interpret 0 as false and
all other semiring values as nuances of true, which provide additional
information, depending on the semiring. For example, the Boolean semiring over
{0,1} corresponds classical semantics, the Viterbi-semiring can model confidence
scores, the tropical semiring is used for cost analysis, and min-max-semirings
(A, max, min, a, b) for a totally ordered set (A,<) can model different access
levels. Most importantly, semirings of polynomials, such as N[X], allow us to
track certain literals by mapping them to different indeterminates. The overall
value of the formula is then a polynomial that describes precisely what
combinations of literals prove the truth of the formula.