Home › Multilingual Archive Index › F-coalgebra

F-coalgebra

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.

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.

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.

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

External links

• CMCS 2008
• International Workshop on Coalgebraic Methods in Computer Science
• Conference on Algebra and Coalgebra in Computer Science
• B. Jacobs, Introduction to Coalgebra. Towards Mathematics of States and Observations (book draft)

See also

• coalgebra