Program Constructions That Are Safe for Bisimulation
Studia Logica 60 (2):311 - 330 (1998)
| Abstract | 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 | No keywords specified (fix it) | |||||||||
| Categories | No categories specified (fix it) | |||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,882 |
| External links |
 |
| Through your library | Configure |
Similar books and articlesJohan Van Benthem (1998). Program Constructions That Are Safe for Bisimulation. Studia Logica 60 (2):311-330.
Sebastian Enqvist (2013). A General Lindström Theorem for Some Normal Modal Logics. Logica Universalis 7 (2):233-264.
Vedran Čačić & Domagoj Vrgoč (2013). A Note on Bisimulation and Modal Equivalence in Provability Logic and Interpretability Logic. Studia Logica 101 (1):31-44.
Balder ten Cate (2006). Expressivity of Second Order Propositional Modal Logic. Journal of Philosophical Logic 35 (2):209 - 223.
Balder ten Cate (2006). Expressivity of Second Order Propositional Modal Logic. Journal of Philosophical Logic 35 (2).
Albert Visser (2012). A Tractarian Universe. Journal of Philosophical Logic 41 (3):519-545.
Jan Eijck, Ji Ruan & Tomasz Sadzik (2012). Action Emulation. Synthese 185 (S1):131-151.
Carlos Areces, Patrick Blackburn & Maarten Marx (2001). Hybrid Logics: Characterization, Interpolation and Complexity. Journal of Symbolic Logic 66 (3):977-1010.
Johan Van Benthem (2005). Minimal Predicates. Fixed-Points, and Definability. Journal of Symbolic Logic 70 (3):696 - 712.
Wim Ruitenburg (1999). Basic Logic, K4, and Persistence. Studia Logica 63 (3):343-352.
David Fernández Duque (2011). On the Modal Definability of Simulability by Finite Transitive Models. Studia Logica 98 (3):347-373.
Analytics
Monthly downloads |
Added to index2011-05-29Total downloads2 ( #234,778 of 556,909 )Recent downloads (6 months)1 ( #64,931 of 556,909 )How can I increase my downloads? |
My notes
Discussion
