Elementary Equivalence Versus Isomorphism in Semiring Semantics

We study the first-order axiomatisability of finite semiring interpretations or, equivalently, the question whether elementary equivalence and isomorphism coincide for valuations of atomic facts over a finite universe into a commutative semiring. Contrary to the classical case of Boolean semantics, where every finite structure is axiomatised up to isomorphism by a first-order sentence, the situation in semiring semantics is rather different, and depends on the underlying semiring. We prove that for a number of important semirings, including min-max semirings, and the semirings of positive Boolean expressions, there exist finite semiring interpretations that are elementarily equivalent but not isomorphic. The same is true for the polynomial semirings that are universal for the classes of absorptive, idempotent, and fully idempotent semirings, respectively. On the other side, we prove that for other, practically relevant, semirings such as the Viterbi semiring, the tropical semiring, the natural semiring and the universal polynomial semiring N[X], all finite semiring interpretations are first-order axiomatisable, and thus elementary equivalence implies isomorphism. This talk is based on a paper jointly written with Erich Grädel which will be presented at ICALP 2021 (pre-print: https: //arxiv. org/abs/2102. 05473). During the presentation, I will briefly explain the generalisation of elementary equivalence and isomorphism from classical structures to semiring interpretations and summarise our main results as well as two general techniques to prove axiomatisability or non-axiomatisability of semiring interpretations up to isomorphism.

Authors

• Lovro Mrkonjić

Keywords

No keywords are indexed for this paper.