Program constructions that are safe for bisimulation

Studia Logica 60 (2):311-330 (1998)
It has been known since the seventies that the formulas of modal logic are invariant for bisimulations between possible worlds models — while conversely, all bisimulation-invariant first-order formulas are modally definable. In this paper, we extend this semantic style of analysis from modal formulas to dynamic program operations. We show that the usual regular operations are safe for bisimulation, in the sense that the transition relations of their values respect any given bisimulation for their arguments. Our main result is a complete syntactic characterization of all first-order definable program operations that are safe for bisimulation. This is a semantic functional completeness result for programming, which may be contrasted with the more usual analysis in terms of computational power. The 'Safety Theorem' can be modulated in several ways. We conclude with a list of variants, extensions, and further developments.
Keywords Philosophy   Logic   Mathematical Logic and Foundations   Computational Linguistics
Categories (categorize this paper)
DOI 10.1023/A:1005072201319
 Save to my reading list
Follow the author(s)
My bibliography
Export citation
Find it on Scholar
Edit this record
Mark as duplicate
Revision history
Request removal from index
Download options
Our Archive

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 28,756
Through your library
References found in this work BETA

No references found.

Add more references

Citations of this work BETA
Modality, Bisimulation and Interpolation in Infinitary Logic.Johan van Benthem - 1999 - Annals of Pure and Applied Logic 96 (1-3):29-41.

Add more citations

Similar books and articles

Monthly downloads

Added to index


Total downloads

23 ( #221,085 of 2,177,988 )

Recent downloads (6 months)

1 ( #317,698 of 2,177,988 )

How can I increase my downloads?

My notes
Sign in to use this feature

There  are no threads in this forum
Nothing in this forum yet.

Other forums