Nordic Online Logic Seminar: next talk, on October 25, by Erich Grädel

[Valentin Goranko]

The Nordic Online Logic Seminar (NOL 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.

See the announcement for the next talk below. 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 .

Val Goranko and Graham Leigh
NOL seminar organisers

--------------------------------------
Nordic Online Logic Seminar

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.

This can also be used for strategy analysis in games. Evaluating formulae that define winning regions in a given game in an appropriate
semiring of polynomials provides not only the Boolean information on who wins, but also tells us how they win and which strategies they might use. For this approach, the case of Büchi games is of special interest, not only due to their practical importance, but also because it is the simplest case where the logical definition of the winning region involves a genuine alternation of a greatest and a least fixed point.
We show that, in a precise sense, semiring semantics provide information about all absorption-dominant strategies -- strategies that win with minimal effort, and we discuss how these relate to positional and the more general persistent strategies. This information enables further applications such as game synthesis or determining minimal modifications to the game needed to change its outcome.


-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20211008/fda837fe/attachment-0001.html>