Am Donnerstag, dem 19. February, habe ich einen Vortrag im Internen Seminar gehalten. Urspruenglich hatte ich geplant, einen technischen Einblick in den Beweis des Komplementierungslemmas fuer Koalgebra Automaten aus meiner neuesten Veroeffentlichung mit Yde Venema zu geben einschliesslich unserer spiel- und automatentheoretischen Ergebnisse, dann habe ich aber nur zwei Drittel geschafft. Wenn es der Plan zu laesst, fuehre ich die Details in einem erweiterten Seminar in den naechsten Monaten aus.

Titel Complementation of Coalgebra Automata

Zusammenfassung Coalgebra automata, introduced by Venema, generalise the well-known automata operating on infinite words, such as streams, trees, graphs, or transition systems. The coalgebraic perspective lays foundation for a unified theory of automata operating on infinite models.

We prove a complementation lemma for coalgebra automata. In particular, we provide an algorithm that transforms a given coalgebra automaton into an automaton of similar type accepting precisely those pointed coalgebras rejected by the original automaton. Our construction works for arbitrary Set functors which preserve weak pullbacks and restrict to finite sets.

Our proof is coalgebraic in nature in that we introduce and use the coinductive notion of game bisimilarity between certain kinds of parity graph games.