LO4: Reasoning under uncertainty by logics of incomplete information

Logics of incomplete information, in their modern incarnations, model uncertainty by assigning to variables not unique values but sets of values and treat notions of dependence and independence as atomic properties of such data sets. They provide tools for reasoning about uncertainty, dependence, and independence on the basis of team semantics, that evaluates each formula on a team of possible assignments. This approach goes back to ideas of Väänänen and Hodges, and the study of expressive power, complexity, proof theory and game-based evaluation methods of such logical systems is a vibrant area of current research.

So far, these logics reason about imperfect information in an essentially qualitative way, and the associated notions of uncertainty and (in)dependence are of a logical rather than of a probabilistic or statistical nature. It is an important current challenge to strengthen these logics and enable them to deal with randomness and probabilistic reasoning. For this purpose it is necessary to extend the underlying semantics, taking multiplicities of data values into account. This can be done in several different ways, e.g., by a multi-team semantics on the basis of multi-sets (aka bags) of assignments, in combination with counting constructs as in recent work. An alternative approach is to exploit aggregate functions or multi-set operations as used in databases and in meta-finite model theory.

The objective of the proposed dissertation project is to explore different variants of logics with appropriately extended team semantics. Of particular interest are: the relationship between logical and probabilistic properties of data sets, the expressive power and algorithmic properties of logical systems under multi-team semantics, and evaluation games for such logics, but taking into account randomness and uncertainty.

(This dissertation project is related to the project AP5.)