% 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{Naaf:996756,
author = {Naaf, Matthias Ferdinand},
othercontributors = {Grädel, Erich and Esparza, Javier},
title = {{L}ogic, semirings, and fixed points},
school = {RWTH Aachen University},
type = {Dissertation},
address = {Aachen},
publisher = {RWTH Aachen University},
reportid = {RWTH-2024-10804},
pages = {1 Online-Ressource : Illustrationen},
year = {2024},
note = {Veröffentlicht auf dem Publikationsserver der RWTH Aachen
University 2025; Dissertation, RWTH Aachen University, 2024},
abstract = {Semiring provenance is a successful approach in database
theory, developed over the last two decades, that provides a
unifying framework for various forms of provenance
computations. This is achieved by annotating the database
with semiring values and then defining a semiring semantics
for query languages that combines these values using the
semiring operations, ultimately producing a semiring value
for each answer of the query. By using different semirings,
this approach can cover a wide range of applications: the
Boolean semiring yields standard semantics, the natural
semiring can be used for counting and bag semantics,
semirings on real numbers can model costs or probabilities,
and semirings of polynomials can be used to track which
facts affect the evaluation of a query. This approach was
originally confined to query languages without negation, but
a decade later this limitation was lifted and a semiring
semantics for first-order logic was proposed. This provides
an interesting generalisation of the classical Boolean
semantics to multiple truth values, combining logic and
algebra in a unique way. Indeed, algebraic properties,
homomorphisms, and universal semirings play an important
role in the study of logics under this new semantics. This
becomes even more important for the semiring semantics of
fixed-point logic (LFP), where additional completeness and
continuity assumptions (called full continuity) on the
semiring are needed to guarantee that both least and
greatest fixed points exist and are well behaved. To ensure
that the semantics provides meaningful information (from a
provenance perspective), it is further assumed that the
semirings are absorptive. Of particular interest is thus the
universal fully-continuous and absorptive semiring S(X),
both for provenance applications and as an important tool
for understanding the semantics. In this thesis, we advance
the study of semiring semantics for fixed-point logic in
several directions. An algorithmic aspect concerns the
computation of fixed points arising in the evaluation of
LFP-formulae. Several techniques have been developed to
compute least fixed points in semirings, with the
generalisation of Newton's method to semirings emerging as
the most general technique, but it was not known how to
compute greatest fixed points. We address this problem by
providing a closed-form solution for greatest fixed points
of polynomial systems in absorptive, fully-continuous
semirings. This is a general result about semirings, but
also has implications for the expressive power of LFP
compared to infinitary logic under semiring semantics.
Further contributions on the algebraic side are
generalisations of the universal semiring S(X) by
coefficients and by infinitely many indeterminates, as well
as extensions of semirings by infinitary operations that lay
the foundation for semiring semantics on infinite structures
and for infinitary logic. In the direction of semiring
provenance, we show in a case study on Büchi games how
semiring semantics for LFP can be used for provenance
analysis of infinite games. The resulting provenance values
provide detailed information about winning strategies and
can be used, for instance, to find minimal repairs of the
game arena. Lastly, we take the perspective of model theory
and study how the classical 0-1 laws about the asymptotic
behaviour of logic on random structures can be generalised
to semiring semantics of first-order and infinitary logic
(and hence LFP) for several different semirings.},
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-2024-10804},
url = {https://publications.rwth-aachen.de/record/996756},
}
guest ::