Speaker: Phil Pützstück (RWTH Aachen University)
Date and Time: Thursday, April 15th 2021, 16:30-18:00, Amsterdam time.
Title: Logics of Dependence and Independence: The Local Variants.
Abstract. Modern logics of dependence and independence are often based on team semantics, which means that formulae are evaluated not on a single assignment of values to variables, but on a set of such assignments, called a team. This leads to non-classicality and high expressive power, on the level of existential second-order logic. As an alternative, Baltag and van Benthem have proposed a local variant of dependence logic LFD. While its semantics is also based on a team, the formulae are evaluated locally on just one of its assignments, and the team just serves as the supply of the possible assignments that are taken into account in the evaluation process. In this way, LFD retains classical boolean semantics, and was also shown to be decidable for the version without equality; the version with equality being undecidable as a corollary to one of our results.
We extend the idea of localising logics of dependence and independence in a systematic way, taking into account local variants of standard atomic dependency properties: besides dependence and independence, also inclusion, exclusion, and anonymity. We study decidability issues of the local logics, establish characterisation theorems via appropriate notions of bisimulation and present the complexity of model checking problems for these logics.