[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.