Contents/conteúdo

Mathematics Department Técnico Técnico

Colloquium  RSS

11/01/2001, 16:30 — 17:30 — Amphitheatre Pa1, Mathematics Building
, Technische Universität Braunschweig

Initial algebras, final coalgebras and specification of systems

The fact that natural numbers can be presented as an initial algebra of a very simple endofunctor \(F\) of the category of sets (viz., \(F: X \mapsto X + 1 )\), and the algebra of finite binary trees as an initial algebra of the endofunctor \(G: X \mapsto (X \times X) + 1\) has inspired in the l970s the theory of abstract data types. A part of that theory has been concerned with infinite structures (e.g., infinite words and infinite trees), for which the formalism of complete partial orders (CPO) or complete metric spaces has been applied. It turns out that another very natural approach to these infinite structures is to consider the dual concept of intial algebra, namely, final coalgebra. As recently demonstrated by J. Rutten, coalgebras present a convenient formalism for describing systems. And final coalgebras often represent important structures, e.g. the (co-)algebra of finite and infinite binary trees is final for the above functor \(G\). Moreover, each of these coalgebras carries a natural CPO structure which, thus, need not be assumed a priori.

link

Colloquium_logo

The Mathematics Colloquium is a series of monthly talks organized by the Department of Mathematics of IST, aiming to be a forum for the presentation of mathematical ideas or ideas about Mathematics. The Colloquium welcomes the participation of faculty, researchers and undergraduate or graduate students, of IST or other institutions, and is seen as an opportunity of bringing together and fostering the building up of ideas in an informal atmosphere.

Organizers: Conceição Amado, Lina Oliveira e Maria João Borges.