Fall 2016

Logic and Bisimulation for Guarded Teams

Thursday, November 10th, 2016 10:00 am10:30 am

Add to Calendar

Bisimulation is the crucial notion of symmetry for modal logics. Guarded logics generalize desirable features of modal logics to a much more powerful setting, preserving their good model-theoretic and algorithmic properties. In particular, bisimulations 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, 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.