Institute for Logic, Language and Computation
1pm Wednesday, 6th of May, 2009
Room 4.31/4.33, Informatics Forum
Automata operating on infinite objects provide an invaluable tool for the specification and verification of the ongoing behavior of infinite systems. Coalgebra automata generalize the well-known automata that operate on specific types of infinite structures such as words/streams, trees, graphs or transition systems. 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. These results have many applications in the theory of coalgebraic fixpoint logics (which we will not discuss).