Coalgebraic models of computation

This group Coalgebraic models of computation (SEN3.3) is a subgroup of the research group Foundations of Software Engineering  (SEN3). Coordinator of Coalgebraic models of computation: Jan Rutten

This group Coalgebraic models of computation (SEN3.3) is a subgroup of the research group Foundations of Software Engineering  (SEN3).

Coordinator of Coalgebraic models of computation: Jan Rutten

Coalgebra is a general theory of the (infinite, circular) behaviour of automata, dynamical systems and infinite data structures. As such, it offers a unifying mathematical framework for various state-based behavioural systems and (component-based and service-oriented) programming paradigms.

Part of SEN3.3's activities consist of the study and development of the theory of coalgebra.  Past achievements include the foundation of the field of Universal Coalgebra; and the introduction of coalgebraic calculi of so-called behavioural differential equations, with which infinite data structures and automata can be specified in a mathematically rigorous and tractable fashion. Recently Silva, together with Bonsangue and Rutten, has introduced the new field of Kleene Coalgebra, in wich classical results from the foundations of computation are combined with present day coalgebraic insights.

 

SEN3.3 is also involved in various applications of coalgebraic methods, often in close collaboration with our colleagues inside SEN3, but also with other groups inside and outside CWI. Examples include the semantic modelling of Reo, SEN3's paradigm for coordination, in collaboration with De Boer and Arbab (CWI, SEN3); and the coalgebraic modelling of discrete event systems, in collaboration with colleague Van Schuppen (CWI, MAC2). In addition, SEN3.3 has many national and international collaborations, amongst others with the UL (Bonsangue), RUN (Geuvers, Jacobs) , VUA (Klop), TU/e (Zantema, De Vink), in the Netherlands ; and with Imperial College, Oxford University, Cornell, the universities of Dresden and Braunschweig, ENS de Lyon, and others, abroad.

 

Current and future challenges for the research in SEN3.3 include: the further systematic development of the theory of coinduction, notably coinductive calculi of generalised regular expressions (in the in 2010 awarded NWO project CORE); the development of calculi of behavioural differential equations (in the in 2011 awarded NWO project BDE); the study of the combined occurrence of algebraic and coalgebraic structures (in the context of a DFG/NWO project in preparation); and the automation of coalgebraic reasoning and proofs, through the development of suitable tool support,  in collaboration with Rosu (Urbana-Champaign) and Lucanu (Iasi, Romania).

 

Key publications

  • J.J.M.M. Rutten, Universal coalgebra: a theory of systems. In Theoretical Computer Science , 249(1), pp. 3-80, 2000.
  • F. Arbab, C. Baier, M. Sirjani, J.J.M.M. Rutten, Modeling component connectors in Reo by constraint automata. In Science of Computer Programming, Vol. 61(2), pp. 75-113, 2006.
  • A. Silva and J.J.M.M. Rutten. A coinductive calculus of binary trees. In Information and Computation, Volume 208, Issue 5, May 2010, pp. 578-593.
  • A.M. Silva, M.M. Bonsangue, and J.J.M.M. Rutten. Non-deterministic Kleene coalgebras. In Logical Methods in Computer Science, Vol. 6(3) 2010.
  • A. Silva, Kleene Coalgebra. PhD thesis cum laude, Radboud Universiteit Nijmegen, 2010. Promotores:  M. Bonsangue (UL, CWI) and J.J.M.M. Rutten (CWI).

Projects