Journal of the ACM Bibliography

Bard Bloom, Sorin Istrail, and Albert R. Meyer. Bisimulation can't be traced. Journal of the ACM, 42(1):232-268, January 1995. [BibTeX entry]

In the concurrent language 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. We consider the problem of adding operations to CCS to make bisimulation fully abstract. We define the class of GSOS operations, generalizing the style and technical advantages of CCS operations. We characterize GSOS congruency in as a bisimulation-like relation called ready simulation. Bisimulation is strictly finer than ready simulation, and hence not a congruence for any GSOS language. Copyright 1995 by ACM, Inc.

The abstract is also available as a LaTeX file, a DVI file, or a PostScript file.

Categories and Subject Descriptors: D.3.1 [Programming Languages]: Formal Definitions and Theory -- semantics; D.3.3 [Programming Languages]: Language Constructs and Features -- concurrent programming structures; F.3.2 [Logics and Meanings of Programs]: Semantics of Programming Languages -- algebraic approaches to semantics; operational semantics; I.6.2 [Simulation and Modeling]: Simulation Languages

General Terms: Languages, Theory, Verification

Additional Key Words and Phrases: Bisimulation, structural operational semantics, process algebra, CCS

Selected papers that cite this one

Selected references


  • Journal of the ACM homepage
  • Bibliography top level
  • Journal of the ACM Author Index
  • Search the HBP database