A long-standing characteristic of research in the area of Logic and Computation is the use of logical techniques to better understand a wide range of processes and behaviours involving computation. The unique combination of expertise in modal logic, model theory and complexity theory at ILLC is combined here to yield qualitatively new applications to computation.

Research at ILLC has long emphasized update and transfer of information in language use and computation. Originally, this dynamic perspective was focused on update and learning by individuals. But the essential feature of many information-based activities is interaction between several agents, and accordingly, games have become a major paradigm for integration.

The sub programme Games and Interaction is about developing interfaces between logic, computer science, and game theory, with a view toward creating an integrated multi-agent process theory based on modal and dynamic logics with mathematical depth and a wide range of applications. As for the latter, in addition to language and computation, our second aim is developing new interfaces with congenial areas in the socio-economic sciences (decision theory, social choice theory, welfare economics), along topics such as negotiation, fair division, and general multi-agent resource allocation.

The next three sub programmes provide mathematical foundations for these ambitions, while also adding key concerns of their own.

This is particularly so for the sub programme Algebra and Co-Algebra. A heightened sensitivity to the computational costs of information processing has turned modal logic into the most widely spread branch of logic. Modal logic lies at the fault line of algebra and co-algebra, and some basic connections are emerging today. Our main focus here is on: (1) representation of partially ordered algebras, modal canonicity and correspondence; (2) universal co-algebra as a general mathematical framework for the study of behaviour; (3) modal fix point logics, the natural formalisms for reasoning about ongoing behaviour.

While modal logic is largely concerned with expressive power, the other side of the coin is computational complexity of natural information-related tasks. For the sub programme Computation and Complexity the contribution of our CWI-members is crucial. Quantum Computing and Kolmogorov Complexity are still the key words here. In addition, the identification of structural properties that characterize complexity classes remains an ongoing theme. Also, in close cooperation with work on finite model theory in the sub programme Sets and Models methods are developed for descriptive complexity analysis of data base queries, logic programs, and related topics in computer science. Wider applications range from graph theory to semantics of natural language.

All the preceding themes presuppose an up-to-date understanding of the foundations of model theory and set theory, and hence they involve strong links to the foundations of mathematics. The sub programme Sets and Models studies a number of mathematical themes, with games as a running thread. Topics include determinacy axioms, infinitary combinatorics, transfinite and multi-player games, generalized quantifiers, and abstract logics. One recent high-light are Turing machines for infinite computation, and their consequences for recursion theory and automata theory. While firmly grounded in mathematical logic, this sub programme already has applications to natural language, descriptive complexity theory, and modal logic - and it is actively seeking new ones at ILLC, all the way to philosophy and cognition.