23 Jan 2012
Nijmegen, The Netherlands
COIN - Coalgebra in the Netherlands, 23 January 2012, Nijmegen
==============================================================
COIN, or Coalgebra in the Netherlands, is a seminar taking place
alternating at the Radboud University Nijmegen and the CWI in
Amsterdam. The aim of COIN is to bring together coalgebra researchers
from various locations in the Netherlands, and share current results
and questions in the world of coalgebra. We welcome presentations on
any subject related to coalgebra.
COIN is coordinated by Marcello Bonsangue (Leiden University/CWI), Bart
Jacobs (Radboud Universiteit Nijmegen), and Jan Rutten (CWI/Radboud
Universiteit Nijmegen), and its website can be found at
http://homepages.cwi.nl/~winter/coin.html
The next COIN meeting is scheduled for Monday, 23 January 2012, at the
Huygens building of the Radboud Universiteit Nijmegen, in room
HG00.086. The schedule is as follows:
14:30 - 15:15 Jörg Endrullis (VU)
Part 1: Causality via productivity
Part 2: Degree of undecidability of stream equality
15:15 - 16:00 Bart Jacobs (RU)
Bases as coalgebras
16:15 - 17:00 Joost Winter (CWI)
Generalized context-freeness
Abstracts
=========
Jörg Endrullis (VU)
Part 1: Causality via productivity
Part 2: Degree of undecidability of stream equality
---------------------------------------------------
The talk consists of two parts:
In part (1) we introduce a concept of relative causality that turns out
to be useful in coinductive proofs, in particular using circular
coinduction. Moreover, we will establish a link between productivity
and causality. Thereby automated methods for proving productivity
become applicable for proving (relative) causality.
In part (2) we investigate the degree of undecidability of equality of
streams specified by systems of equations. This question has been
investigated by G. Rosu in 2006:
"Equality of Streams is a Pi-0-2 complete problem".
However, the results in this paper are based on a peculiar notion of
equality. As it turns out, more conventional choices yield entirely
different results of significantly higher complexity.
Bart Jacobs (RU)
Bases as coalgebras
-------------------
The free algebra adjunction, between the category of algebras of a
monad and the underlying category, induces a comonad on the category of
algebras. The coalgebras of this comonad are the topic of study in this
talk (following earlier work). It is illustrated how such
coalgebras-on-algebras can be understood as bases, decomposing each
element x into primitives elements from which x can be reconstructed
via the operations of the algebra. This holds in particular for the
free vector space monad, but also for other monads. For instance,
continuous dcpos or stably continuous frames, where each element is the
join of the elements way below it, can be described as such coalgebras.
Further, it is shown how these coalgebras-on-algebras give rise to a
comonoid structure for copy and delete, and thus to diagonalisation of
endomaps like in linear algebra.
Joost Winter (CWI)
Generalized context-freeness
----------------------------
We provide a coinductive specification format of algebraic power
series, which can be seen as a generalization of a number of existing
notions, such as context-free languages, weighted context-free
languages, and automatic sequences.
This is done by means of systems of behavioural differential equations
in a specific format, which yield exactly this class of sequences.
Furthermore, connections are given with and between the various
existing notions of algebraic power series.
This is joint work with Jan Rutten (CWI/Radboud University) and
Marcello Bonsangue (Leiden University/CWI).