% 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{Wilke:842872,
author = {Wilke, Richard Marlon},
othercontributors = {Grädel, Erich and Lakemeyer, Gerhard and Väänänen,
Jouko},
title = {{R}easoning about dependence and independence : teams and
multiteams},
school = {RWTH Aachen University},
type = {Dissertation},
address = {Aachen},
publisher = {RWTH Aachen University},
reportid = {RWTH-2022-02743},
pages = {1 Online-Ressource : Illustrationen},
year = {2021},
note = {Veröffentlicht auf dem Publikationsserver der RWTH Aachen
University 2022; Dissertation, RWTH Aachen University, 2021},
abstract = {Team semantics is the mathematical basis of modern logics
for reasoning about dependence and independence. Its core
feature is that formulae are evaluated against a set of
assignments, called a team. This approach dates back to
Hodges (1997) who used it to provide a compositional
semantics for independence friendly logic. Building on this
idea, Väänänen (2007) suggested that dependencies between
variables should be treated as atomic propositions instead
of annotations of quantifiers. However, being based on sets,
team semantics can only be used to reason about the presence
or absence of data. Multiteam semantics instead takes
multiplicities of data into account and is based on
multisets of assignments, called multiteams. In this thesis
we systematically develop and study logics with multiteam
semantics. The specific definitions of the multiteam
semantics of logical operators are justified by postulates
which reflect natural properties that a logic with multiteam
semantics should satisfy. Furthermore, the natural extension
of the game theoretic semantics (GTS) of logics with team
semantics to the multiteam setting is equivalent to the GTS
of our semantics. A wide spectrum of logics with multiteam
semantics is explored with regard to their properties and
expressive power. Some of these results resemble what is
known from team semantics but require new techniques. On the
other side, there are also interesting differences. For
instance, inclusion-exclusion logic in team semantics is
expressively equivalent to independence logic, and thus has
the full power of existential second-order logic. In
multiteam semantics, however, independence cannot be
expressed by any combination of downwards closed and union
closed atoms. Further, we establish connections between
logics with multiteam semantics, logics with team semantics
and variants of existential second-order logic. Moreover, we
investigate model-checking games for logics with multiteam
semantics. A further contribution of this thesis concerns
characterisations of the union closed fragments of logics
with team semantics and existential second-order logic,
resolving problems posed by Galliani and Hella (2013). In
particular, we develop novel model-checking games for team
semantics, called inclusion-exclusion games, and use these
to construct a specific dependency atom, whose first-order
closure captures all union closed properties of teams that
are definable in existential second-order logic. The final
contribution of this thesis concerns logics with inquisitive
semantics which, as observed by Ciardelli (2016), have
striking analogies with logics with team semantics. We
introduce an inquisitive monadic second-order logic (InqMSO)
and give a precise characterisation of Ciardelli’s
inquisitive first-order logic (InqBQ) as a fragment of
InqMSO.},
cin = {117220 / 110000 / 080060},
ddc = {510},
cid = {$I:(DE-82)117220_20140620$ / $I:(DE-82)110000_20140620$ /
$I:(DE-82)080060_20170720$},
pnm = {GRK 2236 - UNRAVEL - UNcertainty and Randomness in
Algorithms, VErification, and Logic (282652900)},
pid = {G:(GEPRIS)282652900},
typ = {PUB:(DE-HGF)11},
doi = {10.18154/RWTH-2022-02743},
url = {https://publications.rwth-aachen.de/record/842872},
}
guest ::