- Complementation of coalgebra automata
- Lecture Notes in Computer Science
- Pages (from-to)
- Document type
- Interfacultary Research Institutes
- Institute for Logic, Language and Computation (ILLC)
Coalgebra automata, introduced by the second author, generalize the well-known automata that operate on infinite words/streams, trees, graphs or transition systems. This coalgebraic perspective on automata lays foundation to a universal theory of automata operating on infinite models of computation.
In this paper we prove a complementation lemma for coalgebra automata. More specifically, we provide a construction that transforms a given coalgebra automaton with parity acceptance condition into a device of similar type, which accepts exactly those pointed coalgebras that are rejected by the original automaton. Our construction works for automata operating on coalgebras for an arbitrary standard set functor which preserves weak pullbacks and restricts to finite sets.
Our proof is coalgebraic in flavour in that we introduce and use a notion of game bisimilarity between certain kinds of parity games.
- go to publisher's site
- Proceedings title: Algebra and Coalgebra in Computer Science: Third International Conference, CALCO 2009, Udine, Italy, September
7-10, 2009: proceedings
Place of publication: Berlin
Editors: A. Kurz, M. Lenisa, A. Tarlecki