Show simple item record

dc.contributor.authorBloom, Barden_US
dc.contributor.authorIstrail, Sorinen_US
dc.contributor.authorMeyer, Alberten_US
dc.description.abstractIn the concurrent languages CCS, two programs are considered the same if they are bisimilar. Several years and many researchers have demonstrated that the theory of bisimulation is mathematically appealing and useful in practice. However, bisimulation makes too many distinctions between programs. There are two programs P and Q which are not bisimilar, but nontheless are interchangeable: one may be substituted for the other anywhere in a CCS program and no difference can be seen. Bisimulation is thus not fully abstract. We consider the problem of adding operations to CCS to make bisimulation fully abstract. It is trivial to add an operation achieving full abstraction, but this operation is rather peculiar. We show that bisimilation is not fully abstract with respect to any extension of CCS by CCS-like operations. We give a formal description of "CCS-like," as GSOS and argue by proofs and counterexamples that this is indeed the right class. In the proof of non-full-abstraction a coarser version of bisimulation arises, a notion called ready simulation. We investigate the theory of ready simulation, showing that it possesses the basic properties which make bisimulation attractive. Like bisimulation, it possesses equivalent relational and logical characterizations; it has two additional equivalent characterizations as congruence with respect to all GSOS languages, and with respect to CCS extended by process copying and controlled communication operations. In particular, it is fully abstract for a sensible extension of CCS. As a corollary, we show that bisimulation cannot be fully abstract with respect to any CCS-like languages, observing traces.en_US
dc.format.extent4193108 bytes
dc.format.extent869257 bytes
dc.publisherCornell Universityen_US
dc.subjectcomputer scienceen_US
dc.subjecttechnical reporten_US
dc.titleBisimulation Can't Be Traceden_US
dc.typetechnical reporten_US

Files in this item


This item appears in the following Collection(s)

Show simple item record