[logic-ml] The 50th ToPS [Apr. 27]

[Kazuyuki ASADA]

[Apologies for multiple copies]

I am pleased to announce the 50th Tokyo Programming Seminar,
which will be held at NII on April 27 (Wed).

Ichiro Hasuo from University of Tokyo and Yde Venema from
University of Amsterdam will be talking about
coalgebra theory and automata theory.

The programme is attached below.
I'm looking forward to meeting you at ToPS.

Best regards,
Kazuyuki Asada

----

The 50th ToPS
http://www.ipl.t.u-tokyo.ac.jp/~tops/upcoming_seminar.html

Time: April 27th (Wed) 2011, 15:00--17:00
Place: Rm. 2004 & 2005, 20F, National Institute of Informatics

Speaker:

(1) Ichiro Hasuo (University of Tokyo)
Introduction to Coalgebra, through Final Sequences

Abstract:
In this talk I wish to deliver an elementary and informal
introduction to the theory of coalgebra---a mathematical
machinery underlying coinductive datatypes in functional
programming---focusing on its aspect of being the categorical
dual to algebra. More specifically, I'll first review the
categorical "initial sequence" construction of an initial
algebra, and then elaborate on its dual--the "final sequence"
construction of a final coalgebra. A trip along these sequences
is a good way to familiarize ourselves with the essence of
induction and coinduction, and the contrast between them.


(2) Yde Venema (University of Amsterdam)
Coalgebra Automata

Abstract:
Automata operating on infinite objects provide an invaluable
tool for the spcification and verification of programs.
Many of the infinite objects studied in this area, such as
words/streams, trees, graphs or transition systems, represent
ongoing behaviour in some way, and provide key specimens of
coalgebras. Hence it make sense to develop a universal theory
of coalgebra automata: automata operating on coalgebras.
The motivation underlying the introduction of coalgebra automata
is to gain a deeper understanding of this branch of automata
theory by studying properties of automata in a uniform manner,
parametric in the type of the recognized structures.
Coalgebraic automata theory thus contributes to Universal
Coalgebra as a mathematical theory of state-based evolving systems.

In the talk we give a quick introduction to coalgebra,
and we introduce the notion of a coalgebra automaton.
We will see that in fact a large part of the theory of parity
automata can be lifted to a coalgebraic level of generality,
and thus indeed belongs to the theory of Universal Coalgebra.
More specifically, coalgebra automata satisfy various closure
properties: under some conditions on the coalgebraic type,
the collection of recognizable languages are closed under taking
union, intersection, complementation, and existential projections.
Time permitting, we will discuss two kinds of coalgebra automata,
corresponding to approaches in coalgebraic logic that are based on,
respectively, relation lifting and predicate liftings. Our results
have many applications in the theory of coalgebraic fixpoint
logics), but these will only be discussed tangentially.