+********************************************************************** * * * Einladung * * * * Informatik-Oberseminar * * * +********************************************************************** Zeit: Montag, 14. April 2025, 15:00 Uhr Ort: Raum 9222 (Informatikzentrum E3, Ahornstraße 55) Referent: Lovro Mrkonjić, M.Sc. LuFG Mathematische Grundlagen der Informatik Thema: Semiring Semantics: Algebraic Foundations, Model Theory, and Strategy Analysis Abstract: Classically, a logical formula is either true or false in a given structure. In the semiring framework, which was originally developed by Green, Karvounarakis and Tannen for databases in 2007, Boolean truth values are replaced with values from an arbitrary commutative semiring, which may carry additional information. For example, evaluating a formula under semiring semantics in a suitable semiring may not only tell us if the formula is true, but also which of the facts in the input structure contribute to the truth of the formula. Classical models are replaced with semiring interpretations, which assign a semiring element to each literal of a model. This prompts the introduction of model theory to the semiring setting. In this talk, we address the following questions from semiring model theory: How does elementary equivalence behave in the semiring setting? Does the compactness theorem still hold under semiring semantics? It turns out that the answers heavily depend on the algebraic properties of the semiring in question. For example, while it is well-known that first-order logic can axiomatize finite structures up to isomorphism in classical semantics, we find that this is not the case under semiring semantics: Over fully idempotent semirings with at least three elements, there are finite interpretations which are elementarily equivalent, but not isomorphic. We also find that some classical results survive in the semiring setting, for example, the compactness theorem holds on most finite, absorptive semirings. The final part of this talk is dedicated to the semiring framework for games, which was introduced by Grädel and Tannen (2020). We present an extension of the semiring framework to imperfect information games and discuss some computational challenges in this setting. Es laden ein: die Dozentinnen und Dozenten der Informatik