F-coalgebra
From Wikipedia, the free encyclopedia
In mathematics, specifically in category theory, an F-coalgebra for an endofunctor
is an object A of 
together with a -morphism
.
In this sense F-coalgebras are dual to F-algebras.
Homomorphisms of F-coalgebras are morphisms
in such that
.
Thus F-coalgebras for a given functor F constitute a category.
Contents |
[edit] Examples
Consider the functor 
that sends X to 
, F-coalgebras 
are then finite or infinite streams over the alphabet A, where X is the set of states, α is the state-transition function, and the element of the singleton set 1 indicates that there are no more A's in the stream.
Let P be the power set construction on the category of sets, considered as a covariant functor. The P-coalgebras are in bijective correspondence with sets with a binary relation. Now fix another set, A: coalgebras for the endofunctor P(A×(-)) are in bijective correspondence with labelled transition systems. Homomorphisms between coalgebras correspond to functional bisimulations between labelled transition systems.
[edit] Applications
In computer science, coalgebra has emerged as a convenient and suitably general way of specifying the reactive behaviour of systems. While algebraic specification deals with functional behaviour, typically using inductive datatypes generated by constructors, coalgebraic specification is concerned with reactive behaviour modelled by coinductive process types that are observable by selectors, much in the spirit of automata theory. An important role is played here by final coalgebras, which are complete sets of possibly infinite behaviours, such as streams. The natural logic to express properties of such systems is coalgebraic modal logic.
[edit] References
- B. Jacobs and J. Rutten, A Tutorial on (Co)Algebras and (Co)Induction. EATCS Bulletin 62, 1997, p.222-259.
- Jan J. M. M. Rutten: Universal coalgebra: a theory of systems. Theor. Comput. Sci. 249(1): 3-80 (2000).
- J. Adámek, Introduction to coalgebra. Theory and Applications of Categories 14 (2005), 157-199
- B. Jacobs, Introduction to Coalgebra. Towards Mathematics of States and Observations (book draft)
- Yde Venema: Automata and Fixed Point Logics: a Coalgebraic Perspective. Information and Computation, 204 (2006) 637-678.
