Bonchi, Filippo and Montanari, Ugo - Symbolic and Asynchronous Semantics via Normalized Coalgebras

lmcs:671 - Logical Methods in Computer Science, May 16, 2011, Volume 7, Issue 2
Symbolic and Asynchronous Semantics via Normalized Coalgebras

Authors: Bonchi, Filippo and Montanari, Ugo

The operational semantics of interactive systems is usually described by labeled transition systems. Abstract semantics (that is defined in terms of bisimilarity) is characterized by the final morphism in some category of coalgebras. Since the behaviour of interactive systems is for many reasons infinite, symbolic semantics were introduced as a mean to define smaller, possibly finite, transition systems, by employing symbolic actions and avoiding some sources of infiniteness. Unfortunately, symbolic bisimilarity has a different shape with respect to ordinary bisimilarity, and thus the standard coalgebraic characterization does not work. In this paper, we introduce its coalgebraic models. We will use as motivating examples two asynchronous formalisms: open Petri nets and asynchronous pi-calculus. Indeed, as we have shown in a previous paper, asynchronous bisimilarity can be seen as an instance of symbolic bisimilarity.


Source : oai:arXiv.org:1103.0437
DOI : 10.2168/LMCS-7(2:7)2011
Volume: Volume 7, Issue 2
Published on: May 16, 2011
Submitted on: October 22, 2010
Keywords: Computer Science - Logic in Computer Science,F.3.2


Share

Consultation statistics

This page has been seen 62 times.
This article's PDF has been downloaded 35 times.