Universal coalgebra: A theory of systems
type: Item
instance of: scholarly article
title: Universal coalgebra: A theory of systems
zbMATH Open document ID: 0951.68038
DOI: 10.1016/S0304-3975(00)00056-6
published in: Theoretical Computer Science
publication date: 2000-10-26T00:00:00Z
review text: 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 \textit{P. Aczel} [Non-Well-Founded sets, CSLI Lecture 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.
Mathematics Subject Classification ID: 68Q10
Mathematics Subject Classification ID: 68Q55
zbMATH DE Number: 1521867
zbMATH Keywords: universal coalgebra
author: Jan J. M. M. Rutten
MaRDI profile type: Publication
cites work: A domain equation for bisimulation
cites work: Q3992552
cites work: Final universes of processes
cites work: A final coalgebra theorem
cites work: Machines in a category
cites work: Parametrized data types do not need highly constrained parameters
cites work: Solving reflexive domain equations in a category of complete metric spaces
cites work: Q4373409
cites work: Terminal coalgebras in well-founded set theory
cites work: Additions and corrections to ``Terminal coalgebras in well-founded set theory''
cites work: Q4717366
cites work: Q4304740
cites work: Terminal metric spaces of finitely branching and image finite linear processes
cites work: Q3839054
cites work: Q3910579
cites work: Q3722558
cites work: Universal coalgebra and categories of transition systems
cites work: Q3769642
cites work: Bisimulation for probabilistic transition systems: A coalgebraic approach
cites work: A coinduction principle for recursive data types based on bisimulation
cites work: Processes and hyperuniverses
cites work: Q3773852
cites work: Structured operational semantics and bisimulation as a congruence
cites work: Covarieties and complete covarieties
cites work: Q3784044
cites work: Q3907039
cites work: Structural induction and coinduction in a fibrational setting
cites work: Q3024839
cites work: Mongruences and cofree coalgebras
cites work: Q4222959
cites work: Coalgebraic methods in computer science, CMCS '98. Proceedings of the 1st workshop, Lisbon, Portugal, March 28--29, 1998
cites work: Q4355684
cites work: Bisimulation from open maps
cites work: A small final coalgebra theorem
cites work: Formal verification of parallel programs
cites work: Q3798837
cites work: Q4222950
cites work: Bisimulation through probabilistic testing
cites work: Algebraic specification of data types: A synthetic approach
cites work: Final semantics for a higher order concurrent language
cites work: Q5639839
cites work: Q4123496
cites work: Q3735051
cites work: Q3698981
cites work: Q4023900
cites work: Q4077434
cites work: A calculus of communicating systems
cites work: Co-induction in relational semantics
cites work: Coalgebraic logic
cites work: On the Foundations of Corecursion
cites work: Q3907077
cites work: Mechanizing coinduction and corecursion in higher-order logic
cites work: A co-induction principle for recursively defined domains
cites work: Relational properties of domains
cites work: A general Galois theory for cofunctions and corelations
cites work: Q4222954
cites work: An approach to object semantics based on terminal co-algebras
cites work: Processes as terms: non-well-founded models for bisimulation
cites work: Q4251915
cites work: Q4222961
cites work: Q5287518
cites work: The Category-Theoretic Solution of Recursive Domain Equations
cites work: Q3470521
cites work: A lattice-theoretical fixpoint theorem and its applications
cites work: Q4362964
cites work: Q4818861

Universal coalgebra: A theory of systems (cites work)
cites work: Reactive, generative, and stratified models of probabilistic processes

Universal coalgebra: A theory of systems (cites work)
cites work: Q4857386

Universal coalgebra: A theory of systems (full work available at URL)
full work available at URL: s0304-3975(00)00056-6

Universal coalgebra: A theory of systems (OpenAlex ID)
OpenAlex ID: W2088189323