Tsinghua Logic

Coalgebra and Modal Logic

Time:3:00 – 4:30 pm, June 18, 2008
Place:Xinzhai Room 353, Tsinghua University

ABSTRACT:In recent years, Universal Coalgebra has emerged as a general framework for modelling various kinds of state-based evolving systems. Whereas algebras have operations for constructing new elements from old, coalgebras provide means to observe or unfold objects. Thus coalgebras are remarkably well tailored to model the concept of state-based dynamics, where typically, a ‘state of affairs’ can be observed and modified. Of key importance in this area is the concept of behavior, together with related notions such as invariance and observational indistinguishability.

The generality of the concept enables one to build into the type of a coalgebra many different features like input, output, nondeterminism, probability distributions, etc. Thus many fundamental phenomena in computer science (data streams, automata, transition systems), logic (Kripke models and frames) and mathematics (non-well-founded sets, power series) have in fact a very natural coalgebraic modelling.

The talk will have two parts. We start with a gentle introduction to the theory of coalgebra, concentrating on the concept of observational indistinguishability (or bisimulation). In the second part of the talk we discuss the role of modal logic in the theory of coalgebra. We will argue that (a suitably generalized version of) modal logic is the right language for specifying and reasoning about coalgebraic behavior. We will finish with a discussion of a fundamental dynamic distributive law, which has applications in areas as diverse as automata theory, game theory, and topology.
(The talk does not presuppose any previous exposure to coalgebra.)

Welcome to Tsinghua Logic