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