[logic-ml] Talk by Yde Venema, Thursday this week (17 March)

[Ichiro Hasuo]

Dear colleagues,

This coming Thursday our guest Yde Venema from ILLC, University
of Amsterdam is making a talk at RIMS, Kyoto University.
No registration necessary. See you there!

Best regards,
Ichiro Hasuo
---
RIMS-CS website
http://www.kurims.kyoto-u.ac.jp/~cs/

PS. Our deepest sympathy for those suffering from the tragic
earthquake.


=======
Speaker:
  Yde Venema
  Institute for Logic, Language and Computation
  Universiteit van Amsterdam
  http://staff.science.uva.nl/~yde/

Title:
  Coalgebra automata (towards a universal theory of automata)

Date:
 11.00 - 12.00, Thu 17 Mar 2011

Place:
 Room 478, "Research Bldg. No. 2 (Sougou Kenkyu 2-Goukan)"
   http://www.kyoto-u.ac.jp/en/access/campus/main.htm
   (Next to our CS Lab)
 総合研究2号館 478号室 (CS室のとなりです)
   http://www.kyoto-u.ac.jp/ja/access/campus/map6r_y.htm

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