Tuesday, 23.01.2018
10:00

11:00
Seminarraum i7
Master Kolloquium
Abstract:
Provenance analysis is a concept that originated in the field of database theory which unifies several nonstandard semantics
for database queries, such as bag semantics or probabilistic semantics. These different semantics can be captured in an algebraic
framework using various semirings, and are special instances of computations in a general provenance semiring. While the previous
work on provenance semantics focused mainly on positive query languages for databases, Grädel and Tannen recently introduced
provenance semantics for logical languages that also include negation, e.g. full first order logic.
In this master thesis talk we introduce semiring semantics and provenance analysis for logics with team semantics, such as
Väänänen's dependence logic. The main features of these logics are atomic formulae that allow reasoning about dependence and
independence relations between variables. We define semiring semantics for these logics and analyze their properties, e.g.
with respect to locality, closure properties and game theoretic semantics.
We show that in the class of idempotent semirings, many of the known results for booolean semantics are preserved when considering
semiring semantics. This is not the case for general semirings: many logics that are equivalent for boolean semantics can
be separated for semiring semantics. In particular we show that independence logic and existential second order logic are
incomparable for semiring semantics, but certain extensions of these logics remain equivalent.