Jan Rutten from CWI’s Formal Methods research group was recently awarded by the journal Theoretical Computer Science (TCS) for his much cited article Universal Coalgebra – a theory of systems, on the occasion of the journal’s 40th anniversary. A special online issue appeared on this occasion. The anniversary edition contained the most cited papers, according to Elsevier's citation database Scopus, for each year of the journal’s existence (1975-2015). Rutten's article was the most cited TCS paper of the year 2000 and the second most cited paper in the period 1995 -2004. For this achievement, Rutten received a certificate. Among all papers that TCS has ever published (over 11,000), Universal Coalgebra belongs to the top 10 most cited.
In his paper on Universal Coalgebra Jan Rutten develops the foundations of the theory of coalgebra. Rutten says:
"This is a general formalism for the study of the behavior of all kinds of systems, ranging from dynamical systems and Markov chains (in mathematics), to self-referential statements and paradoxes (in logic), to automata and programming languages (in computer science).
An essential aspect of the coalgebraic method is to study systems (such as hardware systems or computer programs) in terms of what they do rather than in terms of what they are. The emphasis is on the behavior of a system, rather than on how the system has been constructed. For instance, two computer programs that have been written in different ways, may actually behave the same. So from the aspect of a user, the two programs can beconsidered (behaviourally) equivalent.
The theory of coalgebra systematically develops various techniques and methods to reason about this behavioural equivalence of systems. Such techniques can be used to construct smaller systems out of given ones, which still have the same behaviour. This leads, for instance, to smaller but equivalent computer programs and, ultimately, to more efficient implementations."
Coalgebra already existed in the literature since the seventies of the previous century, and had been applied in logic and set theory in the late eighties, by Peter Aczel and Nax Mendler, building on the computational notion of bisimulation developed by Robin Milner, in concurrency theory. The contribution of Rutten's paper has been the systematic development of a universal theory of coalgebra, much along the lines of the theory of universal algebra. This has opened the door to the application of coalgebra in many new and different areas. By now, coalgebra has become one of the standard subjects at many of the major computer science conferences. Moreover, coalgebra is these days being used in a great variety of other sciences, not only logic and mathematics but also economics and even ecology.
More information:
TCS' anniversary journal: 40th Anniversary of Theoretical Computer Science – Top Cited Articles: 1975-2014
Illustrations: Jan Rutten in 2012 (picture: CWI) and the TCS certificate.
