% IMPORTANT: The following is UTF-8 encoded. This means that in the presence
% of non-ASCII characters, it will not work with BibTeX 0.99 or older.
% Instead, you should use an up-to-date BibTeX implementation like “bibtex8” or
% “biber”.
@PHDTHESIS{Mrkonji:1010223,
author = {Mrkonjić, Lovro},
othercontributors = {Grädel, Erich and Tannen, Val},
title = {{S}emiring semantics: algebraic foundations, model theory,
and strategy analysis},
school = {RWTH Aachen University},
type = {Dissertation},
address = {Aachen},
publisher = {RWTH Aachen University},
reportid = {RWTH-2025-03940},
pages = {1 Online-Ressource : Illustrationen},
year = {2025},
note = {Veröffentlicht auf dem Publikationsserver der RWTH Aachen
University; Dissertation, RWTH Aachen University, 2025},
abstract = {Semiring semantics generalizes classical semantics by
replacing the classical domain of Boolean truth values with
a commutative semiring $\mathcal{S}$. A logical formula
$\psi$ is not evaluated to true or false, but instead to an
element $[\![ \psi ]\!]$ from the semiring $\mathcal{S}$. A
valuation of zero is usually interpreted as “false”,
whereas a nonzero element represents “true” and carries
additional information depending on the semiring
$\mathcal{S}$ in question. For example, polynomial semirings
$\mathbb{N}[X]$ may be used to perform provenance analysis,
where the polynomial $[\![ \psi ]\!]$ provides a detailed
overview of the facts that contribute to the truth of $\psi$
in a certain model. In first-order logic, semiring addition
is used to evaluate disjunctions and existential
quantifiers, while multiplication is used for conjunctions
and universal quantifiers. 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. Since
model-theoretic properties of semiring semantics vary
significantly depending on the semiring $\mathcal{S}$, we
first provide an overview of semiring algebra, focusing in
particular on semirings with infinitary operations and
polynomial semirings. We further introduce separating
homomorphisms as an important algebraic tool in semiring
model theory, which can be applied to gain insights on
semiring semantics by reduction to classical Boolean
semantics. In contrast to classical model theory, we show
that elementary equivalence on finite semiring
interpretations does not coincide with isomorphism on large
classes of semirings, such as the class of fully idempotent
semirings with at least three elements, but first-order
axiomatization of finite semiring interpretations is still
possible on some specific semirings such as $\mathbb{N}$.
Additionally, we generalize the classical compactness
theorem to the semiring setting and prove that it holds on
finite semirings with suitable algebraic properties. We also
study semiring semantics in the field of game theory. The
underlying idea is that positions $v$ in a game
$\mathcal{G}$ are evaluated to some semiring element
$\mathcal{G} [\![ v ]\!] \in \mathcal{S}$, based on
“initial” semiring valuations $\ell$ of the positions
and actions in $\mathcal{G}$. It is known that the sum of
strategies theorem holds in this setting: The final
valuation $\mathcal{G} [\![ v ]\!]$ corresponds to the sum
of the valuations of all strategies starting from $v$. We
extend semiring semantics to games with imperfect
information and show that an adapted version of the sum of
strategies theorem still holds in these games.},
cin = {117220 / 110000},
ddc = {510},
cid = {$I:(DE-82)117220_20140620$ / $I:(DE-82)110000_20140620$},
typ = {PUB:(DE-HGF)11},
doi = {10.18154/RWTH-2025-03940},
url = {https://publications.rwth-aachen.de/record/1010223},
}
guest ::