G-Reactive Systems as Coalgebras

详细信息    查看全文

• 作者：Filippo Bonchi ; Ugo Montanari
• 关键词：Process calculus ; labelled transition system ; reactive systems ; G-reactve systems ; universal coalgebra
• 刊名：Electronic Notes in Theoretical Computer Science
• 出版年：2008
• 出版时间：21 November 2008
• 年：2008
• 卷：203
• 期：6
• 页码：3-17
• 全文大小：408 K

文摘

The semantics of process calculi has traditionally been specified by labelled transition systems (LTSs), but with the development of name calculi it turned out that definitions employing reduction semantics are sometimes more natural. Reactive Systems à la Leifer and Milner allow to derive from a reduction semantics definition an LTS equipped with a bisimilarity relation which is a congruence. This theory has been extended to G-Reactive Systems by Sassone and Sobocinki in order to properly handle structural equivalence.

Universal Coalgebra provides a categorical framework where bisimilarity can be characterized as final semantics, i.e., each LTS can be mapped to a minimal realization identifying bisimilar states. Moreover, it is often possible to lift coalgebras to an algebraic setting (yielding bialgebras by Turi and Plotkin or, slightly more generally, structured coalgebras by Corradini, Heckel and Montanari) with the property that bisimilarity is compositional with respect to the lifted structure. The existence of minimal realizations is of theoretical interest, but it is even more of practical interest whenever LTSs are employed for finite state verification.

In this paper we show that for every G-Reactive System we can build a coalgebra. Furthermore, if bisimilarity is compositional in the Reactive System, then we can lift this coalgebra to a structured coalgebra.