David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Jack Alan Reynolds
Learn more about PhilPapers
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||No keywords specified (fix it)|
|Categories||categorize this paper)|
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
|Through your library|
References found in this work BETA
No references found.
Citations of this work BETA
No citations found.
Similar books and articles
Johan 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.
Joohyung Lee & Vladimir Lifschitz, Safe Formulas in the General Theory of Stable Models (Preliminary Report).
Jan van Eijck (2012). Action Emulation. Synthese 185 (1):131-151.
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):209-223.
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.
Added to index2011-05-29
Total downloads4 ( #405,485 of 1,725,580 )
Recent downloads (6 months)1 ( #349,436 of 1,725,580 )
How can I increase my downloads?