F-coalgebra

From Wikipedia, the free encyclopedia

You have new messages (last change).

In mathematics, specifically in category theory, an $F$ -coalgebra for an endofunctor

$F : \mathbf{C}\longrightarrow \mathbf{C}$

is an object $A$ of $\mathbf{C}$ together with a $\mathbf{C}$ -morphism

$\alpha : A \longrightarrow FA$ .

In this sense F-coalgebras are dual to F-algebras.

Homomorphisms of $F$ -coalgebras are morphisms

$f:A\longrightarrow B$

in $\mathbf{C}$ such that

$Ff\circ \alpha = \beta \circ f$ .

Thus $F$ -coalgebras for a given functor F constitute a category.

1 Examples
2 Applications
3 References
4 External links
5 See also

[edit] Examples

Consider the functor $F: \mathbf{Set} \longrightarrow \mathbf{Set}$ that sends $X$ to $X\times A+1$ , $F$ -coalgebras $\alpha : X \longrightarrow X\times A+1 = FX$ are then (finite or infinite) streams over the alphabet $A$ , where the elements of $X$ are the states and $α$ is the transition to the next state and 1 means "end of file".

[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).
Jesse Hughes, Bart Jacobs: Simulations in coalgebra. Theor. Comput. Sci. 327(1-2): 71-108 (2004).
Bart Jacobs, Erik Poll: Coalgebras and monads in the semantics of Java. Theor. Comput. Sci. 291(3): 329-349 (2003).
Alexander Kurz: Specifying coalgebras with modal logic. Theor. Comput. Sci. 260(1-2): 119-138 (2001).