Ehrenfeucht-Fraïssé Games for Semiring Semantics

Erich Grädel (Invited Speaker)

2:30PM - 3:30PM, Sun, Jun 25.

Semiring semantics is based on the idea to evaluate logical statements not just by true or false, but by values in some commutative semiring. This provides more detailed information about logical formulae or database queries, including cost analysis, confidence scores, access levels and security issues, and counting the number of successful evaluation strategies. Further, provenance semirings of polynomials or formal power series allow as to track which combinations of atomic facts determine the truth of a statement, and how often these facts are used in the evaluation.

This approach has first been developed in database theory, as semiring based provenance analysis for positive query languages, such as conjunctive queries, positive relational algebra or datalog. In recent years, it has been systematically extended to semiring semantics for general logical systems, in particular first-order logic and least fixed point logic and to a method for the strategy analysis of finite and infinite games. This raises the question, which classical logical methods and results carry over to semiring semantics, and how this depends on the algebraic properties of the underlying semiring.

In this talk, we discuss Ehrenfeucht-Fraïssé games and back-and-forth-systems. It turns out that the Ehrenfeucht-Fraïssé-Theorem, which classically gives sound and complete criteria for logical equivalences fails, for certain semirings, in both directions. In others, such as fully idempotent semirings, it at least provides sufficient criteria for logical equivalences. We shall discuss, what information Ehrenfeucht-Fraïssé games may provide for various semirings, including extensions and modifications of the classical games, for instance using bijections and homomorphisms.

[Back to Schedule]