Joint Seminar on Mathematical Structures in Computer Science

Coalgebras provide a natural setting for describing (potentially) infinite behaviour of systems and recurrences via local observations. The theory of coalgebra comprises abstract reasoning principles for the equivalence of system behaviour, abstract composition and transformation operations, coalgebraic logic as a generalisation of modal logic, and tools for analysing long-term behaviour.

In this talk, I will provide an introduction to the field of coalgebra and its techniques, and show that it provides a fundamental understanding of many recursive structures in mathematics and computer science. We will see in depth the usefulness of coalgebraic proof techniques to reason about smooth functions, and sketch out a broad range of examples from probability theory, logic, dynamical systems and programming languages. Moreover, we will illustrate the power of abstraction through a generalisation of the existence theorem of stationary distributions for Markov chains to general coalgebras. Finally, I will highlight a few ongoing research directions.

Coalgebras provide a natural setting for describing (potentially) infinite behaviour of systems and recurrences via local observations. The theory of coalgebra comprises abstract reasoning principles for the equivalence of system behaviour, abstract composition and transformation operations, coalgebraic logic as a generalisation of modal logic, and tools for analysing long-term behaviour.

In this talk, I will provide an introduction to the field of coalgebra and its techniques, and show that it provides a fundamental understanding of many recursive structures in mathematics and computer science. We will see in depth the usefulness of coalgebraic proof techniques to reason about smooth functions, and sketch out a broad range of examples from probability theory, logic, dynamical systems and programming languages. Moreover, we will illustrate the power of abstraction through a generalisation of the existence theorem of stationary distributions for Markov chains to general coalgebras. Finally, I will highlight a few ongoing research directions.

Coinduction in R-modules, for R a commutative ring, is useful in e.g., describing the behaviour of linear weighted automata. In this talk, we describe the construction and properties of final coalgebras with a focus on R-modules. First we sketch the relevant background information on convergence ordinals for finitary functors in locally presentable categories. We then give an example of a binary intersection preserving, finitary functor on the category of abelian groups that fails to converge in ω+ω steps, thus settling a question of Adámek, Milius, and Moss. We relate this to the failure of the Artinian property for ℤ and show that all finitary functors on RMod preserving countable intersections and a generalised notion of monomorphism converge in ω(n + 2) steps, where n is the Krull dimension of R.

Time permitting, we may also explain how conditions for behavioural equivalence to imply bisimulation may be given in terms of the Ext¹ functor from homological algebra. This is joint work with Henning Basold and Chase Ford.

Coalgebras provide a natural setting for describing (potentially) infinite behaviour of systems and recurrences via local observations. The theory of coalgebra comprises abstract reasoning principles for the equivalence of system behaviour, abstract composition and transformation operations, coalgebraic logic as a generalisation of modal logic, and tools for analysing long-term behaviour.

In this talk, I will provide an introduction to the field of coalgebra and its techniques, and show that it provides a fundamental understanding of many recursive structures in mathematics and computer science. We will see in depth the usefulness of coalgebraic proof techniques to reason about smooth functions, and sketch out a broad range of examples from probability theory, logic, dynamical systems and programming languages. Moreover, we will illustrate the power of abstraction through a generalisation of the existence theorem of stationary distributions for Markov chains to general coalgebras. Finally, I will highlight a few ongoing research directions.