F-coalgebra

From Wikipedia, the free encyclopedia

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.

Contents

[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 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.

[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).

[edit] External links

[edit] See also