Zero-One Laws in Semiring Semantics

Semiring semantics evaluates logical statements by values in a commutative semiring, which can model information such as costs or access restrictions. Random semiring interpretations, induced by a probability distribution on the semiring, generalise random structures, which raises the question to what extent the classical 0-1 laws of first-order logic apply to semiring semantics. In this talk, we will see that a 0-1 law holds for for many semirings, that is, every first-order sentence asymptotically almost surely evaluates to a unique semiring value on random semiring interpretations. For finite and infinite lattice semirings, we further show that only three semiring values are possible: 0, 1, and the smallest non-zero value. The proof is a combination of the classical extension axioms and an algebraic representation of first-order sentences tailored to semiring semantics. Joint work with Erich Grädel, Hayyan Helal, and Richard Wilke. Contributed talk given by Matthias Naaf

Authors

• Matthias Naaf RWTH Aachen University, Aachen, Germany

Keywords

No keywords are indexed for this paper.