Dependence and Independence, Quantitative Aspects and Counting Constructs in Logic and Games

• Applicant: Professor Dr. Erich Grädel
• Subject Area: Theoretical Computer Science
• Term: from 2015 to 2019
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 270058382

The combination of mathematical logic, automata theory and the theoryof infinite games is the basis of a successful methodology for the synthesisand verification of reactive systems.The main goal of this research project is to extend this methodologyby some relevant components and to strengthen the connections between logics and games with regard to such applications.We focus on two main aspects for such extensions, and on theircombination. On the one hand, we want to develop and strengthenquantitative aspects in logics and the associated game-theoretical models,emphasizing in particular counting constructs of various forms. On the other hand, we investigate logical formalisms and game-theoretical methodsfor dependence and independence, based on the team semantics introduced by Hodges and the logicals systems, initiated by Väänänen, in which notions of dependence and independence are treated as atomic statements. The game models relevant for such logics are, on the one hand, games with imperfect information, and on the other hand, the second-order reachability games that we introduced in our work.Finally, we shall combine these two aspects and integrate quantitative operators and counting constructs in logics for dependence and independence, and into team semantics in general, as well as into the associated game models.

• DFG Programme: Research Grants