# Your search

MODEL CHECKING AND STATE MACHINES

## Universal coalgebra: a theory of systems

Resource type

Author/contributor

- Rutten, J. J. M. M. (Author)

Title

Universal coalgebra: a theory of systems

Abstract

In the semantics of programming, finite data types such as finite lists, have traditionally been modelled by initial algebras. Later final coalgebras were used in order to deal with infinite data types. Coalgebras, which are the dual of algebras, turned out to be suited, moreover, as models for certain types of automata and more generally, for (transition and dynamical) systems. An important property of initial algebras is that they satisfy the familiar principle of induction. Such a principle was missing for coalgebras until the work of Aczel (Non-Well-Founded sets, CSLI Leethre Notes, Vol. 14, center for the study of Languages and information, Stanford, 1988) on a theory of non-wellfounded sets, in which he introduced a proof principle nowadays called coinduction. It was formulated in terms of bisimulation, a notion originally stemming from the world of concurrent programming languages. Using the notion of coalgebra homomorphism, the definition of bisimulation on coalgebras can be shown to be formally dual to that of congruence on algebras. Thus, the three basic notions of universal algebra: algebra, homomorphism of algebras, and congruence, turn out to correspond to coalgebra, homomorphism of coalgebras, and bisimulation, respectively. In this paper, the latter are taken as the basic ingredients of a theory called universal coalgebra. Some standard results from universal algebra are reformulated (using the aforementioned correspondence) and proved for a large class of coalgebras, leading to a series of results on, e.g., the lattices of subcoalgebras and bisimulations, simple coalgebras and coinduction, and a covariety theorem for coalgebras similar to Birkhoff's variety theorem.

Publication

Theoretical Computer Science

Volume

249

Issue

1

Pages

3-80

Date

October 17, 2000

Series

Modern Algebra

Journal Abbr

Theoretical Computer Science

Language

en

DOI

10/fqrjpn

ISSN

0304-3975

Short Title

Universal coalgebra

Accessed

2019-11-26T20:42:58Z

Library Catalog

ScienceDirect

Extra

ZSCC: 0001448

Citation

Rutten, J. J. M. M. (2000). Universal coalgebra: a theory of systems.

*Theoretical Computer Science*,*249*(1), 3–80. https://doi.org/10/fqrjpn
MODEL CHECKING AND STATE MACHINES

Topic

Attachment

Link to this record