- 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
If you believe that digital publication of certain material infringes any of your rights or (privacy) interests, please let the Library know, stating your reasons. In case of a legitimate complaint, the Library will make the material inaccessible and/or remove it from the website. Please Ask the Library, or send a letter to: Library of the University of Amsterdam, Secretariat, Singel 425, 1012 WP Amsterdam, The Netherlands. You will be contacted as soon as possible.