Complementation of coalgebra automata
| Autor: | Kissig, C., Venema, Y., Kurz, A., Lenisa, M., Tarlecki, A. |
|---|---|
| Přispěvatelé: | Logic and Computation (ILLC, FNWI/FGw) |
| Jazyk: | angličtina |
| Rok vydání: | 2009 |
| Předmět: |
Discrete mathematics
Functor TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES Computer science Model of computation Coalgebra Mathematics::Rings and Algebras Timed automaton Modal logic ω-automaton Nonlinear Sciences::Cellular Automata and Lattice Gases Automaton Algebra TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES Mathematics::Quantum Algebra Mathematics::Category Theory Quantum finite automata Automata theory Tree automaton Finite set Computer Science::Formal Languages and Automata Theory |
| Zdroj: | Algebra and Coalgebra in Computer Science: Third International Conference, CALCO 2009, Udine, Italy, September 7-10, 2009 : proceedings, 81-96 STARTPAGE=81;ENDPAGE=96;TITLE=Algebra and Coalgebra in Computer Science Algebra and Coalgebra in Computer Science ISBN: 9783642037405 CALCO |
| ISSN: | 0302-9743 |
| DOI: | 10.1007/978-3-642-03741-2_7 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|