Erich Graedel

Title: Logic and Bisimulation for Guarded Teams

Abstract:
Guarded logics generalize certain desirable features of modal logics to a
more general setting, preserving  their good model-theoretic and
algorithmic properties. In particular, modal characterization theorems can
be lifted to the guarded setting, to provide semantic characterizations
of guarded fragments of first-order and fixed-point logics in terms of
invariance under guarded bisimulation.

Here we investigate guardedness in the context of team semantics in which
logical formulae are evaluated not for a single assignment of values to
variables, but for a set of such assignments. Team semantics is the
mathematical basis of modern logics of dependence and independence,
in which, following a proposal by Väänänen, dependencies are considered as
atomic statements (and not as annotations of quantifiers).

We propose different notions of guarded teams, guarded team logics, and
guarded team bisimulations. We then establish characterization theorems
that relate guarded team logics, invariance under guarded team
bisimulation, and fragments of first-order and second-order logic with
classical Tarski semantics.

This is joint work with Martin Otto.